Seog-Jin Kim (김석진), Signed coloring and list coloring of k-chromatic graphs

January 2nd, 2019

IBS/KAIST Joint Discrete Math Seminar

Signed colouring and list colouring of k-chromatic graphs
Seog-Jin Kim (김석진)
Department of Mathematics Education, Konkuk University, Seoul
2019/1/28 Mon 4PM-5PM (Room B232, IBS)
A signed graph is a pair (G, σ), where G is a graph and σ: E(G) → {1,-1} is a signature of G. A set S of integers is symmetric if I∈S implies that -i∈S. A k-colouring of (G,σ) is a mapping f:V(G) → Nk such that for each edge e=uv, f(x)≠σ(e) f(y), where Nk is a symmetric integer set of size k. We define the signed chromatic number of a graph G to be the minimum integer k such that for any signature σ of G, (G, σ) has a k-colouring. Let f(n,k) be the maximum signed chromatic number of an n-vertex k-chromatic graph. This paper determines the value of f(n,k) for all positive integers n ≥ k. Then we study list colouring of signed graphs. A list assignment L of G is called symmetric if L(v) is a symmetric integer set for each vertex v. The weak signed choice number ch±w(G) of a graph G is defined to be the minimum integer k such that for any symmetric k-list assignment L of G, for any signature σ on G, there is a proper L-colouring of (G, σ). We prove that the difference ch±w(G)-χ±(G) can be arbitrarily large. On the other hand, ch±w(G) is bounded from above by twice the list vertex arboricity of G. Using this result, we prove that ch±w(K2⋆n)= χ±(K2⋆n) = ⌈2n/3⌉ + ⌊2n/3⌋. This is joint work with Ringi Kim and Xuding Zhu.

Joonkyung Lee (이준경), Sidorenko’s conjecture for blow-ups

December 25th, 2018

IBS/KAIST Joint Discrete Math Seminar

Sidorenko’s conjecture for blow-ups
Joonkyung Lee (이준경)
Universität Hamburg, Hamburg, Germany
2019/1/3 Thursday 4PM (Room: DIMAG, IBS)
A celebrated conjecture of Sidorenko and Erdős–Simonovits states that, for all bipartite graphs H, quasirandom graphs contain asymptotically the minimum number of copies of H taken over all graphs with the same order and edge density. This conjecture has attracted considerable interest over the last decade and is now known to hold for a broad range of bipartite graphs, with the overall trend saying that a graph satisfies the conjecture if it can be built from simple building blocks such as trees in a certain recursive fashion.Our contribution here, which goes beyond this paradigm, is to show that the conjecture holds for any bipartite graph H with bipartition A∪B where the number of vertices in B of degree k satisfies a certain divisibility condition for each k. As a corollary, we have that for every bipartite graph H with bipartition A∪B, there is a positive integer p such that the blow-up HAp formed by taking p vertex-disjoint copies of H and gluing all copies of A along corresponding vertices satisfies the conjecture. Joint work with David Conlon.

Eun Jung Kim (김은정), New algorithm for multiway cut guided by strong min-max duality

December 17th, 2018

IBS/KAIST Joint Discrete Math Seminar

New algorithm for multiway cut guided by strong min-max duality
Eun Jung Kim (김은정)
CNRS, LAMSADE, Paris, France
2019/01/04 Fri 4PM-5PM (Room: DIMAG, IBS)

Problems such as Vertex Cover and Multiway Cut have been well-studied in parameterized complexity. Cygan et al. 2011 drastically improved the running time of several problems including Multiway Cut and Almost 2SAT by employing LP-guided branching and aiming for FPT algorithms parameterized above LP lower bounds. Since then, LP-guided branching has been studied in depth and established as a powerful technique for parameterized algorithms design.

In this talk, we make a brief overview of LP-guided branching technique and introduce the latest results whose parameterization is above even stronger lower bounds, namely μ(I)=2LP(I)-IP(dual-I). Here, LP(I) is the value of an optimal fractional solution and IP(dual-I) is the value of an optimal integral dual solution. Tutte-Berge formula for Maximum Matching (or equivalently Edmonds-Gallai decomposition) and its generalization Mader’s min-max formula are exploited to this end. As a result, we obtain an algorithm running in time 4k-μ(I)for multiway cut and its generalizations, where k is the budget for a solution.

This talk is based on a joint work with Yoichi Iwata and Yuichi Yoshida from NII.

Hong Liu, Polynomial Schur’s Theorem

December 4th, 2018

IBS/KAIST Joint Discrete Math Seminar

Polynomial Schur’s Theorem
Hong Liu
University of Warwick, UK
2018/12/13 Thu 5PM-6PM (Room B109, IBS)
I will discuss the Ramsey problem for {x,y,z:x+y=p(z)} for polynomials p over ℤ. This is joint work with Peter Pach and Csaba Sandor.

Tony Huynh, A tight Erdős-Pósa function for planar minors

December 4th, 2018

IBS/KAIST Joint Discrete Math Seminar

A tight Erdős-Pósa function for planar minors
Tony Huynh
Université libre de Bruxelles
2018/12/10 5PM-6PM (Room B109, IBS)
Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f(k) such that for all k and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G−X has no H-minor. We prove that this remains true with f(k)=ck log k for some constant c depending on H. This bound is best possible, up to the value of c, and improves upon a recent bound of Chekuri and Chuzhoy. The proof is constructive and yields the first polynomial-time O(log ???)-approximation algorithm for packing subgraphs containing an H-minor.

This is joint work with Wouter Cames van Batenburg, Gwenaël Joret, and Jean-Florent Raymond.