On July 4, 2023, Tuan Tran from the University of Science and Technology of China gave a talk on a Sauer-Shelah-type lemma in the study of the maximal pattern entropy of a theoretical dynamical system and its connection to a recent result in communication complexity at the Discrete Math Seminar. The title of his talk was “Complexity of null dynamical systems.”

## Tuan Tran, Complexity of null dynamical systems

A *theoretical dynamical system* is a pair (X,T) where X is a compact metric space and T is a self homeomorphism of X. The *topological entropy* of a theoretical dynamical system (X,T), first introduced in 1965 by Adler, Konheim and McAndrew, is a nonnegative real number that measures the complexity of the system. Systems with positive entropy are random in certain sense, and systems with zero entropy are said to be deterministic. To distinguish between deterministic systems, Huang and Ye (2009) introduced the concept of maximal pattern entropy of a theoretical dynamical system. At the heart of their argument is a Sauer-Shelah-type lemma. We will discuss this lemma and its surprising connection to a recent breakthrough in communication complexity.

Joint work with Guorong Gao, Jie Ma, and Mingyuan Rong.

## Tuan Tran gave a talk on the volume of the intersection of two balls in a metric space with applications at the Discrete Math Seminar

On December 14, 2021, Tuan Tran from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on sufficient conditions for balls in a metric space to have small intersection and their applications. The title of his talk was “Exponential decay of intersection volume with applications on list-decodability and sphere-covering bounds“.

## Tuan Tran, Exponential decay of intersection volume with applications on list-decodability and sphere-covering bounds

We give some natural sufficient conditions for balls in a metric space to have small intersection. Roughly speaking, this happens when the metric space is (i) expanding and (ii) well-spread, and (iii) certain random variable on the boundary of a ball has a small tail. As applications, we show that the volume of intersection of balls in Hamming space and symmetric groups decays exponentially as their centers drift apart. To verify condition (iii), we prove some deviation inequalities `on the slice’ for functions with Lipschitz conditions.

We then use these estimates on intersection volumes to

- obtain a sharp lower bound on list-decodability of random q-ary codes, confirming a conjecture of Li and Wootters [IEEE Trans. Inf. Theory 2021]; and
- improve sphere-covering bound from the 70s on constant weight codes by a factor linear in dimension, resolving a problem raised by Jiang and Vardy [IEEE Trans. Inf. Theory 2004].

Our probabilistic point of view also offers a unified framework to obtain improvements on other sphere-covering bounds, giving conceptually simple and calculation-free proofs for q-ary codes, permutation codes, and spherical codes.

This is joint work with Jaehoon Kim and Hong Liu.

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

## Tuan Tran gave a talk on the minimum saturated families of sets at the Discrete Math Seminar

On January 26, 2021, Tuan Tran from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on a result towards the conjecture of Erdős and Kleitman on the size of an s-saturated family of subsets of {1,2,…,n}. The title of his talk was “Minimum saturated families of sets“.

## Tuan Tran, Minimum saturated families of sets

A family $\mathcal F$ of subsets of [n] is called s-saturated if it contains no s pairwise disjoint sets, and moreover, no set can be added to $\mathcal F$ while preserving this property. More than 40 years ago, Erdős and Kleitman conjectured that an s-saturated family of subsets of [n] has size at least $(1 – 2^{-(s-1)})2^n$. It is a simple exercise to show that every s-saturated family has size at least $2^{n-1}$, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of $(1/2 + \varepsilon)2^n$, for some fixed $\varepsilon > 0$, seems difficult. We prove such a result, showing that every s-saturated family of subsets of [n] has size at least $(1 – 1/s)2^n$. In this talk, I will present two short proofs. This is joint work with M. Bucic, S. Letzter and B. Sudakov.

## 2020 Combinatorics Workshop (2020 조합론 학술대회) was held on August 24 online

On August 24, Monday, the 2020 Combinatorics Workshop (2020 조합론 학술대회) was held online due to the COVID-19 pandemic. This local workshop series began in 2004 and has been continued to be one of the biggest annual gathering of people in combinatorics located in Korea. Due to the COVID-19 pandemic, it has been reduced to a one-day online conference on Zoom. It was hosted by Kyung Hee University and IBS Discrete Mathematics Group.

The workshop website: https://cw2020.combinatorics.kr

## There were 5 invited speakers.

**Sejeong Bang (방세정)**, Yeungnam University,*Geometric distance-regular graphs***Ringi Kim (김린기)**, KAIST,*Decomposing planar graphs into graphs with degree restrictions***Sangwook Kim (김상욱)**, Chonnam National University,*Combinatorics of lattice path matroid polytopes***Jinyoung Park (박진영)**, Institute for Advanced Study,*Tuza’s Conjecture for random graphs***Jongyook Park (박종육)**, Kyungpook National University,*On distance-regular graphs with induced subgraphs $K_{r,t}$*

## There were 4 contributed talks.

**Byung-Hak Hwang (황병학)**, Seoul National University,*Acyclic orientation polynomials***Jaeseong Oh (오재성)**, Seoul National University,*On linearization coefficients of q-Laguerre polynomials***Jun Seok Oh (오준석)**, Incheon National University,*An inverse Erdős-Ginzburg-Ziv theorem for finite groups***Tuan Tran**, IBS Discrete Mathematics Group,*The singularity of random combinatorial matrices*

## Tuan Tran gave a talk on the anti-concentration phenomena at the Discrete Math Seminar

On August 18, 2020, Tuan Tran from IBS Discrete Mathematics Group gave a talk on the anti-concentration phenomena and its consequences to the random matrix theory. The title of his talk is “Anti-concentration phenomena”.

## Welcome Ben Lund and Tuan Tran, new research fellows in the IBS Discrete Mathematics Group

The IBS discrete mathematics group welcomes Dr. **Ben Lund** and Dr. **Tuan Tran**, new research fellows at the IBS discrete mathematics group from August 1, 2020.

**Ben Lund** received his Ph.D. from the Department of Mathematics at Rutgers University in 2017 under the supervision of Prof. Shubhangi Saraf. Before joining the IBS, he was a postdoc at Princeton University and a postdoc at the University of Georgia.

**Tuan Tran** received his Ph.D. from the Department of Mathematics at the Freie Universität Berlin in 2015 under the supervision of Prof. Tibor Szabó. Before joining the IBS, he was a lecturer at Hanoi University of Science and Technology, a postdoc at ETH Zürich, and a postdoc at Czech Academy of Sciences. He won the IBS Young Scientist Fellowship.