Invited Speakers

---

Gwenaël Joret (ULB)
Eun Jung Kim (LAMSADE, Paris-Dauphine)
Matthew Kwan (IST Austria)
Shoham Letzter (University College London)
Rose McCarty (Princeton)
Dhruv Mubayi (UI Chicago)
Oleg Pikhurko (Warwick)
Luke Postle (Waterloo)
Martin Tancer (Charles University)

European Prize Talks

---

Johannes Carmesin (University of Birmingham)
Felix Joos (Heidelberg University)

Titles, Abstracts, and Slides

---

Gwenaël Joret (ULB)
chi-boundedness for posets (slides)
Abstract: A class of graphs is chi-bounded if the graphs in the class have chromatic number bounded from above by a function of their clique number. Moving to the realm of posets, chromatic number naturally corresponds to dimension, while cliques correspond to the so-called "standard examples". This leads to the following notion of dim-boundedness: A family of posets is dim-bounded if the posets have dimension bounded from above by a function of the largest size of standard examples they contain.

There is a wealth of results about $\chi$-boundedness for graphs, and many graph classes of interest are known to be $\chi$-bounded. On the other hand, for posets very little was known prior to 2022, even though these questions have been studied since the early 1980s. In this talk, I will present some very recent progress in this area, including a proof that posets with cover graphs of bounded treewidth are dim-bounded. The proof relies on Colcombet’s deterministic version of Simon’s factorization theorem, which is a fundamental tool in formal language and automata theory, and which we believe deserves a wider recognition in structural and algorithmic graph theory.

Joint work with Piotr Micek, Michał Pilipczuk, and Bartosz Walczak.

Eun Jung Kim (LAMSADE, Paris-Dauphine)
Twin-width and Its Implications (slides)
Abstract: Twin-width is a graph parameter introduced in 2020 by Bonnet, Kim, Thomassé, Watrigant, which quickly gained much traction since then. The contraction of two vertices u,v, in a graph G is an operation that identifies u and v into a new vertex z, and updates the adjacency relations between z and x of V-{u,v} into (black) edge, non-edge and red edge: each reflects the state that {u,v} and {x} are homogeneously adjacent/homogeneously non-adjacent/ not homogeneous. Given a graph G, a repeated application of contraction operations results in a sequence of ‘trigraph’ starting with G and ending in a single-vertex graph, which we call a contraction sequence of G. Twin-width of a contraction sequence is the maximum number of red edges incident with a vertex in a trigraph over all trigraphs that appears along the contraction sequence, and twin-width of G is the minimum twin-width of a contraction sequences of G.

Many well-studied graph classes like bounded tree-width and rank-width graphs, unit interval graphs, strict hereditary classes of permutations, minor-closed graph classes are known to have bounded twin-width, thus the list of bounded twin-width classes include both spare and dense graph classes. Thanks to its rich structure, twin-width provides a new perspective on the tractability of many computational problems on seemingly different graph classes as well as a broad explanation of nice combinatorial properties such as small growth phenomenon and chi-boundedness. Moreover, natural variants of twin-width give an alternative characterization of well-known graph parameters such as bounded rank-width, tree-width and so on.

In this talk, we give an overview of twin-width and its various implications.

Matthew Kwan (IST Austria)
Edge-statistics in Ramsey graphs
Abstract: An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log n (i.e., if it has near-optimal Ramsey behavior). In this talk, we discuss a recent result on edge-statistics in Ramsey graphs, giving very precise control of the distribution of the number of edges in a random vertex subset of a C-Ramsey graph. The proof involves an unusually wide range of different tools and ideas, from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics, and low-rank approximation. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay. Joint work with Ashwin Sah, Lisa Sauermann and Mehtaab Sawhney.

Shoham Letzter (University College London)
Turán densities of tight cycles (slides)
Abstract: The Turán density of an r-uniform hypergraph H is the limit, as n tends to infinity, of the maximum number of edges in an n-vertex r-uniform hypergraph that does not contain a copy of H. We determine the Turán density of the 3-uniform tight cycle of length k, for every large enough k which is not divisible by 3. This is the first example of a hypergraph whose Turán density is proven to be realised by an `iterated blow-up'. A key component of our proof is a 3-uniform analogue of the statement: a graph is bipartite if and only if it does not contain an odd cycle. This is joint work with Nina Kamčev and Alexey Pokrovskiy.

Rose McCarty (Princeton)
δ-boundedness (slides)
Abstract: There are many classical constructions of graphs that have arbitrarily large minimum degree, but no big bicliques. A class of graphs is "δ-bounded" if, essentially, it avoids all such constructions. We give an overview of this area, focusing on parallels with χ-boundedness.

One theorem we will discuss in more detail says that any graph whose minimum degree is exponential in t^3(log c) contains either: 1) a K_t,t-subgraph, or 2) an induced subgraph with minimum degree at least c and no 4-cycles. This is joint work with Xiying Du, António Girão, Zach Hunter, and Alex Scott.

Dhruv Mubayi (UI Chicago)
Randomness and Determinism in Ramsey Theory
Abstract: For many decades randomness proved to be the central paradigm in Ramsey theory. Recent results suggest, however, that optimal constructions in the field may involve a subtle blend of randomness and determinism. We will illustrate this by surveying many recent results, mainly about graph and hypergraph Ramsey numbers.

Oleg Pikhurko (Warwick)
Measurable Combinatorics (slides)
Abstract: We give an introduction, aimed at non-experts, to measurable combinatorics that studies definable graphs on topological or measure spaces (for example, an interval of reals) and looks for constructive assignments satisfying some local combinatorial constraints (for example, a proper vertex colouring). This is an emerging field on the borderline between combinatorics and descriptive set theory with deep connections to many other areas. The aim of this talk is to advertise this field to a wider research community.

Luke Postle (Waterloo)
Hypergraph Matchings Avoiding Forbidden Submatchings
Abstract: We overview a general theory for finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of forbidden submatchings (which we view as a hypergraph H where V(H)=E(G)). In particular, we have a new common generalization of the classical theorems of Pippenger (for finding an almost perfect matching of G) and Ajtai, Komlos, Pintz, Spencer, and Szemeredi (for finding an independent set in a girth five hypergraph H) into this unified framework. More generally, we proved coloring and list coloring versions, and also generalized this further to when H is a hypergraph with small codegrees. We also discuss applications to various areas of high girth combinatorics. This is joint work with Michelle Delcourt.

Martin Tancer (Charles University)
Combinatorics, Topology & Computing (slides)
Abstract: In this talk, my aim will be to describe and explain various types of interactions among Combinatorics, Topology and Computing (mostly those that I have met in my own work). They include understanding to combinatorial and computational complexity of various problems in topology as well as using combinatorial or computational tools in topology or topological tools in combinatorics. A particular focus will be given to higher-dimensional generalization of graph planarity called embeddability.

Johannes Carmesin (University of Birmingham)
Angry theorems and decompositions of 3-connected graphs (slides)
Abstract: We offer a new structural basis for the theory of 3-connected graphs, providing a unique decomposition of every such graph into parts that are either quasi 4-connected, wheels, or thickened K_{3,m}’s. Our construction is explicit, canonical, and has the following applications: we obtain a new theorem characterising all Cayley graphs as either essentially 4-connected, cycles, or complete graphs on at most four vertices, and we provide an automatic proof of Tutte’s wheel theorem, as well as follow-up works including new FPT-algorithms. .

Felix Joos (Heidelberg University)
Random graph processes
Abstract: In this talk I survey some results regarding the F-free and F-removal process as well as other random greedy algorithms. This includes recent results on conflict-free hypergraph matchings. .