## 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.

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

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

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.