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.

Ilkyoo Choi (최일규), Largest 2-regular subgraphs in 3-regular graphs

October 31st, 2018
Largest 2-regular subgraphs in 3-regular graphs
Ilkyoo Choi (최일규)
Department of Mathematics, Hankuk University of Foreign Studies, Yongin-si
2018/11/26 Mon 5PM-6PM (Bldg. E6-1, Room 1401)
For a graph G, let f2(G) denote the largest number of vertices in a 2-regular subgraph of G. We determine the minimum of f2(G) over 3-regular n-vertex simple graphs G.
To do this, we prove that every 3-regular multigraph with exactly c cut-edges has a 2-regular subgraph that omits at most max{0,⎣(c-1)/2⎦} vertices.
More generally, every n-vertex multigraph with maximum degree 3 and m edges has a 2-regular subgraph that omits at most max{0, ⎣(3n-2m+c-1)/2⎦} vertices.
These bounds are sharp; we describe the extremal multigraphs.
This is joint work with Ringi Kim, Alexandr V. Kostochka, Boram Park, and Douglas B. West.

Jaehoon Kim, Introduction to Graph Decomposition

October 2nd, 2018
Introduction to Graph Decomposition
Jaehoon Kim (김재훈)
Mathematics Institute, University of Warwick, UK
2018/10/15 5PM
Graphs are mathematical structures used to model pairwise relations between objects.
Graph decomposition problems ask to partition the edges of large/dense graphs into small/sparse graphs.
In this talk, we introduce several famous graph decomposition problems, related puzzles and known results on the problems.

Jaehoon Kim, Rainbow subgraphs in graphs

October 2nd, 2018
Rainbow subgraphs in graphs
Jaehoon Kim (김재훈)
Mathematics Institute, University of Warwick, UK
2018/10/15 2:30PM
We say a subgraph H of an edge-colored graph is rainbow if all edges in H has distinct colors. The concept of rainbow subgraphs generalizes the concept of transversals in latin squares.
In this talk, we discuss how these concepts are related and we introduce a result regarding approximate decompositions of graphs into rainbow subgraphs. This has implications on transversals in latin square. It is based on a joint work with Kühn, Kupavskii and Osthus.