For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e\in E(\overline G)$, $G+e$ contains $H$. In this note, we prove a sharp lower bound for the number of paths and walks on length 2 in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $n\to \infty$.

## Extremal and Probabilistic Combinatorics (2021 KMS Spring Meeting)

A special session “Extremal and Probabilistic Combinatorics” at the 2021 KMS Spring Meeting is organized by Tuan Tran.

URL: https://www.kms.or.kr/meetings/spring2021/

## Speakers and Schedule

All talks are on April 30.

- [9:00 am]
**Joonkyung Lee (이준경)**, University College London*Majority dynamics on sparse random graphs*

- [9:30 am]
**Dong Yeap Kang (강동엽)**, Unversity of Birmingham*The Erdős-Faber-Lovász conjecture and related results*

- [10:00 am]
**Jinyoung Park (박진영)**, IAS*The threshold for the square of a Hamilton cycle*

- [10:50 am]
**Debsoumya Chakraborti**, IBS Discrete Mathematics Group*Generalized graph saturation*

- [11:20 am]
**Jaehoon Kim (김재훈)**, KAIST*Resolution of the Oberwolfach problem*

- [11:50 am]
**Hong Liu**, University of Warwick*Sublinear expanders and its applications*

## Abstracts

#### Debsoumya Chakraborti, Generalized graph saturation

Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph G is called *F-saturated* if G does not contain a subgraph isomorphic to F, but the addition of any edge creates a copy of F. We resolve one of the most fundamental questions of minimizing the number of cliques of size r in a $K_s$-saturated graph for all sufficiently large numbers of vertices, confirming a conjecture of Kritschgau, Methuku, Tait and Timmons. We further prove a corresponding stability result. This talk will be based on joint work with Po-Shen Loh.

#### Jaehoon Kim (김재훈), Resolution of the Oberwolfach problem

The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given 2-factor. We show that this can be achieved for all large n. We actually prove a significantly more general result, which allows for decompositions into more general types of factors.

#### Dong Yeap Kang (강동엽), The Erdős-Faber-Lovász conjecture and related results

A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős, Faber, and Lovász in 1972, states that the chromatic index of any linear hypergraph on n vertices is at most n.

In this talk, I will present the ideas to prove the conjecture for all large n. This is joint work with Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.

#### Joonkyung Lee (이준경), Majority dynamics on sparse random graphs

*Majority dynamics* on a graph G is a deterministic process such that every vertex updates its {-1,1}-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O’Donnell, Tamuz and Tan conjectured that, in the Erdős-Rényi random graph G(n,p), the random initial {-1,1}-assignment converges to the unanimity with high probability whenever p>> 1/n.

This conjecture was firstly confirmed for $p>Cn^{-1/2}$ for a large constant C>0 by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, none of them managed to extend it beyond the barrier $p>Cn^{-1/2}$. We prove the conjecture for sparser random graphs G(n,p), where $Dn^{-3/5}\log n < p < C n^{-1/2}$ with a large constant D>0.

Joint work with Debsoumya Chakraborti, Jeong Han Kim and Tuan Tran.

#### Hong Liu, Sublinear expanders and its applications

I will review the history of sublinear expander and present some recent applications, which lead to resolutions of several long-standing problems in sparse graphs embeddings.

#### Jinyoung Park (박진영), The threshold for the square of a Hamilton cycle

We will talk about a recent result of Jeff Kahn, Bhargav Narayanan, and myself stating that the threshold for the random graph G(n,p) to contain the square of a Hamilton cycle is $1/\sqrt n$, resolving a conjecture of Kühn and Osthus from 2012. The proof idea is motivated by the recent work of Frankston and the three aforementioned authors on a conjecture of Talagrand — “a fractional version of Kahn-Kalai expectation threshold conjecture.”

## Jaehoon Kim (김재훈) gave a talk on a resilience version of Pósa’s theorem regarding Hamiltonian cycles at the Discrete Math Seminar

On June 23, 2020, Jaehoon Kim (김재훈) from KAIST presented his work with Padraig Condon, Alberto Espuny Diaz, Daniela Kühn and Deryk Osthus on a resilience version of Pósa’s theorem regarding a sufficient condition on the degree sequence for a graph to have a Hamiltonian cycle at the Discrete Math Seminar. The title of his talk is “A resilience version of Pósa’s theorem“.

## Jaehoon Kim (김재훈), A resilience version of Pósa’s theorem

Pósa’s theorem states that any graph G whose degree sequence $d_1\leq \dots \leq d_n$ satisfies $d_i \geq i+1$ for all $i< n/2$ has a Hamilton cycle. This degree condition is best possible. We show that a similar result holds for suitable subgraphs $G$ of random graphs. This is joint work with Padraig Condon, Alberto Espuny Diaz, Daniela Kühn and Deryk Osthus.

## The 2nd East Asia Workshop on Extremal and Structural Graph Theory

The **2nd East Asia Workshop on Extremal and Structural Graph Theory** is a workshop to bring active researchers in the field of extremal and structural graph theory, especially in the East Asia such as China, Japan, and Korea.

## Date

**Oct 31, 2019** (Arrival Day) – **Nov 4, 2019** (Departure Day)

## Venue and Date

1st floor Diamond Hall

**UTOP UBLESS Hotel**, Jeju, Korea (**유탑유블레스호텔제주**) Address: 502 Johamhaean-ro, Jocheon-eup, Jeju, Korea (제주특별자치도 제주시 조천읍 조함해안로 502) We plan to support the accommodation for invited participants.

## Invited Speakers

**Ping Hu**, Sun Yat-Sen University, China**Jaehoon Kim**, KAIST, Korea**O-joung Kwon**, Incheon National University and IBS Discrete Mathematics Group, Korea**Joonkyung Lee**, University of Hamburg, Germany**Binlong Li**, Northwestern Polytechnical University, China**Hongliang Lu**, Xi’an Jiaotong University, China**Abhishek Methuku**, IBS Discrete Mathematics Group, Korea**Atsuhiro Nakamoto**, Yokohama National University, Japan**Kenta Noguchi**, Tokyo University of Science, Japan**Kenta Ozeki**, Yokohama National University, Japan**Boram Park**, Ajou University, Korea**Yuejian Peng**, Hunan University, China**Zi-Xia Song**, University of Central Florida, U.S.A.**Tomáš Kaiser**, University of West Bohemia, Czech Republic.**Maho Yokota**, Tokyo University of Science, Japan.**Xuding Zhu**, Zhejiang Normal University, China

*More speakers to be announced as soon as confirmed. Last update: September 10.*

## Program

#### Day 0 (Oct. 31 Thursday)

- 4:00PM-6:00Pm Registration and Discussions

#### Day 1 (Nov. 1 Friday)

- 9:00AM-9:20AM Opening address
- 9:20AM-9:50AM
**Jaehoon Kim**,*A quantitative result on the polynomial Schur’s theorem* - 10:00AM-10:30AM
**Yuejian Peng**,*Lagrangian densities of hypergraphs* - 10:30AM-10:50AM Coffee Break
- 10:50AM-11:20AM
**Atsuhiro Nakamoto**,*Geometric quadrangulations on the plane* - 11:30AM-12:00PM
**Ping Hu**,*The inducibility of oriented stars* - 2:00PM-2:30PM
**Boram Park**,*5-star coloring of some sparse graphs* - 2:40PM-3:10PM
**Kenta Ozeki**,*An orientation of graphs with out-degree constraint* - 3:10PM-3:30PM Coffee Break
- 3:30PM-5:30PM Problem session

#### Day 2 (Nov. 2 Saturday)

- 9:20AM-9:50AM
**Xuding Zhu**,*List colouring and Alon-Tarsi number of planar graphs* - 10:00AM-10:30AM
**O-joung Kwon**,*A survey of recent progress on Erdős-Pósa type problems* - 10:30AM-10:50AM Coffee Break
- 10:50AM-11:20AM
**Kenta Noguchi**,*Extension of a quadrangulation to triangulations, and spanning quadrangulations of a triangulation* - 11:30AM-12:00PM
**Zi-Xia Song**,*Ramsey numbers of cycles under Gallai colorings* - 2:00PM-2:30PM
**Binlong Li**,*Cycles through all finite vertex sets in infinite graphs* - 2:40PM-3:10PM
**Tomáš Kaiser**,*Hamilton cycles in tough chordal graphs* - 3:20PM-3:50PM
**Abhishek Methuku**,*On a hypergraph bipartite Turán problem* - 3:50PM-4:10PM Coffee Break
- 4:10PM-6:00PM Problem session and discussion

#### Day 3 (Nov. 3 Sunday)

- 9:20AM-9:50AM
**Joonkyung Lee**,*Odd cycles in subgraphs of sparse pseudorandom graphs* - 10:00AM-10:30AM
**Maho Yokota**,*Connectivity, toughness and forbidden subgraph conditions* - 10:30AM-10:50AM Coffee Break
- 10:50AM-11:20AM
**Hongliang Lu**,*On minimum degree thresholds for fractional perfect matchings and near perfect matchings in hypergraphs* - 11:30AM-12:00PM Contributed Talks
- 2:00PM-6:00PM Problem session / Discussions / Hike

#### Day 4 (Nov. 4 Monday)

- 9:00AM-10:30AM Discussions

## History

- 1st East Asia Workshop on Extremal and Structural Graph Theory
- Nov. 30-Dec. 2, 2018.
- Held at and sponsored by Shanghai Center for Mathematical Sciences in China, under the name “2018 SCMS Workshop on Extremal and Structural Graph Theory”.
- Organizers: Ping Hu, Seog-Jin Kim, Kenta Ozeki, Hehui Wu.

## Organizers

- Seog-Jin Kim, Konkuk University, Korea.
- Sang-il Oum, IBS Discrete Mathematics Group, Korea and KAIST, Korea.
- Kenta Ozeki, Yokohama National University, Japan.
- Hehui Wu, Shanghai Center for Mathematical Sciences, China.

## Sponsor

IBS Discrete Mathematics Group, Korea.

## Abstracts

#### Ping Hu, The inducibility of oriented stars

Let $S_{k,\ell}$ denote the oriented star with $k+\ell$ edges, where the center has out-degree $k$ and in-degree $\ell$. For all $k,\ell$ with $k+\ell$ large, we determine n-vertex digraphs $G$ which maximize the number of induced $S_{k,\ell}$. This extends a result of Huang (2014) for all $S_{k,0}$, and a result of Hladký, Král’ and Norin for $S_{1,1}$. Joint work with Jie Ma, Sergey Norin, and Hehui Wu.

#### Jaehoon Kim, A quantitative result on the polynomial Schur’s theorem

Recently, Liu, Pach, and Sándor [arXiv:1811.05200] proved that for a polynomial $p(z)\in \mathbb{Z}[z]$, any $2$-coloring of $\mathbb{N}$ has infinitely many monochromatic solutions of the equatoin $x+y=p(z)$ if and only if $2\mid p(0)p(1)$. We improve their result in a quantitative way. We prove that if $p(z)$ has degree $d \neq 3$ and $2\mid p(0)p(1)$, then any $2$-coloring of $[n]=\{1,\dots, n\}$ contains at least $n^{2/d^2 -o(1)}$ monochromatic solutions. This is sharp as there exists a coloring of $[n]$ with $O(n^{2/d^2})$ monochromatic solutions. Our method also gives some bound for the case when $d=3$, but it is not sharp. We also prove that if $2\mid p(0)p(1)$, then the interval $[n, p(\lceil \frac{p(n)}{2} \rceil)]$ contains at least one monochromatic solution of $x+y=p(z)$. This is sharp up to multiplicative constant at most two as one can color $[n, \frac{1}{2}p(\lceil \frac{p(n)}{2} \rceil)-1]$ with no monochromatic solutions. Joint work with Hong Liu and Péter Pál Pach.

#### O-joung Kwon, A survey of recent progress on Erdős-Pósa type problems

A graph family $\mathcal{F}$ is said to have the *Erdős-Pósa property* if there is a function $f$ such that for every graph $G$ and an integer $k$, either $G$ contains $k$ disjoint copies of graphs in $\mathcal{F}$, or it has a vertex set of size at most $f(k)$ that hits all copies of graphs in $\mathcal{F}$. This name is motivated from the Erdős-Pósa theorem (1965) which says that the set of cycles has the Erdős-Pósa property. In this talk, we survey on progress of finding various graph families that have the Erdős-Pósa property, and would like to pose interesting open problems.

#### Joonkyung Lee, Odd cycles in subgraphs of sparse pseudorandom graphs

We answer two extremal questions about odd cycles that naturally arise in the study of sparse pseudorandom graphs. Let $\Gamma$ be an $(n,d,\lambda)$-graph, i.e., $n$-vertex, $d$-regular graphs with all nontrivial eigenvalues in the interval $[-\lambda,\lambda]$. Krivelevich, Lee, and Sudakov conjectured that, whenever $\lambda^{2k-1}\ll d^{2k}/n$, every subgraph $G$ of $\Gamma$ with $(1/2+o(1))e(\Gamma)$ edges contains an odd cycle $C_{2k+1}$. Aigner-Horev, Hàn, and the third author proved a weaker statment by allowing an extra polylogarithmic factor in the assumption $\lambda^{2k-1}\ll d^{2k}/n$, but we completely remove it and hence settle the conjecture. This also generalises Sudakov, Szabo, and Vu’s Turán-type theorem for triangles. Secondly, we obtain a Ramsey multiplicity result for odd cycles. Namely, in the same range of parameters, we prove that every 2-edge-colouring of $\Gamma$ contains at least $(1-o(1))2^{-2k}d^{2k+1}$ monochromatic copies of $C_{2k+1}$. Both results are asymptotically best possible by Alon and Kahale’s construction of $C_{2k+1}$-free pseudorandom graphs. Joint work with Sören Berger, Mathias Schacht.

#### Binlong Li, Cycles through all finite vertex sets in infinite graphs

A closed curve in the Freudenthal compactification $|G|$ of an infinite locally finite graph $G$ is called a *Hamiltonian* *curve* if it meets every vertex of $G$ exactly once (and hence it meets every end at least once). We prove that $|G|$ has a Hamiltonian curve if and only if every finite vertex set of $G$ is contained in a cycle of $G$. We apply this to extend a number of results and conjectures on finite graphs to Hamiltonian curves in infinite locally finite graphs. For example, Barnette’s conjecture (that every finite planar cubic 3-connected bipartite graph is Hamiltonian) is equivalent to the statement that every one-ended planar cubic 3-connected bipartite graph has a Hamiltonian curve. It is also equivalent to the statement that every planar cubic 3-connected bipartite graph with a nowhere-zero 3-flow (with no restriction on the number of ends) has a Hamiltonian curve. However, there are 7-ended planar cubic 3-connected bipartite graphs that do not have a Hamiltonian curve. Joint work with André Kündgen and Carsten Thomassen.

#### Hongliang Lu, On minimum degree thresholds for fractional perfect matchings and near perfect matchings in hypergraphs

We study degree conditions for the existence of large matchings and fractional perfect matching in uniform hypergraphs. Firstly, we give some sufficient conditions for $k$-graphs to have fractional perfect matching in terms of minimum degree. Secondly, we prove that for integers $k,l,n$ with $k\ge 3$, $k/2<l<k$, and $n$ large, if $H$ is a $k$-uniform hypergraph on $n$ vertices and $\delta_{l}(H)>{n-l\choose k-l}-{(n-l)-(\lceil n/k \rceil-2)\choose 2}$, then $H$ has a matching covering all but a constant number of vertices. When $l=k-2$ and $k\ge 5$, such a matching is near perfect and our bound on $\delta_l(H)$ is best possible. When $k=3$, with the help of an absorbing lemma of Hàn, Person, and Schacht, our proof also implies that $H$ has a perfect matching, a result proved by Kühn, Osthus, and Treglown and, independently, of Kahn. Joint work with Xingxing Yu and Xiaofan Yuan.

#### Abhishek Methuku, On a hypergraph bipartite Turán problem

Let $t$ be an integer such that $t\geq 2$. Let $K_{2,t}^{(3)}$ denote the triple system consisting of the $2t$ triples $\{a,x_i,y_i\}$, $\{b,x_i,y_i\}$ for $ 1 \le i \le t$, where the elements $a, b, x_1, x_2, \ldots, x_t,$ $y_1, y_2, \ldots, y_t$ are all distinct. Let $ex(n,K_{2,t}^{(3)})$ denote the maximum size of a triple system on $n$ elements that does not contain $K_{2,t}^{(3)}$. This function was studied by Mubayi and Verstraëte, where the special case $t=2$ was a problem of Erdős that was studied by various authors. Mubayi and Verstraëte proved that $ex(n,K_{2,t}^{(3)})<t^4\binom{n}{2}$ and that for infinitely many $n$, $ex(n,K_{2,t}^{(3)})\geq \frac{2t-1}{3} \binom{n}{2}$. These bounds together with a standard argument show that $g(t):=\lim_{n\to \infty} ex(n,K_{2,t}^{(3)})/\binom{n}{2}$ exists and that \[\frac{2t-1}{3}\leq g(t)\leq t^4.\] Addressing a 15 year old question of Mubayi and Verstraëte on the growth rate of $g(t)$, we prove that as $t \to \infty$, \[g(t) = \Theta(t^{1+o(1)}).\] Joint work with Beka Ergemlidze and Tao Jiang.

#### Atsuhiro Nakamoto, Geometric quadrangulations on the plane

Let $P$ be a point set on the plane with $|P| \geq 4$ in a *general position *(i.e., no three points lie on the same straight line). A *geometric quadrangulation* $Q$ on $P$ is a *geometric* plane graph (i.e., every edge is a straight segment) such that the outer cycle of $Q$ coincides with the boundary of the convex hull ${\rm Conv}(P)$ of $P$ and that each finite face of $Q$ is quadrilateral. We say that $P$ is *quadrangulatable* if $P$ admits a geometric quadrangulation. It is easy to see that if $P$ has an even number of points on the boundary of ${\rm Conv}(P)$, then $P$ is quadrangulatable. Suppose that $P$ is $k$-colored for $k \geq 2$, and that no two consecutive points on the boundary of ${\rm Conv}(P)$ have the same color. Let us consider whether $P$ is quadrangulatable with no edge joining two points with the same color. Then we see that $P$ is not necessarily quadrangulatable. Hence, introducing *Steiner points* $S$ for $P$, which are ones put in the interior of ${\rm Conv}(P)$ as we like, we consider whether $P \cup S$ is quadrangulatable. Intuitively, for any $k$-colored $P$, adding sufficiently large Steiner points $S$, we wonder if $P \cup S$ is quadrangulatable. However, we surprisingly see that it is impossible when $k=3$ (Alvarez et al., 2007). In my talk, we summarize these researches on quadrangulatability of point sets with Steiner points, and describe a relation with coloring of topological quadrangulations (Alvarez and Nakamoto, 2012 and Kato et al., 2014). Moreover, we describe a recent progress on a similar topic on quadrangulatability of a polygon with Steiner points.

#### Kenta Noguchi, Extension of a quadrangulation to triangulations, and spanning quadrangulations of a triangulation

A *triangulation* (resp., a *quadrangulation*) on a surface $S$ is a map of a graph (possibly with multiple edges and loops) on $S$ with each face bounded by a closed walk of length $3$ (resp., $4$). In this talk, we focus on the relationship between triangulations and quadrangulations on a surface. (I) An *extension* of a graph $G$ is the construction of a new graph by adding edges to some pairs of vertices in $G$. It is easy to see that every quadrangulation $G$ on any surface can be extended to a triangulation by adding a diagonal to each face of $G$. If we require the resulting triangulation to have more properties, the problem might be difficult and interesting. Our two main results are as follows. Every quadrangulation on any surface can be extended to an even (i.e. Eulerian) triangulation. Furthermore, we give the explicit formula for the number of distinct even triangulations extended from a given quadrangulation on a surface. These completely solves the problem raised by Zhang and He (2005). (II) It is easy to see that every loopless triangulation $G$ on any surface has a quadrangulation as a spanning subgraph of $G$. As well as (I), if we require the resulting quadrangulation to have more properties, the problem might be difficult and interesting. Kündgen and Thomassen (2017) proved that every loopless even triangulation $G$ on the torus has a spanning nonbipartite quadrangulation, and that if $G$ has sufficiently large face width, then $G$ also has a bipartite one. We prove that a loopless even triangulation $G$ on the torus has a spanning bipartite quadrangulation if and only if $G$ does not have $K_7$ as a subgraph. This talk is based on the papers (2015, 2019, 2019). Joint work with Atsuhiro Nakamoto and Kenta Ozeki.

#### Kenta Ozeki, An orientation of graphs with out-degree constraint

An *orientation* of an (undirected) graph $G$ is an assignment of directions to each edge of $G$. An orientation with certain properties has much attracted because of its applications, such as a list-coloring, and Tutte’s $3$-flow conjecture. In this talk, we consider an orientation such that the out-degree of each vertex is contained in a given list. For an orientation $O$ of $G$ and a vertex $v$, we denote by $d_O^+(v)$ the *out-degree* of $v$ in the digraph $G$ with respect to the orientation $O$. Recall that the number of outgoing edges is the out-degree. We denote by $\mathbb{N}$ the set of natural numbers (including $0$). For a graph $G$ and a mapping $L: V(G)\rightarrow 2^{\mathbb{N}}$, an orientation $O$ of $G$ such that \[d_O^+(v) \in L(v)\] for each vertex $v$ is called an $L$-orientation. In this talk, we pose the following conjecture. **Conjecture**. Let $G$ be a graph and let $L: V(G) \rightarrow 2^{\mathbb{N}}$ be a mapping. If \[|L(v)| \ \geq \ \frac{1}{2}\Big(d_G(v) +3\Big)\]for each vertex $v$, then $G$ has an $L$-orientation. I will explain some results related to Conjecture; the best possibility if it is true, and partial solutions for bipartite graphs. However, it is open even for complete graphs. This talk is based on the paper https://doi.org/10.1002/jgt.22498. Joint work with S. Akbari, M. Dalirrooyfard, K.Ehsani, and R. Sherkati.

#### Boram Park, 5-star coloring of some sparse graphs

A *star $k$-coloring* of a graph $G$ is a proper (vertex) $k$-coloring of $G$ such that the vertices on a path of length three receive at least three colors. Given a graph $G$, its *star chromatic number*, denoted $\chi_s(G)$, is the minimum integer $k$ for which $G$ admits a star $k$-coloring. Studying star coloring of sparse graphs is an active area of research, especially in terms of the maximum average degree $\mathrm{mad}(G)$ of a graph $G$. It is known that for a graph $G$, if $\mathrm{mad}(G)<\frac{8}{3}$, then $\chi_s(G)\leq 6$ (Kündgen and Timmons, 2010), and if $\mathrm{mad}(G)< \frac{18}{7}$ and its girth is at least 6, then $\chi_s(G)\le 5$ (Bu et al., 2009). We improve both results by showing that for a graph $G$ with $\mathrm{mad}(G)\le \frac{8}{3}$, then $\chi_s(G)\le 5$. As an immediate corollary, we obtain that a planar graph with girth at least 8 has a star 5-coloring, improving the best known girth condition for a planar graph to have a star 5-coloring (Kündgen and Timmons, 2010 and Timmons, 2008). Joint work with Ilkyoo Choi.

#### Yuejian Peng, Lagrangian densities of hypergraphs

Given a positive integer $n$ and an $r$-uniform hypergraph $H$, the *Turán number* $ex(n, H)$ is the maximum number of edges in an $H$-free $r$-uniform hypergraph on $n$ vertices. The *Turán density* of $H$ is defined as \[\pi(H)=\lim_{n\rightarrow\infty} { ex(n,H) \over {n \choose r } }.\] The *Lagrangian density* of an $r$-uniform graph $H$ is \[\pi_{\lambda}(H)=\sup \{r! \lambda(G):G\;\text{is}\;H\text{-free}\},\] where $\lambda(G)$ is the Lagrangian of $G$. The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Recently, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. The Lagrangian density of an $r$-uniform hypergraph $H$ is the same as the Turán density of the extension of $H$. Therefore, these two densities of $H$ equal if every pair of vertices of $H$ is contained in an edge. For example, to determine the Lagrangian density of $K_4^{3}$ is equivalent to determine the Turán density of $K_4^{3}$. For an $r$-uniform graph $H$ on $t$ vertices, it is clear that $\pi_{\lambda}(H)\ge r!\lambda{(K_{t-1}^r)}$, where $K_{t-1}^r$ is the complete $r$-uniform graph on $t-1$ vertices. We say that an $r$-uniform hypergraph $H$ on $t$ vertices is $\lambda$-perfect if $\pi_{\lambda}(H)= r!\lambda{(K_{t-1}^r)}$. A result of Motzkin and Straus implies that all graphs are $\lambda$-perfect. It is interesting to explore what kind of hypergraphs are $\lambda$-perfect. We present some open problems and recent results.

#### Zi-Xia Song, Ramsey numbers of cycles under Gallai colorings

For a graph $H$ and an integer $k\ge1$, the *$k$-color Ramsey number $R_k(H)$* is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $m\ge4 $ vertices. For odd cycles, Bondy and Erdős in 1973 conjectured that for all $k\ge1$ and $n\ge2$, $R_k(C_{2n+1})=n\cdot 2^k+1$. Recently, this conjecture has been verified to be true for all fixed $k$ and all $n$ sufficiently large by Jenssen and Skokan; and false for all fixed $n$ and all $k$ sufficiently large by Day and Johnson (2017). Even cycles behave rather differently in this context. Little is known about the behavior of $R_k(C_{2n})$ in general. In this talk we will present our recent results on Ramsey numbers of cycles under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. We prove that the aforementioned conjecture holds for all $k$ and all $n$ under Gallai colorings. We also completely determine the Ramsey number of even cycles under Gallai colorings. Joint work with Yaojun Chen and Fangfang Zhang.

#### Tomáš Kaiser, Hamilton cycles in tough chordal graphs

Chvátal conjectured in 1973 that all graphs with sufficiently high toughness are Hamiltonian. The conjecture remains open, but it is known to be true for various classes of graphs, including chordal graphs, claw-free graphs or planar graphs. We will discuss the case of chordal graphs and outline our proof that 10-tough chordal graphs are Hamiltonian, relying on a hypergraph version of Hall’s Theorem as our main tool. This improves a previous result due to Chen et al. (1998) where the constant $10$ is replaced by $18$. Joint work with Adam Kabela.

#### Maho Yokota, Connectivity, toughness and forbidden subgraph conditions

Let $\textrm{conn}(G)$ and $\textrm{tough}(G)$ denote the connectivity and the toughness of $G$. We know that low connectivity implies low toughness; if $\textrm{conn}(G)\leq k$, then $\textrm{tough}(G) \leq k/2$. On the other hand, we also know the converse is not true. We can construct a graph with high connectivity and low toughness. About this, we have next proposition. **Proposition 1**. Let $G$ be a graph, $k$ be an integer with $k\geq 1$ and $r$ be a real number with $r>1$. If $G$ is $k$-connected and $K_{1,\lfloor r \rfloor +1}$-free, then $\textrm{tough}(G)\geq k/r$. It means high connectivity implies high toughness under the star-free condition. Our purpose is to prove assertions which can be regarded as a converse of this statement; that is say, we ask what we can say about $\mathcal H$ if high connectivity implies high toughness in the family of $\mathcal H$-free graphs. About this question, Ota and Sueiro (2013) proved the following theorem. **Theorem 1** (Ota and Sueiro). Let $H$ be a connected graph and $\tau$ be a real number with $0<\tau\leq 1/2$. Almost all $H$-free connected graphs $G$ satisfy $\textrm{tough}(G)\geq \tau$ if and only if $K_{1,\lfloor 1/\tau \rfloor +1}$ contains $H$ as an induced subgraph. Our main result is high connectivity versions of this theorem. We proved the following theorems. **Theorem 2**. Let $H$ be a connected graph, $k$ be an integer with $k\geq 1$ and $r$ be a real number with $r>1$. Almost all $H$-free $k$-connected graphs $G$ satisfy $\textrm{tough}(G)\geq k/r$ if and only if $K_{1,\lfloor 1/\tau \rfloor +1}$ contains $H$ as an induced subgraph. **Theorem 3**. Let $\mathcal H=\{H_1,H_2\}$ be a family of connected graphs, $k$ be an integer with $k\geq 1$ and $r$ be a real number with $r>1$. Almost all $\mathcal H$-free $k$-connected graphs $G$ satisfy $\textrm{tough}(G)\geq k/r$ if and only if $K_{1,\lfloor 1/\tau \rfloor +1}$ contains one of $H$ as an induced subgraph.

#### Xuding Zhu, List colouring and Alon-Tarsi number of planar graphs

A *$d$-defective colouring* of a graph $G$ is a colouring of the vertices of $G$ such that each vertex $v$ has at most $d$ neighbours coloured the same colour as $v$. We say $G$ is *$d$-defective $k$-choosable* if for any $k$-assignment $L$ of $G$, there exists a $d$-defective $L$-colouring, i.e., a $d$-defective colouring $f$ with $f(v) \in L(v)$ for each vertex $v$. It was proved by Eaton and Hull (1999) and Škrekovski (1999) that every planar graph is $2$-defective $3$-choosable, and proved by Cushing and Kierstead (2010) that every planar graph is $1$-defective $4$-choosable. In other words, for a planar graph $G$, for any $3$-assigment $L$ of $G$, there is a subgraph $H$ with $\Delta(H) \le 2$ such that $G-E(H)$ is $L$-colourable; and for any $4$-list assignment $L$ of $G$, there is a subgraph $H$ with $\Delta(H) \le 1$ such that $G-E(H)$ is $L$-colourable. An interesting problem is whether there is a subgraph $H$ with $\Delta(H) \le 2$ such that $G-E(H)$ is $3$-choosable, and whether there is a subgraph $H$ with $\Delta(H) \le 1$ such that $G-E(H)$ is $4$-choosable. It turns out that the answer to the first question is negative and the answer to the second question is positive. Kim, Kim and I proved that there is a planar graph $G$ such that for any subgraph $H$ with $\Delta(H)=3$, $G-E(H)$ is not $3$-choosable. Grytczuk and I proved that every planar graph $G$ has a matching $M$ such that $G-M$ has Alon-Tarsi number at most $4$, and hence is $4$-choosable. The late result also implies that every planar graph is $1$-defective $4$-paintable. For a subset $X$ of $V(G)$, let $f_X$ be the function defined as $f_X(v)=4$ for $v \in X$ and $f_X(v)=5$ for $v \in V(G)-X$. Our proof also shows that every planar graph $G$ has a subset $X$ of size $|X| \ge |V(G)|/2$ such that $G$ is $f_X$-AT, which implies that $G$ is $f_X$-choosable and also $f_X$-paintable. In this talk, we shall present the proof and discuss possible strengthening of this result.

## “2019 Combinatorics Workshop” was held from August 13 to August 15, 2019 at Incheon.

The **2019 Combinatorics Workshop (2019 조합론 학술대회)** was held from August 13, 2019 to August 15, 2019 at the SKYPARK Hotel, Songdo, Incheon. There were 16 talks.

### Plenary Speaker

- Mihyun Kang (강미현), Graz University of Technology

### Keynote Speakers

- Jaehoon Kim (김재훈), KAIST
- Seung Jin Lee (이승진), Seoul National University
- Meesue Yoo (유미수), Dankook University

### Invited Speakers

- Eun-Kyung Cho (조은경), Hankuk University of Foreign Studies
- Soogang Eoh (어수강), Seoul National University
- JiSun Huh (허지선), Sungkyunkwan University
- Jihyeug Jang (장지혁), Sungkyunkwan University
- Dong Yeap Kang (강동엽), KAIST and IBS Discrete Mathematics Group
- Min Jeong Kang (강민정), Incheon National University
- Dabeen Lee (이다빈), IBS Discrete Mathematics Group
- Kang-Ju Lee (이강주), Seoul National University
- Myeonghwan Lee (이명환), Incheon National University
- Jihye Park (박지혜), Yeungnam University
- Sun-mi Yun (윤선미), Sungkyunkwan University

## 2019 Combinatorics Workshop

The annual conference on Combinatorics Workshop (조합론 학술대회) began in 2004 by the Yonsei University BK21 Research Group. This year it will take place in Songdo, Incheon, August 13-15, 2019.

Due to the capacity (50 persons) of the place, we are able to limit your registration. In principle, registration is on a first-come, first-served basis.

**Title**2019 Combinatorics Workshop (2019 조합론 학술대회)**Date**August 13-15 (Tue-Thu), 2019**Venue**Hotel Skypark, Songdo, Incheon**Web**https://cw2019.combinatorics.kr

We are going to

- give six 50-minute talks and ten 25-minute talks in Korean.
- distribute the program and abstracts of CW2019.
- provide for the accommodations for all participants.
- provide for six meals (two breakfasts, two luncheons, one dinner, and one banquet) for all participants.

# Plenary Speaker

- Mihyun Kang, Graz University of Technology

# Keynote Speakers

- Jaehoon Kim, KAIST
- Seung Jin Lee, Seoul National University
- Meesue Yoo, Dankook University

# Invited Speakers

- Eun-Kyung Cho, Hankuk University of Foreign Studies
- Soogang Eoh, Seoul National University
- JiSun Huh, Sungkyunkwan University
- Jihyeug Jang, Sungkyunkwan University
- Dong Yeap Kang, KAIST and IBS Discrete Mathematics Group
- Min Jeong Kang, Incheon National University
- Dabeen Lee, IBS Discrete Mathematics Group
- Kang-Ju Lee, Seoul National University
- Myeonghwan Lee, Incheon National University
- Jihye Park, Yeungnam University
- Sun-mi Yun, Sungkyunkwan University

# Organizing Committee

- O-joung Kwon, Incheon National University and IBS Discrete Mathematics Group
- Suil O, SUNY Korea
- Sang-il Oum, IBS Discrete Mathematics Group and KAIST
- Heesung Shin, Inha University

# Advisory Committee

- Committee of Discrete Mathematics, The Korean Mathematical Society (Chair: Seog-Jin Kim, Konkuk University)

# Sponsors

- IBS Discrete Mathematics Group
- NRF (National Research Foundation of Korea)

## “2019-2 IBS One-Day Conference on Extremal Graph Theory” was held on August 12, 2019.

The 2019-2 IBS One-Day Conference on Extremal Graph Theory was held on August 12, 2019 at the IBS Discrete Mathematics Group. There were four talks. Here is a list of talks.

- Jaehoon Kim (김재훈), KAIST:
*Tree decompositions of graphs without large bipartite holes* - Hong Liu (刘鸿), University of Warwick:
*Recent advance in Ramsey-Turán theory* - Abhishek Methuku, IBS Discrete Mathematics Group:
*Bipartite Turán problems for ordered graphs* - Péter Pál Pach, Budapest University of Technology and Economics:
*On some applications of graph theory to number theoretic problems*

## 2019-2 IBS One-Day Conference on Extremal Graph Theory

## Invited Speakers

- Jaehoon Kim (김재훈), KAIST
- Hong Liu (刘鸿), University of Warwick
- Abhishek Methuku, IBS Discrete Mathematics Group
- Péter Pál Pach, Budapest University of Technology and Economics

## Schedule

### August 12, Monday

11:00am-12:00pm **Jaehoon Kim (김재훈)**: Tree decompositions of graphs without large bipartite holes

12:00pm-1:30pm Lunch

1:30pm-2:30pm **Abhishek Methuku**: Bipartite Turán problems for ordered graphs

3:00pm-4:00pm **Péter Pál Pach**: On some applications of graph theory to number theoretic problems

4:30pm-5:30pm **Hong Liu**: Recent advance in Ramsey-Turán theory

6:00pm-8:00pm Banquet

## Abstract

#### Jaehoon Kim (김재훈), Tree decompositions of graphs without large bipartite holes

A recent result of Condon, Kim, Kühn and Osthus implies that for any $r\geq (\frac{1}{2}+o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this talk, we prove that a similar result holds for an almost $\alpha n$-regular graph $G$ with any $\alpha>0$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. This is joint work with Younjin Kim and Hong Liu.

#### Abhishek Methuku, Bipartite Turán problems for ordered graphs

A zero-one matrix $M$ contains a zero-one matrix $A$ if one can delete rows and columns of $M$, and turn 1-entries into 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted by $ex(n,A)$, is the maximum number of $1$-entries in an $n\times n$ sized matrix $M$ that does not contain $A$.

A matrix $A$ is column-$t$-partite (or row-$t$-partite), if it can be cut along the columns (or rows) into $t$ submatrices such that every row (or column) of these submatrices contains at most one $1$-entry. We prove that if $A$ is column-$t$-partite, then $\operatorname{ex}(n,A)<n^{2-\frac{1}{t}+\frac{1}{2t^{2}}+o(1)}$, and if $A$ is both column- and row-$t$-partite, then $\operatorname{ex}(n,A)<n^{2-\frac{1}{t}+o(1)}$, and this bound is close to being optimal. Our proof introduces a new density-increment-type argument which is combined with the celebrated dependent random choice method.

Results about the extremal numbers of zero-one matrices translate into results about the Turán numbers of bipartite ordered graphs. In particular, a zero-one matrix with at most $t$ 1-entries in each row corresponds to an ordered graph with maximum degree $t$ in one of its vertex classes. The aim of this talk is to establish general results about the extremal numbers of ordered graphs. Our results are partially motivated by a well known result of Füredi (1991) and Alon, Krivelevich, Sudakov (2003) stating that if $H$ is a bipartite graph with maximum degree $t$ in one of the vertex classes, then $\operatorname{ex}(n,H)=O(n^{2-\frac{1}{t}})$. This is joint work with Tomon.

#### Péter Pál Pach, On some applications of graph theory to number theoretic problems

How large can a set of integers be, if the equation $a_1a_2\dots a_h=b_1b_2\dots b_h$ has no solution consisting of distinct elements of this set? How large can a set of integers be, if none of them divides the product of $h$ others? How small can a multiplicative basis for $\{1, 2, \dots, n\}$ be? The first question is about a generalization of the multiplicative Sidon sets, the second one is of the primitive sets, while the third one is the multiplicative version of the well-studied analogue problem for additive bases.

In answering the above mentioned questions graph theory plays an important role and in most of our results not only the asymptotics are found, but very tight bounds are obtained for the error terms, as well. We will also discuss the counting version of these questions.

#### Hong Liu, Recent advance in Ramsey-Turán theory

We will talk about Ramsey-Turán theory and some recent development. More specifically, we will talk about graphs with $\alpha_r(G)=o(n)$, where $\alpha_r(G)$ is the largest size subset with no $K_r$. Two major open problems in this area from the 80s ask: (1) whether Bollobas-Erdos graph can be generalised to densities other than $1/2$; (2) whether the asymptotic extremal structure for $\alpha_r(G)$ resembles that of $\alpha_2(G)$. We settle the first conjecture by constructing Bollobas-Erdos type graph with density $a$ for arbitrary rational number $a\le 1/2$; and refute the second conjecture by witnessing asymptotic extremal structures that are drastically different from the $\alpha_2(G)$ problem via a ”Mobius product” construction.

Joint work with Christian Reiher, Maryam Sharifzadeh, and Katherine Staden.