KAIST Discrete Math Seminar

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.

We present a deterministic (1+√5)/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints; Hoogeveen showed that the natural variant of Christofides’ algorithm is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact had been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides’ algorithm variant. Our algorithm also proves an upper bound of (1+√5)/2 on the integrality gap of the path-variant Held-Karp relaxation. The techniques devised in this paper can be applied to other optimization problems as well: these applications include improved approximation algorithms and improved LP integrality gap upper bounds for the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.

This is joint work with Bobby Kleinberg and David Shmoys.