Programme

Horaire

Cours

Introduction to coarse graph theory
Tara Abrishami

Coarse graph theory is a recent area of study which aims to bring ideas from geometric group theory to graph theory in order to study the large-scale geometry of graphs. The core idea is to identify properties of graphs that persist even when we “zoom out” and view a “coarsened” version of the graph.

One goal of coarse graph theory is to find "coarse" analogs of classical results. For example, Menger's theorem states that between two vertex subsets \(S\) and \(T\) of a graph, either there are \(k\) vertex-disjoint \(S-T\) paths or there is a set \(X\) of size at most \(k-1\) that separates \(S\) and \(T\). The "Coarse Menger Conjecture" asks for a similar dichotomy but for paths that are far apart instead of simply vertex-disjoint. Despite being an intuitive conjecture, Coarse Menger was recently shown to be false, even in approximate forms. On the other hand, there are numerous positive results in coarse graph theory, and ideas from coarse graph theory have connections to different topics like group theory and algorithms. This mini-course will focus on explaining the core concepts and tools from coarse graph theory, such as quasi-isometry and asymptotic dimension. We will discuss several positive results, and we will also discuss the opportunity for new ideas after the recent discovery of counterexamples to several main conjectures.

Covering random trees and local convergence
Serte Donderwinkel

This mini-course presents a new viewpoint on the geometry of random trees by exploring their covering numbers through the framework of local convergence. Given a graph \(G\) and a fixed radius \(r \in \mathbb{N}\), the \(r\)-covering number is the size of the smallest set of vertices in a graph that together are within distance \(r\) from all other vertices. This notion is connected to applications ranging from efficient information dissemination in network models to disaster mitigation and resource allocation in spatial systems.

In this course, we focus on large random trees and uncover how their \(r\)-covering numbers can be accurately predicted from their local weak limits, which are random objects that capture the asymptotic distribution of local neighborhoods in the tree. Along the way, participants will be introduced to the theory of local convergence, a powerful and rapidly evolving tool in modern probability and combinatorics.

The content of the course is based on joint work in progress with Louigi Addario-Berry, Caelan Atamanchuk, Simon Briend and Elaine Herrera.

The Kahn Kalai conjectures
Quentin Dubroff

Given a finite set \(X\) and an increasing family \(\mathcal{A} \subset 2^X\), the threshold of \(\mathcal{A}\), denoted \(p_c(\mathcal{A})\), is the unique \(p\) for which \(\mathbb{P}(X_p \in \mathcal{A}) = 1/2\), where \(X_p\) is the binomial random subset of \(X\) obtained by keeping elements with probability \(p\). The study of thresholds has recently been revolutionized, with major progress on the sunflower conjecture leading to Park and Pham's proof of the Kahn-Kalai conjecture. The Kahn-Kalai conjecture furnishes estimates on thresholds (dubbed expectation thresholds) that are strikingly precise and often trivial to compute: given an increasing family \(\mathcal{A}\), there are parameters \(q_f(\mathcal{A})\) and \(q(\mathcal{A})\) such that \[q(\mathcal{A}) \leq q_f(\mathcal{A}) \leq p_c(\mathcal{A}) < K q(\mathcal{A}) \log \ell(\mathcal{A}),\] where \(K\) is an absolute constant and \(\ell(\mathcal{A})\) is the size of the largest minimal element of \(\mathcal{A}\). Thus if one understands \(q(\mathcal{A})\), which we do for many families \(\mathcal{A}\) of interest, then one understands \(p_c(\mathcal{A})\) up to a \(\log\) factor.

This course will survey the recent developments on the Kahn-Kalai conjecture, and present several of its as-yet-unsolved variants.

Advances in Ramsey theory
Simon Griffiths

For integers \(s,t \ge 1\), the Ramsey number \(R(s,t)\) is the smallest integer \(n\) such that if the edges of the complete graph \(K_n\) are coloured in either red or blue, either a monochromatic red subgraph of size \(s\) or a monochromatic blue subgraph of size \(t\) will appear. In 1935, Erdös and Szekeres proved that \(R(s,t) < {s+t-2 \choose s-1}< \infty\); in particular, this yields that the diagonal Ramsey number \(R(s,s)\) satisfies the bound \(R(s,s) \le {2s-2 \choose s-1} = 4^{s-\Theta(\log s)}\). As of 75 years later, the best known bound was \(R(s,s) \le 4^{s-\Theta(\log^2 s)}\).

In the last two years there have been a number of large and surprising advances in Ramsey Theory. There have been innovative new constructions which have improved lower bounds on Ramsey numbers, in both off-diagonal and near-diagonal cases. Moreover, after 80 years, there have also been exponential improvements to known upper bounds on diagonal Ramsey numbers, for two or more colours. (In particular, it is now known that \(R(s,s) \le 3.8^{s+o(s)}\).) This course will survey a number of the recent advances and new techniques that have been developed for the study of Ramsey numbers.

Clique numbers of random Cayley graphs
Liana Yepremyan

In this course we will cover some recent progress on the clique number of random Cayley graphs and related problems. We consider Cayley graphs in undirected setting. Given a group \(\Gamma\) and a symmetric generator set \(S\) of \(G\), the undirected Cayley graph \(\mathrm{Cay}(\Gamma,S)\) is the graph with vertex set \(G\) where two vertices \(x\) and \(y\) are joined by an edge if and only if \(xy^{-1} \in S\). For a constant \(C\), a graph on \(N\) vertices is called \(C\)-Ramsey if both its clique number and its independence number, that is, the clique number of its complement, are at most \(C\log{N}\). One of the first applications of the probabilistic method by Erdös says that almost all graphs on \(N\) vertices are 2-Ramsey. By an early result of Erdös and Szekeres, and more recently by a result of Campos, Griffiths, Morris, and Sahasrabudhe, we know there are no \((1/2+\varepsilon)\)-Ramsey graphs, for some absolute \(\varepsilon >0\).

As a way to construct explicit \(C\)-Ramsey graphs, Alon (1995) conjectured that there is an absolute constant \(C\) such that every finite group \(\Gamma\) has a \(C\)-Ramsey Cayley graph, that is, there exists some generator set \(S\) for the group \(\Gamma\) such that the clique number and the independence number of the Cayley graph \(Cay (\Gamma, S)\) is at most \(C\log{N}\) where \(|G|=N\). Recently, together with Conlon, Fox and Tuan Pham, we showed that there is an absolute constant \(C\) such that the uniform random Cayley graph on any group \(G\) with \(N\) elements has clique number at most \(C \log N \log \log N\) with high probability. This improves on an earlier bound of \(C \log^2 N\) of Alon (1995) and, for some groups such as \(\mathbb{F}_2^n\) is the best possible up to the constant. Our techniques have also led to some interesting results on additive and multiplicative dimensions of groups. The course will present these new results and the techniques behind them; time permitting, we will also discuss further generalizations of random Cayley graphs and some recent results on the clique and independence number of these graphs.