KAIST Discrete Math Seminar

During the last decade, inverse combinatorial optimization problems have found an increased interest in the optimization community. Whereas an optimization problem asks for a feasible solution with minimum or maximum objective function value, inverse optimization problems are defined with a feasible solution, and aim to perturb as little as possible the parameters (costs, profits, etc.) of the problem so that the given solution becomes optimum in the new instance. In this talk, we introduce some generalized inverse combinatorial problems, and investigate inverse chromatic number problems in permutation graphs and interval graphs.

A permutation tableau is a relatively new combinatorial object introduced by Postnikov in his study of totally nonnegative Grassmanian. As one can guess from its name, permutation tableaux are in bijection with permutations. Surprisingly, there is also a connection between permutation tableaux and a statistical physics model called PASEP (partially asymmetric exclusion process). In this talk, we study some combinatorial properties of permutation tableaux. One of our result is a sign-imbalace formula for permutation tableaux which is very similar to the sign-imbalace formula for standard Young tableaux conjectured by Stanley.

In 1989, Stephenson and Zelen derived an elegant formula for the information I_ab contained in all possible paths between two nodes a and b in a network, which is described as follows. Given a finite weighted graph G and its Laplacian matrix L, the combinatorial Green’s function , of G is the inverse of L+J, where J is the all 1’s matrix. Then, it was shown that I_ab=(g_aa+g_bb-2g_ab)^-1, where g_ij is the (i,j)-th entry of . In this talk, we prove an intriguing combinatorial formula for I_ab:

,

where is the complexity, or tree-number, of G, and G_a*b is obtained from G by identifying two vertices a and b. We will discuss several implications of this new formula, including the equivalence of I_ab and the effective conductance between two nodes in electrical networks.