Join us online for our 4th Developments in Combinatorics online workshop. All information can be found here: https://www.ibs.re.kr/ecopro/development-in-combinatorics-4th-workshop-2024/
Summer school 2024
This year’s summer school again consists of two parts. All information, including lecture notes, recordings will be available on the course homepage: https://www.ibs.re.kr/ecopro/summer-2024/
Week 1: July 29 — August 2
Lecturer: Boris Bukh (CMU)
Title: Algebraic methods in combinatorics
Description: The aim of this lecture series is to introduce algebraic proof techinques in extremal combinatorics. Three main topics will be covered: polynomial interpolation, slice rank and algebraic geometry constructions. Depending on pacing and audience’s wishes, towards the end, we might discuss other recent topics of interest.
Week 2: August 5 — August 9
Lecturer: Tung Nguyen (Princeton)
Title: Recent work on the Erdős–Hajnal conjecture
Abstract: A conjecture of Erdős and Hajnal asserts that every graph with a forbidden induced subgraph contains a clique or independent set of polynomial size. We will discuss recent work on this conjecture (joint with Alex Scott and Paul Seymour, and partly with Matija Bucić), which includes the loglog improvement over the general bound of Erdős and Hajnal, Rödl’s theorem and the polynomial Rödl property, and the method of iterative sparsification with application to prime graphs and graphs of bounded VC-dimension.

Dongyeap Kang got Sangsan Prize for Young Mathematicians! Congratulations!
Our YSF Dongyeap Kang received 2023 the prestigious Sangsan Prize for Young Mathematicians (상산젊은수학자상) from the Korean Mathematical Society. This prize is for those with outstanding academic achievements in mathematics who are within 5 years of receiving their Ph.D. degree.




3rd Developments in Combinatorics Workshop
Will be held at Grand Hyatt Jeju from October 20 to 23, 2023. For more details, please see the workshop homepage: https://www.ibs.re.kr/ecopro/development-in-combinatorics-3rd-workshop-2023/



Summer school 2023 part 2 at SDU
Graph limits and flag algebras by Andrzej Grzesik.






Summer school 2023 part 1 at IBS
Hypergraph containers by Wojciech Samotij.



Summer school 2023 kicks off next week!
Our summer school will start on next Monday. For all information, please visit the course homepage: https://www.ibs.re.kr/ecopro/summer-2023/

Winter School “Statistical physics and combinatorics”
The 1st hybrid winter school Statistical physics and combinatorics will be held on February, 2023. This will be an in-person lecture series and streamed online.
- Lecture room: IBS, B332
- 09:30am, Monday – Friday, Feb 6 – 10, 2023
- Zoom: 346 934 4087, password: 202302
Program
This mini-course will be an introduction to how methods, ideas, and intuition from statistical physics can be used in extremal, probabilistic, and enumerative combinatorics. The course will begin with a brief introduction to the fundamentals of statistical physics: Gibbs measures, partition functions, phase transitions, correlation decay. We will then see how this perspective can be applied to combinatorial problems. Finally we will present several probabilistic methods in combinatorics based on statistical physics tools like the cluster expansion and correlation decay.
Organizers
- Hong Liu, IBS Extremal Combinatorics and Probability Group
- Bingyu Luan, Shandong University
- Guanghui Wang, Shandong University

Online workshop “Developments in Combinatorics”
The 2nd online workshop Developments in Combinatorics will be held on November 28 and 29, 2022.
- Zoom: 346 934 4087, password: 202209
Invited Speakers

Zdeněk Dvořák
Charles University

Lior Gishboliner
ETH Zürich

Andrzej Grzesik
Jagiellonian University

Jie Han
Beijing Institute of Technology

Dongyeap Kang
University of Birmingham

Imre Leader
University of Cambridge

Joonkyung Lee
Hanyang University

Alex Scott
University of Oxford

Chong Shangguan
Shandong University

Jozef Skokan
LSE
Program
Time in Korea | Nov 28 Monday | Nov 29 Tuesday |
---|---|---|
15:30-16:10 | Jie Han | Chong Shangguan |
16:10-16:50 | Joonkyung Lee | Zdeněk Dvořák |
16:50-17:30 | Lior Gishboliner | Andrzej Grzesik |
17:40-18:20 | Alex Scott | Imre Leader |
18:20-19:00 | Dongyeap Kang | Jozef Skokan |
Abstracts
Jie Han, H-factors in graphs with sublinear independence number
There has been a recent tread in finding spanning subgraphs in (host) graphs with sublinear independence number. In this talk we study the H-factors problem in such a setting. That is, given a graph H, what is the best possible minimum degree condition forcing an H-factor in a graph G with independence number o(|G|)? Joint work with Ming Chen, Guanghui Wang and Donglei Yang.
Joonkyung Lee, Extended commonality of paths and cycles via Schur convexity
A graph
We prove a graph homomorphism inequality that extends the commonality of paths and cycles.
Namely,
This answers a question of Sidorenko from 1989, who proved a slightly weaker result for even-length paths to prove the commonality of odd cycles.
Furthermore, it also settles a recent conjecture of Behague, Morrison, and Noel in a strong form, who asked if the inequality holds for graphons
Joint work with Jang Soo Kim.
Lior Gishboliner, Polynomial removal lemmas
The removal lemma is a cornerstone of extremal graph theory. It has many generalizations and extensions to other combinatorial structures, such as induced subgraphs, hypergraphs, digraphs and matrices. A general open question is to characterize the cases in which the removal lemma has polynomial bounds. I will survey the state of knowledge on this general problem and present some new results.
Based on joint works with A. Shapira and I. Tomon.
Alex Scott, Invertibility of digraphs and tournaments
For an oriented graph D and a set X of vertices of D, the inversion of X in D is the digraph obtained from D by reversing the orientations of all edges with both endpoints in X. The inversion number of D is the minimum number of inversions required to turn D into an acyclic digraph.
We answer several questions of Bang-Jensen, da Silva, and Havet: (1) We show that for each fixed k, it is possible to decide in quadratic time whether a tournament T has inversion number at most k. This exponent is optimal for all k. (2) Building on their work, we prove their conjecture that for every k the problem is NP-complete for digraphs. (3) We construct digraphs with inversion number equal to twice their cycle transversal number; and (4) we disprove their conjecture concerning the inversion number of so-called `dijoin’ digraphs.
Joint work with Emil Powierski, Michael Savery and Elizabeth Wilmer.
Dongyeap Kang, Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
We prove that for
This is joint work with Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.
Chong Shangguan, Some problems in extremal set theory
Abstract: Consider an
1. it is called
2. it is called
3. it is called
Let
Zdeněk Dvořák, On density of Z_3-flow-critical graphs
(joint work with Bojan Mohar)
Many important results on chromatic number of graphs drawn on surfaces have been obtained by studying k-critical graphs, i.e., minimal obstructions for (k-1)-colorability. The theory of critical graphs for the dual notion of nowhere-zero flows is much less developed. For an abelian group A, a graph G is said to be A-flow-critical if G does not admit a nowhere-zero A-flow, but for each edge e, the contraction G/e has a nowhere-zero A-flow. We give a bound on the density of Z_3-flow-critical graphs drawn on a fixed surface, generalizing the bound on the density of 4-critical graphs by Kostochka and Yancey.
Andrzej Grzesik, Maximizing cycles of a given length in oriented graphs
We consider a problem of determining the asymptotic behavior of the maximal number of directed cycles of a given length in oriented graphs. Settling a conjecture of Bartley and Day, we prove that for cycle lengths not divisible by 4 the maximum value is the same as in the random tournament, additionally providing a characterization of extremal examples. For the remaining cycle lengths we provide asymptotically tight bounds.
We also consider the same problem in the setting where an oriented cycle of a given length is forbidden. We prove the correct order of magnitude for all cycle lengths, as well as exact answers in some special cases, showing the variety of possible extremal structures.
Based on joint works with Daniel Král’, László M. Lovász, Jan Volec, and Justyna Jaworska, Bartłomiej Kielak, Tomasz Ślusarczyk.
Imre Leader, Euclidean Ramsey Theory
The famous conjecture of Erdos, Graham, Montgomery, Rothschild, Spencer and Straus is that a set is Ramsey if and only if it embeds in a sphere. Here as usual “Ramsey” means that for every k there is an n such that whenever we k-colour real n-dimensional space there is a copy of the set that is monochromatic. We propose a “rival” conjecture, that a set is Ramsey if and only if it embeds into a (finite) transitive set. We will discuss the motivation for this conjecture, as well as how it relates to the original conjecture.
(Joint work with Paul Russell and Mark Walters).
Jozef Skokan, Graphs with large minimum degree and no small odd cycles are three-colourable
Let
Letzter and Snyder showed that the homomorphism threshold of
Organizers
- Hong Liu, IBS Extremal Combinatorics and Probability Group
- Bingyu Luan, Shandong University
- Guanghui Wang, Shandong University

IBS Internal Workshop at Yeosu
“The 2022 DIMAG-ECOPRO Joint Internal Workshop” on October 31-November 3, 2022 was held at Yeosu.
