KAIST Discrete Math Seminar

The Riordan group is an easy yet powerful tool for looking at a large number of results in combinatorial enumeration. At the first level it provides quick proofs for many binomial identities as well as a systematic way to invert them. We will see how they arise naturally when looking at the uplift principle as applied to classes of ordered trees. We will also discuss some recent results including the Double Riordan group, summer – winter trees, spoiled child trees, and will mention a few open problems as well. The main tools involved are generating functions, matrix multiplication, and elementary group theory.

The chromatic polynomial of a graph counts the number of proper colorings of the graph. We give an affirmative answer to the conjecture of Read (1968) and Welsh (1976) that the absolute values of the coefficients of the chromatic polynomial form a log-concave sequence. We define a sequence of numerical invariants of projective hypersurfaces analogous to the Milnor number of local analytic hypersurfaces. Then we show log-concavity of the sequence by answering a question of Trung and Verma on mixed multiplicities of ideals. The conjecture on the chromatic polynomial follows as a special case.

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.

The notion of a matroid was introduced by H. Whitney in 1935 as an abstraction of “linear independence” in a vector space. In 1960’s, J. Edmonds found that matroids are closely related to an efficient algorithm. After then, many researchers have studied and extended Matroid Theory. In 2007, S. Fujishige, G. A. Koshevoy, and Y. Sano introduced cg-matroids as an generalization of matroids. They defined a matroid-like structure on an abstract convex geometry, where the notion of an abstract convex geometry was introduced by P. H. Edelman and R. E. Jamison in 1985. In this talk, I will introduce the theory of cg-matroids. In particular, I will talk about the definition and some examples of cg-matroids, some combinatorial properties and characterization of cg-matroids, and the relationship between cg-matroids and the greedy algorithm.

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.