One-Day Meeting in Combinatorics

One-Day Meeting in Combinatorics
Mathematical Institute
University of Oxford

Tuesday 27 May 2025

A One-Day Meeting in Combinatorics will be held in the Mathematical Institute, University of Oxford on Tuesday 27 May 2025. The schedule can be found below.

Schedule

10.30 am                      Coffee

11.00 am                      Yuval Wigderson (ETH Zurich)
                                     The approximate structure of triangle-free graphs

11.55 am                      Liana Yepremyan (Emory)
                                     On random Cayley graphs and their generalizations

12.50 pm                      Lunch

2.15 pm                        Dan Kráľ (Leipzig University and MPI-MiS)
                                     Matroid depth parameters - structure and algorithms

3.10 pm                        Marthe Bonamy (Bordeaux)
                                     Using asymptotic dimension for distributed computing

4.05 pm                        Tea

4.30 pm                        Agelos Georgakopoulos (Warwick)
                                     An update on Coarse Graph Theory

Anyone interested is welcome to attend, and no registration is required. Some funds may be available to contribute to the expenses of research students who wish to attend. For any inquiries, please contact Alex Scott (scott at maths.ox.ac.uk). Support for this event by the London Mathematical Society and the British Combinatorial Committee is gratefully acknowledged.

Abstracts

Yuval Wigderson (ETH Zurich) The approximate structure of triangle-free graphs

Abstract: A natural way of constructing a dense triangle-free graph is to start with a triangle-free graph G₀ of bounded size, blow it up, and then delete some edges. Many of the natural triangle-free graphs we encounter, such as all bipartite graphs, can be obtained in this way.
Astonishingly, it turns out that this is essentially the *only* way of constructing dense triangle-free graphs. More precisely, for every ε>0, there exists some M(ε) such that every triangle-free graph G is ε-close to a blowup of a triangle-free graph G₀ on M(ε) vertices. In other words, if we are willing to tolerate some small error, then every triangle-free graph is of the form described above. Moreover, if we impose some additional condition on G, such as sufficiently high minimum degree, then this approximate structure can be made exact.
Unfortunately, such results are of limited applicability, because the known bounds on M(ε) are enormous, and it is moreover known that super-exponential bounds are necessary in general. In this talk, I will discuss this problem, and describe several settings in which we can prove much stronger bounds.
Based on joint work with Lior Gishboliner and Eoin Hurley.

Liana Yepremyan (Emory) On random Cayley graphs and their generalizations

Abstract: Various random graphs models satisfy that each edge appears independently of all other edges but those in a bounded degree graph. Examples include Erdős-Rényi random graphs, random Cayley graphs, random Latin square graphs, and recently introduced random entangled graphs. We begin the systematic study of such random graphs under a weak independence hypothesis, focusing on the clique number. We prove that for 01/p N and at most O(log N loglog N). The lower bound is tight for the Erdős-Rényi random graph, and the upper bound is tight for random Cayley graphs in finite vector spaces over a fixed finite field. Using the trace method and some intricate counting, in case when the dependency graph is symmetric, we also obtain an upper bound on the second largest eigenvalue of these random graphs. Using that, several properties of these graphs are established, such as Hamiltonicity etc.
Based on joint works with David Conlon, Jacob Fox and Huy Tuan Pham.

Dan Kráľ (Leipzig University and MPI-MiS) Matroid depth parameters - structure and algorithms

Abstract: Depth and width parameters of graphs, e.g., tree-width, path-width and tree-depth, play a crucial role in algorithmic and structural graph theory. These notions are of fundamental importance in the theory of graph minors, fixed parameter complexity and combinatorial sparsity. Likewise, matroid depth and width parameters play a crucial role in algorithmic and structural problems concerning matroids.
In this talk, we will survey structural and algorithmic results concerning width and depth parameters of matroids. We will view matroids as purely combinatorial objects and discuss their structural properties related to depth and width decompositions. As an algorithmic application, we will present matroid based algorithms that can uncover a hidden Dantzig-Wolfe-like structure of instances of integer programs (if such structure is present).
The most recent results presented in the talk are based on joint work with Marcin Briański, Martin Koutecký, Ander Lamaison, Kristýna Pekárková and Felix Schröder.

Marthe Bonamy (Bordeaux) Using asymptotic dimension for distributed computing

Abstract: What can be computed locally? We focus on the problem of Minimum Dominating Set in the LOCAL model of distributed computing. After a gentle introduction to the model and an even gentler introduction to asymptotic dimension, we explain how to use asymptotic dimension to turn global bounds into local ones, and show there is a simple constant-round algorithm that computes a 50-approximation for Minimum Dominating Set in H-minor-free graphs for any H of pathwidth 2. Until then, though fast and approximate distributed algorithms for such problems were already known for H-minor-free graphs, all of them had an approximation ratio depending on the size of H.

Agelos Georgakopoulos (Warwick) An update on Coarse Graph Theory

Abstract: Coarse graph theory is an emerging area that combines ideas from graph theory and coarse geometry. I will start by giving an overview of the topic for those new to it, and then present more recent results and questions. Based on joint works with P. Papasoglu and with S. Albrechtsen & M. Distel.