Archive for the ‘KAIST Discrete Math Seminar’ Category

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

Wednesday, 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

Tuesday, 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

Tuesday, 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.

Dong Yeap Kang (강동엽), On the rational Turán exponents conjecture

Thursday, September 27th, 2018
On the rational Turán exponents conjecture
Dong Yeap Kang (강동엽)
Department of Mathematical Sciences, KAIST
2018/11/5 Mon 5PM-6PM
The extremal number ex(n,F) of a graph F is the maximum number of edges in an n-vertex graph not containing F as a subgraph. A real number r∈[1,2] is realisable if there exists a graph F with ex(n , F) = Θ(nr). Several decades ago, Erdős and Simonovits conjectured that every rational number in [1,2] is realisable. Despite decades of effort, the only known realisable numbers are 1,7/5,2, and the numbers of the form 1+(1/m), 2-(1/m), 2-(2/m) for integers m≥1. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers 1 and 2.
We discuss some recent progress on the conjecture of Erdős and Simonovits. First, we show that 2-(a/b) is realisable for any integers a,b≥1 with b>a and b≡±1 (mod a). This includes all previously known ones, and gives infinitely many limit points 2-(1/m) in the set of all realisable numbers as a consequence.
Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.
This is joint work with Jaehoon Kim and Hong Liu.

JinHoo Ahn (안진후), Mekler’s Construction on NTP1 Theory

Tuesday, September 18th, 2018
Mekler’s Construction on NTP1 Theory
JinHoo Ahn (안진후)
Department of Mathematics, Yonsei University, Seoul
2018/10/1 Mon 5PM-6PM (E6-1, Room 1401)
Any structure whose language is finite has a model of graph theory which is bi-interpretable with it. From this idea, Mekler further developed a way of interpreting a model into a group. This Mekler’s construction preserves various model-theoretic properties such as stability, simplicity, and NTP2, thus helps us find new group examples in model theory. In this talk, I will introduce to you what Mekler’s construction is and briefly show that this preserves NTP1.