KAIST Discrete Math Seminar

We generalize two bijections due to Garsia and Gessel to compute the generating functions of the two vector statistics (des_G, maj, ℓ_G, col) and (des_G, ides_G, maj, imaj, col, icol) over the wreath product of a symmetric group by a cyclic group. Here des_G, ℓ_G, maj, col, ides_G, imaj_G, and icol denote the number of descents, length, major index, color weight, inverse descents, inverse major index, and inverse color weight, respectively. Our main formulas generalize and unify several known identities due to Brenti, Carlitz, Chow-Gessel, Garsia-Gessel, and Reiner on various distributions of statistics over Coxeter groups of type A and B.

Transportation and network polytopes are classical objects in operations research. In this talk, we focus on recent advances on the diameters of several classes of transportation polytopes, motivated by the efficiency of the simplex algorithm. In particular, we discuss results on 2-way transportation polytopes, including a recent result of Stougie and report on joint work with Bruhn-Fujimoto and Pilaud, concerning 2-way transportation polytopes with a certain support structure. We also present a bound on 3-way transportation polytopes in joint work with De Loera, Onn, and Santos. To conclude, we discuss avenues for future work on transportation polytopes and their diameters.

If one draws the Hasse diagram for the face lattice of a polytope, this may appear to be the 1-skeleton of some other polytope. In 1971 Lindström asked whether the intervals of a polytope’s face lattice ordered by containment can be realized as the face lattice of another polytope. If so, this would be the polytope appearing the Hasse diagram. In this talk, I will give necessary and sufficient conditions for the intervals of a polytope’s face lattice to be realizable, and I will provide a counter example showing that not every polytope satisfies these conditions.

The phase transition deals with sudden global changes and is observed in many fundamental problems from statistical physics, mathematics and theoretical computer science, for example, Potts models, graph colourings and random k-SAT. The phase transition in random graphs refers to a phenomenon that there is a critical edge density, to which adding a small amount a drastic change in the size of the largest component occurs. In Erdös-Renyi random graph, which begins with an empty graph on n vertices and edges are added randomly one at a time to a graph, a phase transition takes place when the number of edges reaches n/2 and a giant component emerges. Since this seminal work of Erdös and Renyi, various random graph models have been introduced and studied. In this talk we discuss phase transitions in several random graph models, including Erdös-Renyi random graph, random graphs with a given degree sequence, random graph processes and random planar graphs.

In one of their joint papers, Victor Reiner and Dennis Stanton introduced a (q,t)-generalization of the binomial coefficient. There was an interesting conjecture for the cases when q≤-2 is a negative integer. In this talk, I will prove this conjecture and try to give some combinatorial sense using integer partitions.