KAIST Discrete Math Seminar

We say that a graph property is first order expressible if it can be written as a logic sentence using the universal and existential quantifiers with variables ranging over the nodes of the graph, the usual connectives AND, OR, NOT, parentheses and the relations = and ~, where x ~ y means that x and y share an edge. For example, the property that G contains a triangle can be written as
Exists x,y,z : (x ~ y) AND (x ~ z) AND (y ~ z).</p>

Starting from the sixties, first order expressible properties have been studied extensively on the most commonly studied model of random graphs, the Erdos-Renyi model. A number of very attractive and surprising results have been obtained, and by now we have a fairly full description of the behaviour of first order expressible properties on this model.
The Gilbert model of random graphs is obtained as follows. We take n points uniformly at random from the d-dimensional unit torus, and join two points by an edge if and only their distance is at most r.
In this talk I will discuss joint work with S. Haber which tells a nearly complete story on first order expressible properties of the Gilbert random graph model. In particular we settle several conjectures of McColm and of Agarwal-Spencer.
(Joint with S. Haber)

We prove that the Lam-Shimozono “down operator” on the affine Weyl group induces a derivation of the affine Fomin-Stanley subalgebra of the affine nilCoxeter algebra. We use this to verify a conjecture of Berg, Bergeron, Pon and Zabrocki describing the expansion of k-Schur functions of “near rectangles” in the affine nilCoxeter algebra. Consequently, we obtain a combinatorial interpretation of the corresponding k-Littlewood–Richardson coefficients. This can be found in arxiv:1112.4460 and arxiv:1112.4460.

Recently, Kenyon and Wilson introduced a certain matrix M in order to compute pairing probabilities of what they call the double-dimer model. They showed that the absolute value of each entry of the inverse matrix M^-1 is equal to the number of certain Dyck tilings of a skew shape. They conjectured two formulas on the sum of the absolute values of the entries in a row or a column of M^-1. In this talk we prove the two conjectures. As a consequence we obtain that the sum of the absolute values of all entries of M^-1 is equal to the number of complete matchings. We also find a bijection between Dyck tilings and complete matchings.
This talk is based on the following paper: arxiv:1108.5558.

An old problem raised independently by Jacobson and Schönheim asks to determine the maximum s for which every graph with m edges contains a pair of edge-disjoint isomorphic subgraphs with s edges. We determine this maximum up to a constant factor and show that every m-edge graph contains a pair of edge-disjoint isomorphic subgraphs with at least c (m log m)2/3 edges for some absolute constant c, and find graphs where this estimate is off only by a multiplicative constant. Our results improve bounds of Erdős, Pach, and Pyber from 1987.
Joint work with Po-Shen Loh and Benny Sudakov.

A dynamic coloring of a graph G is a proper coloring of the vertex set V(G) such that for each vertex of degree at least 2, its neighbors receive at least two distinct colors. A dynamic k-coloring of a graph is a dynamic coloring with k colors. Note that the gap χ_d(G) – χ(G) could be arbitrarily large for some graphs. An interesting problem is to study which graphs have small values of χ_d(G) – χ(G).
One of the most interesting problems about dynamic chromatic numbers is to find upper bounds of χ_d(G)$ for planar graphs G. Lin and Zhao (2010) and Fan, Lai, and Chen (recently) showed that for every planar graph G, we have χ_d(G)≤5, and it was conjectured that χ_d(G)≤4 if G is a planar graph other than C₅. (Note that χ_d(C₅)=5.)
As a partial answer, Meng, Miao, Su, and Li (2006) showed that the dynamic chromatic number of Pseudo-Halin graphs, which are planar graphs, are at most 4, and Kim and Park (2011) showed that χ_d(G)≤4 if G is a planar graph with girth at least 7.
In this talk we settle the above conjecture that χ_d≤4 if G is a planar graph other than C₅. We also study the corresponding list coloring called a list dynamic coloring.
This is joint work with Seog-Jin Kim and Won-Jin Park.