KAIST Discrete Math Seminar

In this talk, we consider the combinatorial formula for the Schur coefficients of the integral form of the Macdonald polynomials. As an attempt to prove Haglund’s conjecture that ⟨J_λ[X;q,q^k]/(1-q)ⁿ,s_μ(X)⟩∈ℕ[q], we have found explicit combinatorial formulas for the Schur coefficients in one row case, two column case and certain hook shape cases. Egge-Loehr-Warrington constructed a combinatorial way of getting Schur expansion of symmetric functions when the expansion of the function in terms of Gessel’s fundamental quasi symmetric functions is given. We apply this method to the combinatorial formula for the integral form Macdonlad polynomials of Haglund-Haiman-Loehr in quasi symmetric functions to get the Schur coefficients and prove the Haglund’s conjecture in more general cases.

The square G² of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in G² if the distance between u and v in G is at most 2. Let χ(H) and χ_l(H) be the chromatic number and the list chromatic number of H, respectively. A graph H is called chromatic-choosable if χ_l(H) = χ(H). It is an interesting problem to find graphs that are chromatic-choosable. Kostochka and Woodall conjectured that χ_l(G²) = χ(G²) for every graph G, which is called List Square Coloring Conjecture. In this paper, we give infinitely many counterexamples to the conjecture. Moreover, we show that the value χ_l(G²) − χ(G²) can be arbitrary large.

A split of a graph is a partition (A,B) of the vertex set V(G) having subsets A₀ of A and B₀ of B such that |A|,|B| > 1 and a vertex a in A is adjacent to a vertex b in B if and only if a is in A₀ and b is in B₀. A graph is prime (with respect to the split decomposition) if it has no split.

We prove that for each n, there exists N such that every prime graph on at least N vertices contains a vertex-minor isomorphic to either a cycle of length n or a graph consisting of two disjoint cliques of size n joined by a matching.

In this talk, we plan to describe a main tool, which is called a blocking sequence in a prime graph, and we will describe two big steps of the proof. And we will pose some open problems behind this result.

This is a joint work with Sang-il Oum.

In this talk we will see a combinatorial way to expand certain continued fractions using lattice paths called Motzkin paths. This method allows us to prove a formula for q-secant numbers. I will explain that this approach can be used to find a finite version of Jacobi’s triple product identity. This talk is based on my paper with Matthieu Josuat-Vergès: “Touchard-Riordan formulas, T-fractions, and Jacobi’s triple product identity”, The Ramanujan Journal, Volume 30, Issue 3, pp 341-378.

A graph G is (0,1)-colorable if V(G) can be partitioned into two sets V₀ and V₁ so that G[V₀] is an independent set and G[V₁] has maximum degree at most 1. The problem of verifying whether a graph is (0,1)-colorable is NP-complete even in the class of planar graphs of girth 9.

Maximum average degree, Mad(G), is a graph parameter measuring how sparse the graph G is. Borodin and Kostochka showed that every graph G with Mad(G) ≤ 12/5 is (0,1)-colorable, thus every planar graph with girth at least 12 also is (0,1)-colorable.

The aim of this talk is to prove that every triangle-free graph G with Mad(G) ≤ 22/9 is (0,1)-colorable. We prove the slightly stronger statement that every triangle-free graph G with |E(H)| < (11|V(H)|+5)/9 for every subgraph H is (0,1)-colorable and show that there are infinitely many non (0,1)-colorable graphs G with |E(G)|= (11|V(G)|+5)/9.

This is joint work with A. V. Kostochka and Xuding Zhu.