We ask the question, which oriented trees \(T\) must be contained as subgraphs in every finite directed graph of sufficiently large minimum out-degree. We formulate the following simple condition: all vertices in \(T\) of in-degree at least \(2\) must be on the same `level' in the natural height function of \(T\). We prove this condition to be necessary and conjecture it to be sufficient. In support of our conjecture, we prove it for a fairly general class of trees.
An essential tool in the latter proof, and a question interesting in its own right, is finding large subdivided in-stars in a directed graph of large minimum out-degree. We conjecture that any digraph and oriented graph of minimum out-degree at least \(k\ell\) and \(k\ell/2\), respectively, contains the \((k-1)\)-subdivision of the in-star with \(\ell\) leaves as a subgraph; this would be tight and generalizes a conjecture of Thomass\'e. We prove this for digraphs and \(k=2\) up to a factor of less than \(4\).

An \(\ell\)-uniform hypergraph is disperse if the number of edges induced by any set of \(\ell+1\) vertices is 0, 1, \(\ell\) or \(\ell+1\). We show that every disperse \(\ell\)-uniform hypergraph on \(n\) vertices contains a clique or independent set of size \(n^{\Omega_{\ell}(1)}\), answering a question of the first author and Tomon. To this end, we prove several structural properties of disperse hypergraphs.

We introduce the notion of temperate families as families \(\mathcal{F}\subset\mathcal{P}([n])\) where each \(A\in\mathcal{F}\) contains at most \(|A|\) elements of \(\mathcal{F}\) as a proper subset. More generally, we say that \(\mathcal{F}\subset\mathcal{P}([n])\) is \(t\)-temperate if each \(A\in\mathcal{F}\) contains at most \(\sum_{i=1}^t {\binom{|A|}{t}}\) elements of \(\mathcal{F}\) as a proper subset.
Given this notion, we study the following basic questions: What is the maximum size of a \(t\)-temperate family? What is the maximum size of an intersecting temperate family? What are the extremal examples?
Tackling all questions with probabilistic arguments, we fully answer the first one and classify all the maximum examples. We also answer the second question for odd \(n\) and conjecture the maximum size for even \(n\).
This talk is based on joint work with Pavel Turek.

Dependent randomized rounding is a useful approach in combinatorial optimization. We will survey several algorithmic aspects and applications of the technique.

For a given graph the bisection is a partition of its vertex set into two parts of (almost) equal sizes. The size of the bisection is the number of edges crossing between the two parts. The bisection width is the least possible size of all the bisections. Calculating the bisection width is known to be NP-complete. In this talk, we present an improvement on the local algorithm of Diaz, Serna and Wormald to construct a small bisection on regular graphs and an approach for analysis. Based on numerical results we also point out a possible simplification on our calculations. As a corollary, we deduce that random 5-regular graphs asymptotically almost surely admit an internal partition, which is a partition of the vertex set into two nonempty classes such that every vertex has at least half of its neighbors in its own class.

M. Skopenkov
King Abdullah University of Science and Technology
Quantum walks, introduced by Richard Feynman, are archetypical for studying quantum algorithms. A one-dimensional quantum walk exhibits a phase transition: the wave function oscillates inside some region but exponentially decreases outside. The large-time asymptotic behavior at the transition point is described by the Airy function, as proved by Sunada-Tate in 2012. For the first time, we prove a uniform asymptotic formula in the whole domain where the average velocity is less than the speed of light minus epsilon. We also prove a general theorem producing uniform asymptotic formulae of this kind from certain conformal mappings.
This is joint work with M. Drmota, F. Kuyanov, and A. Ustinov

A theorem due to Erd\H{o}s and Gallai fully answers the question of when one can realize a provided integer sequence as the degree sequence of a graph with an easy-to-check, necessary and sufficient condition. If one considers a random integer partition as the provided integer sequence, a theorem of Pittel's shows that with high probability a random partition is not the degree sequence of a graph. We consider the analogous question for 3-uniform hypergraphs and show that with high probability a random partition can indeed be realized as the degree sequence of a 3-uniform hypergraph. We will further consider the realizability question of whether one can realize three random integer partitions as the marginals of an associated three-dimensional contingency table. We will briefly discuss how this latter result resolves two conjectures of Pak and Panova regarding Kronecker coefficients.

An edge-weighted graph \(G\), possibly with loops, is said to be antiferromagnetic if it has nonnegative weights and at most one positive eigenvalue, counting multiplicities.
The number of graph homomorphisms from a graph \(H\) to an antiferromagnetic graph \(G\) generalises various important parameters in graph theory, including the number of independent sets and proper vertex-colourings, as well as their relaxations in statistical physics.
We obtain homomorphism inequalities for various graphs \(H\) and antiferromagnetic graphs \(G\) of the form
\(\lvert\operatorname{Hom}(H,G)\rvert^2 \leq \lvert\operatorname{Hom}(H\times K_2,G)\rvert,\) where \(H\times K_2\) denotes the tensor product of \(H\) and \(K_2\).
Firstly, we show that the inequality holds for any \(H\) obtained by blowing up vertices of a bipartite graph into complete graphs and any antiferromagnetic \(G\). In particular, one can take \(H=K_{d+1}\), which already implies a new result for the Sah--Sawhney--Stoner--Zhao conjecture on the maximum number of \(d\)-regular graphs in antiferromagnetic graphs.
Secondly, the inequality also holds for \(G=K_q\) and those \(H\) obtained by blowing up vertices of a bipartite graph into complete multipartite graphs, paths or even cycles.
Both results can be seen as the first progress towards Zhao's conjecture on \(q\)-colourings, which states that the inequality holds for any \(H\) and \(G=K_q\), after his own work. Our method leverages on the emerging theory of Lorentzian polynomials due to Br\"and\'en and Huh and log-concavity of the list colourings of bipartite graphs, which may be of independent interest.
This is joint work with Joonkyung Lee and Jaeseong Oh.

The study of random subtrees of a tree goes back to the work of Jamison in the 1980s, who in particular considered the mean subtree order (the average number of vertices in a subtree). This talk gives an overview of results on the mean subtree order and related graph invariants of trees and arbitrary graphs, with a focus on recent developments as well as some natural problems that still remain open.

I will present a central limit theorem for pattern counts in random planar maps in the case of patterns with a simple boundary. The proof relies on a combination of analytic and combinatorial methods together with a moment method due to Gao and Wormald.
Joint work with M. Drmota and N. Wormald

The expected average length of a cycle in a random permutation of \(d\) elements is approximately \(d/\log d\). A permutation can be viewed as a cycle factor of the complete digraph (with loops). So we might wonder about the expected average cycle length in a random cycle factor of some other \(d\)-regular digraph. An intuitive conjecture is that (disjoint unions of) the complete digraph is the minimiser. We show this is true up to constant factors, by showing a lower bound of \(d/(4 \log d)\). The best previous bound due to Vishnoi was \(\sqrt{\log d}\). The proof is short and uses the language of entropy. The result also yields state of the art efficient algorithms for a number of problems, such as finding short tours of regular graphs.
Joint work with Micha Christoph, Nemanja Dragani´c, António Girão, Lukas Michel and Alp Müyesser.

[No abstract]

A graph is even-degenerate if one can iteratively remove a vertex of even degree at each step until at most one edge remaining. Recently, Janzer and Yip showed that the Erd\H{o}s--Renyi random graph \(G(n,1/2)\) is even-degenerate with high probability and asked whether an analogous result holds for any general \(G(n,p)\). In this paper, we answer this question in affirmation by proving that \(G(n,p)\) is even-degenerate with high probability for any constant \(p\in (0,1)\).

The Ramsey number for matchings in graphs was determined by Cockayne and Lorimer and later extended to hypergraphs by Alon, Frankl, and Lovász, who showed that every q-colouring of the complete r-uniform hypergraph on n vertices contains a monochromatic matching of size floor((n+q-1)/(r+q-1)).
In this talk I will present two extensions of this classical result. The first is a **defect version**, which asserts that every q-colouring of an *almost-complete* r-uniform hypergraph contains a monochromatic matching of comparable size to that in the complete case. The second is a **transference principle**, showing that a monochromatic matching of comparable size exists, with high probability, in any q-colouring of a *sparse, random* r-uniform hypergraph with sufficiently large constant average degree.
The proofs combine methods from extremal set theory with a variant of the weak hypergraph regularity lemma.
Joint work with Lior Gishboliner, Stefan Glock, and Amedeo Sgueglia.

The Prague dimension of a graph \(G\) is defined as the minimum number of complete graphs whose product contains \(G\) as an induced subgraph. Introduced in the 1970s by Nešetřil, Pultr, and Rödl motivated by the induced Ramsey theorem, determining the Prague dimension of a graph is a notoriously hard problem.
We show that for all \(\epsilon > 0\) and \(p\) such that \( n^{-1+\epsilon} \le p \le n^{-\epsilon}\), with high probability the Prague dimension of the binomial random graph \(G(n,p)\) is \(\Theta_{\epsilon}(np)\). This improves on a recent result by Molnar, Rödl, Sales and Schacht. The main idea behind our proof is to upper bound the so-called set representation number of random graphs via the differential equation method.

What is the maximum number of points that can be selected from an \(n \times n\) square lattice such that no k+1 of them are in a line? This problem has been asked more than 100 years ago for k=2 and it remained wide open ever since. In this talk, we prove the precise answer is \(kn\), provided that \(k > C(n \log(n))^(1/2)\) for an absolute constant \(C\). The proof relies on carefully constructed bi-uniform random bipartite graphs and concentration inequalities. The case when k is small is discussed in the talk of B. Kovács.
Reference: Settling the no-(k+1)-in-line problem when k is not small, B Kovács, Z.L. Nagy, D. R. Szabó, ArXiv preprint, arxiv.org/abs/2502.00176

What is the maximum number of points, \(f_k(n)\), that can be selected from an \(n \times n\) square lattice such that no \(k+1\) of them are on the same line? This was asked more than 100 years ago for \(k=2\) and it has remained wide open ever since.
In this talk, we prove that \(f_3(n) \geq 1.97n-o(n)\) by building a random construction using modular hyperbolae, inspired by Hall, Jackson, Sudbery, and Wild. Moreover, we show that \(f_k(n) \geq (k-2)n-o(n)\) for all \(k\).
The talk is connected to that of Zoltán Lóránt Nagy, who discusses the case when \(k\) is not small.
Joint work with Zoltán Lóránt Nagy and Dávid R. Szabó.

I will present, for various positive reals \(\lambda\), a construction of bounded-degree \(n\)-vertex regular graphs whose adjacency matrices have second-largest eigenvalue precisely \(\lambda\) and for which the multiplicity of \(\lambda\) increases as \(\log\log n\). A major technical input in this construction is a distribution on \(k\)-factors of regular bipartite graphs which possesses good (spectral) concentration properties.
As an application, I will show that some angles \(\theta\) exhibit "intermediate" behavior in the storied problem of equiangular lines with a fixed angle: fixing \(\theta\) and growing the dimension \(n\), what is the maximum number of lines through the origin in \(n\) dimensions, each pair of which meets at the same angle \(\theta\)?

In the talk we will investigate the partition function of the random cluster model of graphs.  For a graph \(G\) it's defined as \(Z_G(q,w)=\sum_{A\subseteq E(G)}q^{k(A)}w^{|A|}\), where \(k(A)\) denotes the number of connected components of the graph \((V,A)\).
This model turns out to be a natural generalization of other well-known models (Ising and Potts) and the partition function is closely related to a central object in enumerative combinatorics (Tutte-polynomial).
In this talk we will see a result about the free-energy of the random cluster model on regular large-girth graphs when \(q\ge 2\). As such, we discuss some recent consequences of this result and technique (e.g. phase transition, weak limit, typical landscape).
Joint work with Márton Borbényi and Péter Csikvári.

For a graph \(G=(V,E)\) with \(v(G)\) vertices the partition function of the random cluster model is defined by
\(Z_G(q,w)=\sum_{A\subseteq E(G)}q^{k(A)}w^{|A|},\)
where \(k(A)\) denotes the number of connected components of the graph \((V,A)\). Furthermore, let \(g(G)\) denote the girth of the graph \(G\), that is, the length of the shortest cycle.
We show that if \((G_n)_n\) is a sequence of \(d\)-regular graphs such that the girth \(g(G_n)\to \infty\), then the limit
\(\lim_{n\to \infty} \frac{1}{v(G_n)}\ln Z_{G_n}(q,w)=\ln \Phi_{d,q,w}\)
exists if \(q\geq 2\) and \(w\geq 0\), and can be computed explicitly. We also show that the same result holds true if \(0 < q \leq 1-w\). To prove these results we introduce two new methods: the combinatorial approximation method that works for any large-girth graph sequence, and the sibling method that is useful for regular graphs.
This is a joint work with Ferenc Bencs and Márton Borbényi.

For a graph \(G=(V,E)\) the random cluster model with given parameters \(q > 0, w > 0\) is random subset of edges such that the probability of some \(A\subseteq E\) is \(\frac{1}{Z_G(q,w)}q^{k(A)}w^{|A|}\) where \(k(A)\) denotes the number of connected components of the graph \((V,A)\) and \(Z_G(q,w)\) denotes partition function of the model.
We show that if \(G_n\) is the random \(d\)-regular graph on \(n\) vertices, then the energy of the random cluster model, \(\frac{1}{n}\ln Z_{G_n}(q,w)\), converges to some value \(\ln \Phi_{d,q,w}\) a.a.s., if \(1\le q\leq 2\) and \(w > 0\).
In particular, we describe the free energy \(\ln \Phi_{d,q,w}\), together with the phase transition and the typical local landscape of the random cluster model. Our main tools are large deviation type inequalities, a connection between the random cluster model and the Ising model; and a method to make an "incorrectly" magnetized Ising model.
Ongoing work with Ferenc Bencs and Péter Csikvári.

More than 40 years ago, Galvin, Rival and Sands asked the following problem: given a graph \(G\) that does not contain the complete bipartite graph \(K_{s,s}\), and has a path on \(n\) vertices, how long of an induced path must \(G\) contain? In this talk, we give a short probabilistic proof that such graphs contains an induced path of length at least \((\log \log n)^{1−o(1)}\), which comes close to the best known upper bound \(O((\log \log n)^2)\).
Joint work with Hunter, Milojevic and Tomon

Let \(Q^d\) be the \(d\)-dimensional binary hypercube. We form a random subgraph \(Q^d_p\subseteq Q^d\) by retaining each edge of \(Q^d\) independently with probability \(p\).
We show that, for every constant \(\epsilon > 0\), there exists a constant \(C=C(\epsilon) > 0\) such that, if \(p\geq C/d\), then with high probability \(Q^d_p\) contains a cycle of length at least \((1-\epsilon)2^d\).
This confirms a long-standing folklore conjecture, stated in particular by Condon, Espuny D{\'i}az, Gir{\~a}o, K{\"u}hn, and Osthus.
This is joint work with Sahar Diskin, Joshua Erde, Mihyun Kang, Michael Krivelevich and Lyuben Lichev.

Let \(Q^d_p\) be the random subgraph of the \(d\)-dimensional binary hypercube obtained after bond-percolation with probability \(p\). Recently, Anastos, the speaker, Erde, Kang, Krivelevich and Lichev showed that for every constant \(\epsilon > 0\) there exists a constant \(c > 0\), such that if \(pd > c\) then typically \(Q^d_p\) contains a cycle of length at least \((1-\epsilon)2^d\). In this talk we present a strengthening of this result, showing that, under the same assumptions, typically \(Q^d_p\) contains cycles of all even lengths between \(4\) and \((1-\epsilon)2^d\).

A conjecture of Talagrand (2010) states that the so-called expectation and fractional expectation thresholds are always within at most some constant factor from each other. Expectation (resp. fractional expectation) threshold \(q\) (resp. \(q_f\)) for an increasing nontrivial class \(\mathcal{F}\subseteq 2^X\) allows to locate the threshold for \(\mathcal{F}\) within a logarithmic factor (these are important breakthrough results of Park and Pham (2022), resp. Frankston, Kahn, Narayanan and Park (2019)). I will give an overview about the problem and present what is known so far.

In 1991 B.Bollobás and A.Frieze found the threshold probability for \(G(n,p)\) to contain a spanning triangulation of a triangle, up to a logarithmic factor. In this talk, we establish the threshold for \(G(n,p)\) to contain a spanning triangulation of a polygon of arbitrary size \(k=k(n)\), up to a constant factor. The main tool is the so-called fragmentation process which was first used in the breakthrough work of J. Kahn, B. Narayanan and J.Park to determine the threshold for the square of Hamilton cycle. This method is directly connected with checking a strengthening of the spreadness property for the hypergraph of all copies of the spanning structure in question. Therefore, we additionally formulate a general lemma for checking this superspreadness condition in terms of relations between the number of edges and vertices of subgraphs, following the approach of A. Díaz and Y. Person.
Joint work with Maksim Zhukovskii.

When is it possible to detect a hidden random tree inside a random graph \(G(n,p)\)? More specifically, given a tree \(T\), we consider a random graph \(G_1(T)\) which is a union of a \(k\)-vertex tree \(T\), placed randomly into \(\{1, \ldots, n\}\), and a random graph \(G(n,p)\).
Firstly, let \(T\) be a 'typical' uniformly random labelled tree. We show that when \(k = \Omega(\log n)\) and \(p < (1+\epsilon) / n\) for a small positive constant \(\epsilon > 0\), \(G_1\) can be distinguished from \(G(n,p)\). This is surprising since at this density, \(G(n,p)\) contains random trees of size \(\Omega(n^{1/3})\). On the other hand, when \(p = C/n\) for a large constant \(C\) and \(k = o(\sqrt{n})\), \(G_1\) cannot be distinguished. Both bounds on \(k\) are optimal up to a constant factor.
We prove similar results for the case when \(T\) is a \(d\)-ary tree, and when \(T\) is an 'unknown' uniformly random tree (i.e. not exposed to the 'detector' prior to sampling \(G_1\)).
Joint work with Nicolas Broutin, Gabor Lugosi, Bruce Reed and Liana Yepremyan.

Temporal graphs are dynamic graphs where the edge set can change in each time step, while the vertex set stays the same. The temporal exploration problem (TEXP) asks for a walk in a given temporal graph, where at most one edge is traversed in each time step, and all vertices are visited. In this talk we will consider the temporal exploration problem (TEXP) on a model of random temporal graphs which are connected in each time step. It is known that there are n-vertex temporal graphs which are connected in each time step but require \(\Omega(n^2)\) steps to explore, our aim is to understand what happens against a random adversary.
In our model an adversary supplies a measure \(\mu\) supported on a set of (labelled) spanning trees of a static graph \(G\), and we obtain a (random) temporal graph by sampling a spanning tree from \(\mu\) at each time step. We show that, for any pair \((μ, G)\), w.h.p. there is a schedule which explores the corresponding temporal graph in time \(O(\min\{ |E(G)|, n^{3/2}\})\). Furthermore we provide an example of pair \((\mu, G)\) which requires \(\Omega(n^{3/2})\) steps to explore in expectation.
This is joint work with Samuel Baguley, Andreas Gobel, Nicolas Klodt, George Skretas, and Viktor Zamaraev

We study random temporal graphs, in the context of the Stochastic Block Model. Temporal graphs naturally model time-dependent propagation processes, for instance social interactions or infection processes. In these graphs, every edge has a unique timestamp, chosen uniformly at random, and the notion of connectivity is limited to sequences of edges with timestamps that increase over time. Our goal is to understand the asymptotic behavior of the temporal diameter of these graphs, especially in the subcritical regime where the average number of connections per node is of order \(c \log n\), with \(c < 1\). We analyze the first-order asymptotics for various aspects, including the length of the longest increasing paths starting at a typical vertex, as well as the size of the set of vertices reachable from a typical vertex via increasing paths.

We will talk about monotonicity and sprinkling properties of the model \(G(n,d)\) of random \(d\)-regular graphs on \(n\) vertices. Concerning monotonicity, we show that for \(n\) even, and a wide range of parameters \(d_1 \leq d_2\), there exists a coupling of \(G_1 \sim G(n,d_1)\) and \(G_2 \sim G(n,d_2)\) such that \(G_1 \subseteq G_2\) whp. This makes some progress towards a conjecture of Gao, Isaev, and McKay. Concerning sprinkling properties, we show for a wide range of parameter \(d\), that any event holding whp for the model of \(d\) random edge-disjoint perfect matching on a vertex set of size \(n\) even, also holds whp for \(G(n,d)\). This adds another tool for the study of random regular graphs, and makes some progress towards a conjecture of Isaev, McKay, Southwell and Zhukovskii.

Let \(t_{r-1}(n)\) denote the number of edges of the Turán graph with \(r - 1\) parts and \(n\) vertices. A conjecture of Győri states that if \(G\) is an \(n\)-vertex graph such that \(e(G) = t_{r-1}(n) + k\), then \(G\) has at least \((2 - o(1))k/r\) edge disjoint cliques of size \(r\). We outline the proof of this conjecture and give directions for future work.
Joint work with József Balogh.

In 1963, Anton Kotzig famously conjectured that \(K_{n}\), the complete graph of order \(n\), where \(n\) is even, can be decomposed into \(n-1\) perfect matchings such that every pair of these matchings forms a Hamilton cycle. The problem is still wide open and here we consider a variant of it for the binomial random graph \(G(n,p)\). In fact, our main result is a very precise answer for the following counting problem: given any \(k\) edge-disjoint perfect matchings \(M_1,\dots,M_k\) of \(K_n\), how many perfect matchings \(M^*\) in \(K_n\) have the property that \(M^*\cup M_i\) forms a Hamilton cycle for each \(i\in [k]\)?
Joint work with Stefan Glock.

Triangle-decompositions of large enough complete graphs are known to exist since the work of Steiner and Kirkman from the mid-1800s, barring trivial divisibility conditions. Two natural extensions have been studied recently, showing exciting progress with the new developments in absorption methodologies.
A celebrated conjecture of Nash-Williams asserts that any graph on n vertices with minimum degree at least \(3n/4\) admits a triangle-decomposition, assuming triangle-divisibility. This conjecture was reduced to the case of fractional decompositions by Barber, Kühn, Lo, and Osthus. In another direction, Erdős conjectured that for any g, sufficiently large complete graphs admit triangle-decompositions of girth at least g. Kwan, Sah, Sawhney, and Simkin proved this conjecture in their work on high girth Steiner triple systems.
Glock, Kühn, and Osthus unified these themes by conjecturing that every large enough triangle-divisible graph with minimum degree at least \(3n/4\) has a triangle-decomposition of girth at least g, for any fixed g. While earlier work relied on iterative absorption, we apply the recently developed refined absorption framework by Delcourt and Postle to show that the existence of fractional decompositions implies the existence of high-girth triangle-decompositions.
Joint work with Delcourt, Henderson and Postle.

The number of independent sets in regular bipartite expander graphs can be efficiently approximated by expressing it as the partition function of a suitable polymer model and truncating its cluster expansion. While this approach has been extensively used for graphs, surprisingly little is known about analogous questions in the context of hypergraphs.
In this talk, we apply this method to asymptotically determine the number of independent sets in regular k-partite k-uniform hypergraphs which satisfy natural expansion properties. The resulting formula depends only on the local structure of the hypergraph, making it computationally efficient. In particular, we provide a simple closed-form expression for linear hypergraphs.
This is joint work with Patrick Arras and Felix Joos.

In 1897 Dedekind posed the question of enumerating the number of antichains of the Boolean lattice. This was answered, almost a century later by Korshunov, and Sapozhenko simplified his proof by using what is now known as the graph container method. Sapozhenko asked whether the same approach can be applied to the product of chains of 3 elements. Counting the antichains of \(\{0,1,2\}^n\) was also asked independently by Noel, Scott and Sudakov, who obtained the asymptotics on the logarithmic scale. In our work, we provide sharp asymptotics for this number. As a tool, we prove a container type lemma to bound the number of expanding sets in a class of irregular graphs and isoperimetric estimates for generalizations of the Boolean lattice that may be of independent interest.
This is joint work with Matthew Jenssen and Jinyoung Park.

Given a graph \(G\), we form a random subgraph \(G_p\) by including each edge of \(G\) independently with probability \(p\). We prove an asymptotic expansion of the expected number of independent sets in random subgraphs of regular bipartite graphs satisfying certain vertex-isoperimetric properties, extending work of Kronenberg and Spinka on the percolated hypercube. Combining graph containers with the cluster expansion from statistical physics, we give an expansion of the partition function of the Ising model in certain range of the parameters. As a tool, we prove a refined container lemma for the Ising model that mildly improves recent bounds of Jenssen, Malekshahian, and Park for the hard-core model.
This is joint work with Anna Geisler, Mihyun Kang, and Michail Sarantis.

A growing random graph is constructed by successively sampling without replacement an element from the variable pool of virtual vertices and edges. At start of the process the pool contains \(N\) virtual vertices and no edges. Each time a vertex is sampled it becomes occupied, and the edges linking the vertex to previously occupied vertices are added to the pool of virtual elements. Each time a virtual edge is sampled, it becomes occupied and is included in the graph. We focus on the edge-counting at times when the graph composed of occupied elements has \(n \leq N\) vertices. Two different Poisson limits are identified for \(n\asymp N^{1/3}\) and \(N−n\asymp 1\). For the bulk of the process, when \(n\asymp N\), the normalised number of edges is shown to fluctuate about a nonrandom curve, with fluctuations being of the order of \(N^{3/2}\) and approximable by a Gaussian bridge.
This is a joint work with Michael Farber and Wajid Mannan.

In this talk, we discuss the evolution of majority dynamics with more than two states on a random graph. This is a process on a graph \(G=(V,E)\) where at round \(t\) the state of the vertices \(S(t) : V \to \{1,...,k\}\), for \(k > 2\), is the most popular state among the neighbours of each vertex during round \(t-1\), with ties broken randomly. We consider this process on a binomial random graph \(G(n,p)\). We show that for a random initial state \(S(0)\), where each vertex takes a state in \(\{1,...,k\}\) independently with some distribution that may not be the uniform, the process converges to unanimity, if \(np \gg n^{2/3}\).
This is joint work with Jordan Chellig.

A preferential attachment graph \(G_n^h\) is generated from a finite initial graph by adding new vertices one at a time. Each new vertex connects to \(h \geq 1\) already existing vertices, and these are chosen with probability proportional to their current degrees. We are particularly interested in the community structure of \(G_n^h\), which is expressed in terms of the so--called modularity. We prove that the modularity of \(G_n^h\) is with high probability upper bounded by a function that tends to \(0\) as \(h\) tends to infinity. This resolves the conjecture of Prokhorenkova, Prałat, and Raigorodskii from 2016.

We study a probabilistic version of the celebrated Conway's Army game. In this game the lower semiplane of an infinite chessboard may be filled with checker pieces. A celebrated result due to Conway (1961) shows that one cannot move a piece in a finite number of steps to a cell on row 5 (however, rows 1-4 are reachable).
In the version of this problem we are interested in, inspired by percolation theory, we assign pieces to all cells of the lower semiplane independently by flipping a coin with success probability \(p\) (a fixed constant between 0 and 1). We estimate \(D_{k}(p)\), the probability that one can reach a fixed cell on line \(k\), for \(k=1,2,3,4\).
We first give several rresults that provide rigorous lower and upper bounds on this probability. These results suggest the fact that the \(D_{k}(p)\) is an analytic function of \(p\). We complement these rigorous results by experimental ones, based on SAT solving.
We then show that our problem is related to a percolation game on hypergraphs as follows: we identify a percolation property on the 3-uniform hypergraph (with hyperedges corresponding to three consecutive cells of the 2-dimensional integer lattice) that yields probabilities \(D_k(p)\). We then study this property on a hypergraph analog of the Bethe lattice, and show that there is a critical probability for percolation on this hypergraph. This critical probability can be rigorously computed via an argument reminiscent of the computation of the extinction probability of Galton-Watson branching processes.
Joint work with Bogdan Dumitru and Mihai Prunescu

Consider a graph whose vertices are colored in one of two colors, say black or white. A white vertex is called integrated if it has at least as many black neighbors as white neighbors, and similarly for a black vertex. The coloring as a whole is integrated if every vertex is integrated. A classic exercise in graph theory, known as the Affirmative Action Problem, is to prove that every finite simple graph admits an integrated coloring. The solution can be neatly summarized with the one-liner: "maximize the number of balanced edges," that is, the edges that connect neighbors of different colors. However, not all integrated colorings advertise the maximum possible number of balanced edges.
In this talk, we characterize and enumerate the integrated colorings for complete graphs, bicliques, paths, and cycles. We also derive the distributions and extremal values for the mixing numbers (the number of balanced edges) across all integrated colorings over these families of graphs. For paths and cycles in particular, we use the quasi-powers framework for probability generating functions to prove a central limit theorem for the mixing number of random integrated colorings. Lastly, we obtain an upper bound for the number of integrated colorings over any fixed graph via the second-moment method. A specialized bound for the number of integrated colorings over a regular graph is also obtained.

We prove that for any \(k \geq 3\) for clause/variable ratios up to the Gibbs uniqueness threshold of the corresponding Galton-Watson tree, the number of satisfying assignments of random \(k\)-SAT formulas is given by the ‘replica symmetric solution’ predicted by physics methods [Monasson, Zecchina: Phys. Rev. Lett. 76 (1996)]. Furthermore, while the Gibbs uniqueness threshold is still not known precisely for any \(k \geq 3\), we derive new lower bounds on this threshold that improve over prior work [Montanari and Shah: SODA (2007)]. The improvement is significant particularly for small \(k\).

In 1983, Daykin and Erd\H{o}s asked the following problem: let \(\mathcal{F}\subset 2^{[n]}\) be a family of sets, and suppose that when you sample \(S,T\sim \mathcal{F}\) uniformly at random, the two sets are disjoint with probability \(p\); how large can \(|\mathcal{F}|\) be in terms of \(p,n\)? Alon and Frankl showed that if \(|\mathcal{F}| > 2^{(1/2+\delta)n}\), then \(p < 2^{-\Omega(\delta^2 n)}\), showing that one cannot do much better than taking \(\mathcal{F} = 2^X \cup 2^Y\) for two disjoint \(X,Y\) of size \(n/2\). However, some questions remained about the precise dependence on \(p\).
In joint work with Aleksa Milocevic, Benny Sudakov, and Istvan Tomon, we essentially fully resolve these questions. This is done via a short entropy argument, which furthermore gives a weak stability result.

Let \(\mathcal{A}\) and \(\mathcal{B}\) be set families of size \(m\) on the ground set \([n]\), such that at least \(m^2/2\) pairs \(A\in \mathcal{A}, B\in \mathcal{B}\) are disjoint. How large subfamilies \(\mathcal{A}'\subseteq \mathcal{A}, \mathcal{B}'\subseteq \mathcal{B}\) can one find with the property that all pairs \(A'\in \mathcal{A}', B'\in \mathcal{B}'\) are disjoint? This problem was posed by Singer and Sudan, as a special case of a conjecture of Lovett about low-rank sparse matrices. In my talk, I will show a short probabilistic argument which obtains optimal bounds for this problem. Further, I will talk about the the motivations for the problem, and connections to the fields of communication complexity (via the log-rank conjecture) and coding theory (via \(r\)-cover-free families).
This talk is based on joint work with Zach Hunter, Benny Sudakov and Istv\'an Tomon.

For natural numbers \(k\) and \(n\), a \(k\)-uniform intersecting family is a subfamily of \([n]^{(k)}\) such that any two elements have non-empty intersection. The Erd\H{o}s--Ko--Rado Theorem, which states that when \(n \geq 2k > 0\) any intersecting family \(\mathcal{F} \subset [n]^{(k)}\) satisfies \(|\mathcal{F}| \leq \binom{n-1}{k-1}\) is a seminal result in combinatorics that led to the study of intersecting set systems becoming a major focus of combinatorial research. We give two novel results on the theory of maximal intersecting families. The first determines a double exponential lower bound for the number of \(k\)-uniform MLCIFs, answering a question of Barber. The second is a generalisation of the Erd\H{o}s--Ko--Rado Theorem to weight functions, where we show that only \(k\) many of the \(k\)-uniform maximal left-compressed intersecting families (MLCIFs), precisely a very natural class of families we call the canonical ones, can be made optimal under an increasing weight function.

An ordered \(r\)-uniform matching of size \(n\) is a collection of \(n\) pairwise disjoint \(r\)-subsets of a linearly ordered set of \(rn\) vertices. For \(n=2\), such a matching is called an \(r\)-pattern, as it represents one of \(1/2{2r \choose r}\) ways two disjoint edges may intertwine. Given a set \(P\) of \(r\)-patterns, a \(P\)-clique is a matching with all pairs of edges belonging to \(P\).
We study a Ramsey type problem regarding the size of a largest \(P\)-clique in a random ordered \(r\)-uniform matching, that is, one selected uniformly from all such matchings on a fixed set \([rn]\). The starting point here were results of Dudek-Grytczuk-Ruciński and follow-up extensions of Anastos-Jin-Kwan-Sudakov and of Sauermann-Zakharov, which were mostly devoted to \(P\)-cliques induced by single patterns.
We investigate families \(P\) including more than one pattern and mainly focus on determining the a.s.s orders of magnitude of the mentioned \(P\)-cliques. In particular, we provide a solution of this problem for pairs of patterns, as well as families of all \(r\)-partite patterns. We also generalise these results towards more complex families, enjoying a Boolean-like symmetric structure.
(joint work with A. Dudek, J. Grytczuk and A. Ruciński)

Suppose that each number \(1,2,\cdots, N\) has one of \(n\) colours assigned. We show that if there are no monochromatic solutions to the equation \(x_1+x_2+x_3=y_1+y_2\), then \(N=O(\sqrt{n!})\), improving upon a result of Cwalina and Schoen. Further, a stronger bound of \(N=O(\sqrt{(n-k)!})\), where \(k\gg\frac{\log n}{\log\log n}\) is shown for colourings avoiding solutions to the equation \(x_1+x_2+\cdots+x_{12}=y_1+y_2+\cdots+y_{9}\).

Given a graph \(F\), a graph \(G\) is weakly \(F\)-saturated if all non-edges of \(G\) can be added in some order so that each new edge introduces a copy of \(F\). The weak saturation number \(wsat(n,F)\) is the minimum number of edges in a weakly \(F\)-saturated graph on n vertices. Bollobás initiated the study of weak saturation in 1968 to study percolation processes, which originated in biology and have applications in physics and computer science. It was shown by Alon that for each \(F\), there is a constant \(w_F\) such that \(wsat(n,F) = w_F n + o(n)\). We characterize all possible rational values of \(w_F\), proving in particular that \(w_F\) can equal any rational number at least \(3/2\). The techniques involve a combination of random and deterministic constructions and structural methods.
Joint work with Xiaoyu He.

In this talk we introduce the statistic sum of weighted records swrec and show an explicit formula for the total number of swrec over set partitions of \([n]\) with exactly \(k\) blocks in terms of Stirling numbers of the second kind. In addition, we present an explicit formula and asymptotic estimate for the total number of swrec over set partitions of \([n]\) in terms of Bell numbers. For that we need to use generating functions.

Many combinatorial structures can be enumerated by a bivariate generating function involving a functional composition \(F(z,u)= G(u H(z)) M(z)\).
This allows us to analyze limit laws of many parameters of maps, graphs, trees, words, tilings, walks, permutations...
We illustrate in this talk how the confluence of the singularities of \(G/H/M\) dictates phase transitions, leading to universal laws generalizing the Mittag-Leffler distributions, and stable distributions.
This unifies many classical results on phase transitions related to coalescence of singularities (like the Airy distribution popping up in the analysis of Banderier-Flajolet-Schaeffer-Soria), and also extends a recent work of Banderier-Kuba-Wagner-Wallner capturing the phase transitions for objects having a Gibbs weight.

In the Mallows distribution \(\operatorname{Mallows}(n, q)\), where \(q\in (0,1]\), introduced by Mallows in 1957, we sample a permutation \(\pi\) from all permutations on \(\{1,\dots,n\}\) according to the measure proportional to \(q^{\operatorname{inv}(\pi)}\), where \(\operatorname{inv}(\pi)\) is the number of inversions in the sampled permutation \(\pi\). One observes a kind of evolution of the \(\operatorname{Mallows}(n, q)\) distribution: from the uniform distribution (on all permutations on \(\{1,\dots,n\}\)) when \(q=1\), to a degenerate distribution concentrated on the identity permutation when \(q \rightarrow 0\).
In our talk we concentrate on the evolution of the number of arrangements of \(\ell\) consecutive values in the Mallows permutation, \(\ell=O(1)\). We continue the line of investigation initiated by Pinsky in 2022. In particular, we provide a precise asymptotic estimate for the number of arrangements in a permutation. We also show that for \(\ell \ge 3\), when the expected value of this number remains asymptotically constant, the distribution of the number of arrangements converges in distribution to a Poisson law. Furthermore, we present some results concerning the convergence of the number of arrangements to a normally distributed random variable.
This is joint work with John Sylvester.

Consider the following budget-constrained random graph process introduced by Frieze, Krivelevich and Michaeli. A player, called Builder, is presented with \(t\) distinct edges of \(K_n\) one by one, chosen uniformly at random. Builder may purchase at most \(b\) of these edges, and must (irrevocably) decide whether to purchase each edge as soon as it is offered.
Builder's goal is to construct a graph which satisfies a certain (monotone increasing) property.
In this talk, I will present the model in detail and discuss some state-of-the-art results for different properties, including new results for the containment of different \(F\)-factors or powers of Hamilton cycles.
This is based on joint work with Frederik Garbe, Tássio Naia and Zak Smith.

We consider the following budget-constrained random graph process introduced by Frieze, Krivelevich and Michaeli. A player, called Builder, is presented with t distinct edges of \(K_n\) one by one, chosen uniformly at random. Builder may purchase at most \(b\) of these edges, and must (irrevocably) decide whether to purchase each edge as soon as it is offered. Builder's goal is to construct a graph which satisfies a certain property; we investigate the properties of containing different clique covers.
We obtain optimal thresholds for the budget required at various times, for triangle- and \(K_4\)-covers, and show that the budget for \(K_5\)-covers cannot be improved at the hitting time. In particular, this behaviour differs from that for the corresponding clique factors, unlike the hitting times in the standard random graph process.
Based on joint work with Alberto Espuny Díaz, Frederik Garbe, and Tássio Naia.

Previous studies in the literature suggest that financial data, such as stock market prices, contain some intrinsic unpredictability, whose randomness can be compared to other random number generators.
We focus on ultra-high frequency financial data to evaluate the extent to which these data resemble random sequences. While related studies have only used serial correlation or entropy tests, we extend this analysis by applying standard batteries of randomness tests to sequences obtained by ultra high-frequency stock market data. Our purpose is to comprehensively analyze the randomness of these data using statistical tests that evaluate different aspects of randomness.
More specifically, we use most of the tests in the NIST Statistical Test Suite, the ENT battery and the TestU01 battery (using in particular the Rabbit and Alphabit sub-batteries) to prove that the degree of randomness of financial tick data increases together with the increase of the aggregation level in transaction time. In addition, we compare binary strings obtained from financial data with binary strings obtained from random number generators to understand if their efficiency can be compared.

We consider the Ising model on an Erdos-Renyi graph \(G(n,d/n)\), for some \(d > 1\), at the critical temperature and prove that the mixing time of the respective Glauber Dynamics is, with high probability, polynomial in the size of the graph. The proof uses recent breakthrough results by Chen and Eldan to bound the spectral gap of the Markov chain. If time permits, we will mention ways to obtain non-trivial lower bounds as well.
Joint work with Allan Sly.

We study the worst-case mixing time of the global Kawasaki dynamics for the fixed-magnetization ferromagnetic Ising model on the class of bounded-degree graphs. Our result partially proves and disproves a conjecture of Carlson, Davies, Kolla, and Perkins: While we confirm that the Kawasaki dynamics mix rapidly below the tree uniqueness threshold for all magnetizations, we also show that contrary to their conjecture, the regime of fast mixing does not extend throughout the entire regime of tractability of the model. Our rapid mixing result involves showing that a sufficiently strong notion of zero-freeness of the partition function of the grand-canonical Ising model implies spectral independence in the fixed-magnetization model. For the slow mixing part, we first prove a sharp threshold for the existence of multiple metastable states in the grand-canonical Ising model on random regular graphs, which we then use to conclude metastability on a suitable class of random graphs for the fixed-magnetization setting.

In a seminal paper, Diaconis and Shahshahani showed that the classical Bernoulli-Laplace urn model exhibits the cutoff phenomenon. Since then, many different generalizations of the model have been proposed and studied. One such model consists of \(d\) urns, each containing \(n\) balls. In each step, a uniformly chosen ball from each urn is moved cyclically to the following urn. Nestoridi and White obtained bounds on the mixing time of this cyclic shift chain. We prove that it exhibits cutoff. More generally, we establish cutoff for a model consisting of \(dn\) balls distributed equally across \(d\) urns, in which balls are moved across urns according to a permutation sampled from a fixed distribution \(\mu\) on the symmetric group \(S_d\). Additionally, under reversibility, we establish cutoff when the distribution \(\mu\) varies with \(n\). Our proofs use spectral profile estimates, comparison arguments, and hit-mix relations.
This talk is based on joint work with Jonathan Hermon and Dominik Schmid.

The generalized Ramsey number \(r(G, H, k)\) is the minimum number of colors needed to edge-color the graph \(G\) so that every copy of \(H\) in \(G\) receives at least \(k\) colors. In this talk we discuss \(r(K_{n, n}, C_{2k}, 3)\). \(r(K_{n, n}, C_{4}, 3)\) was determined to be asymptotically \(2n/3\) by Axenovich, Furedi and Mubayi (lower bound) and Joos and Mubayi (upper bound). We prove new upper and lower bounds for all \(k \ge 3\), and determine \(r(K_{n, n}, C_{6}, 3)\) asymptotically.
This talk is about joint work with Deepak Bal.

Given a graph \(H\), the Ramsey number \(R(H)\) is the smallest \(n\in\mathbb N\) such that every \(2\)-edge-colouring of \(K_n\) yields a monochromatic copy of \(H\). We write \(mH\) to denote the union of \(m\) vertex-disjoint copies of \(H\). These graphs are also known as \(H\)-tilings.
A famous result of Burr, Erd\H os and Spencer states that \(R(mK_3)=5m\) for \(m\ge2\). On the other hand, Moon proved that every \(2\)-edge-coloured \(K_{3m+2}\) yields a \(mK_3\) where each copy of \(K_3\) is monochromatic, for \(m\ge2\). Crucially, in Moon's result, distinct copies of \(K_3\) might receive different colours.
We investigate the analogous questions where the complete host graph is replaced by a graph of large minimum degree. We determine the largest size of a monochromatic \(K_3\)-tiling one can guarantee in any \(2\)-edge-coloured graph of large minimum degree. We also determine the (asymptotic) minimum degree threshold for forcing a \(K_3\)-tiling covering a prescribed proportion of the vertices in a \(2\)-edge-coloured graph such that every copy of \(K_3\) in the tiling is monochromatic. These results therefore provide dense generalisations of the theorems of Burr--Erd\H os--Spencer and Moon.

We present a general approach how to use flag algebras to prove non-existence of a structure of a given size, and apply it to questions in Ramsey Theory.

One of the classic problems in extremal graph theory is estimating \(\mathrm{forb}_k(n, H)\), the number of \(k\)-uniform \(H\)-free hypergraphs on \(n\) vertices for some \(k\)-uniform hypergraph \(H\). Classic results of Erdős, Kleitman, and Rothschild and Erdős, Frankl, and Rödl showed that \(\mathrm{forb}_k(n, H) = 2^{(1 + o(1)) \mathrm{ex}_k(n, H)}\) for every non-\(k\)-partite hypergraph \(H\). Work of Ferber, McKinley, and Samotij showed that \(\mathrm{forb}_k(n, H) = 2^{\Theta( \mathrm{ex}_k(n, H))}\), provided that \(\mathrm{ex}(n, H) \geq \varepsilon n^{k +\varepsilon-\min_{F \subseteq H, v(F) > k} \frac{v(F) - r}{e(F) - 1}}\). This settles the order of growth of \(\log(\mathrm{forb}_k(n, H))\) for most hypergraphs \(H\), leaving only the question for what hypergraphs \(H\), can we show the best possible bound of \(2^{(1 +o(1))\mathrm{ex}_k(n, H)}\)? In joint work with Tao Jiang, we demonstrated that for \(k\)-hypergraphs contained inside a \(k\)-expansion of some non-intersecting \((k - 2)\)-uniform tree, \(\mathrm{forb}_k(n, H) = 2^{(1 + o(1))\mathrm{ex}_k(n, H))}\). In particular, this shows that for linear cycles \(C_\ell^k\) of length \(\ell\) and uniformity \(k\), for \(k \geq 5, \ell \geq 3\), \(\mathrm{forb}_k(n, C_\ell^k) = 2^{(1 + o(1))\mathrm{ex}_k(n, C_\ell^k))}\), settling a question of Balogh, Narayanan, and Skokan for the corresponding values of \(\ell, k\). In this talk, we will discuss the general proof strategy, including our main tool, a novel supersaturation variant of the delta systems method.

A central problem regarding equiangular lines, first raised by Lemmens and Seidel in 1973, is to determine the maximum number of equiangular lines in an \(r\)-dimensional Euclidean space with a common angle of \(\arccos(1/(2k+1))\), for any integer \(k\). In a recent breakthrough, Jiang, Tidor, Yao, Zhang, and Zhao answered this problem when \(r\) is at least doubly exponential in a polynomial in \(k\). In this talk, we will present joint work with Matija Bucic in which we solve the problem when \(r\) is only a single exponential in a polynomial in \(k\). We also show that for any common angle \(\arccos(a)\), the answer equals \(r + o(r)\) already when \(r\) grows faster than any polynomial in \(1/a\).
The key new ingredients underlying our results are improved upper bounds on the multiplicity of the second largest eigenvalue of a graph. In one of the regimes, our bounds are essentially best possible and in the other, they improve and significantly extend a result of McKenzie, Rasmussen, and Srivastava.

A well-known conjecture in random matrix theory asserts that the empirical spectral distributions (ESDs) of random d-regular digraphs converge to the so-called oriented Kesten--McKay law. In this talk, we will discuss a circulant analogue of this conjecture. Specifically, we will be concerned with circulant matrices defined with respect to arbitrary finite abelian groups and having a fixed number d of non-zero entries in each row/column. Equivalently, these can be viewed as adjacency matrices of random d-regular directed Cayley graphs. We will give exact criteria for convergence in expectation and in probability of ESDs in terms of the sequence of underlying groups. As a consequence, a log-asymptotic for the determinant will be derived.

For any two graphs \(G\) and \(H\), the Ramsey number \(R(G, H)\) is the minimum integer \(n\) such that any graph on \(n\) vertices either contains a copy of \(G\) or its complement contains a copy of \(H\) as a subgraph. The book graph of order \((n + 2)\) denoted by \(Bn\) is the graph with \(n\) distinct copies of triangles sharing a common edge called the ‘base’. A cycle of order \(m\) is denoted by \(Cm\).
In this talk, we will discuss some results related to the book- cycle Ramsey number. For any two graphs \(G\) and \(H\), we will discuss the Ramsey goodness of the pair \((G, H)\). A result will be discussed in which we have obtained an exact value of the Ramsey number \(R(K2,n, Cm)\) where \(K2,n\) is the complete bipartite graph and \(m \geq 7\) is odd. This proves that \(K2,n\) is \(Cm\)-good for some parametrization of \(n\) and \(m\).

Given a graph \(G\), the Ramsey number \(R(G)\) is defined to be the smallest \(N\) such that any red/blue colouring of the complete graph on \(N\) vertices contains a monochromatic copy of \(G\). For a tree \(T\) whose bipartition classes have sizes \(t_1 \geq t_2\), two simple constructions show that \(R(T) \geq \max\{t_1+2t_2-1,2t_1-1\}\). Burr conjectured in 1974 that equality holds for every tree \(T\).
It has been shown that Burr’s conjecture is false for certain trees called the double stars, though all of these known counterexamples have large maximum degrees. In 2002, Haxell, Łuczak and Tingley showed that an approximate version of Burr’s conjecture is true if one imposes a maximum degree condition. In a joint work with Richard Montgomery and Matías Pavez-Signé, we prove that Burr’s conjecture is true for all trees with up to small linear maximum degrees. That is, there exists a constant \(c > 0\), such that every tree \(T\) on n vertices with maximum degree at most \(cn\) satisfies \(R(T)=\max\{t_1+2t_2-1,2t_1-1\}\).

Suppose G is a random graph with edge probability p below the threshold for G to be Ramsey for H, so that by the Rödl-Ruciński theorem, with high probability G has a red-blue colouring avoiding monochromatic copies of H. Fix such a colouring f, and reveal a second random graph G' with edge probability q on the same vertex set. How large can q be so that we can extend some colouring f to a "good" colouring of \(G\cup G'\) i.e. one avoiding monochromatic copies of H? This is well understood when p is within a constant factor of the threshold for a wide class of graphs H, due to Conlon, Das, Lee and Meszaros. When p is below the threshold by a factor growing with n, and H is a triangle, it was discovered by Alon, Morris and Samotij that the threshold for q displays two distinct regimes. In this talk I will discuss what happens when H is any cycle.

Consider a red/blue coloring of the edges of the complete graph \(K_n\). The Ramsey multiplicity \(c_t\) is the limit as \(n\) tends to infinity of the smallest possible number of monochromatic t-cliques in such a coloring, normalized by \({n \choose t}\). Disproving a conjecture by Erdős (1962), Thomason (1989) showed that \(c_4 < 1/32\), the value obtained from \(G(n,1/2)\), but the exact value remains unknown. Introducing new methods and ideas, we provide random constructions that improve the upper bounds on \(c_4\) and \(c_5\). Our constructions are substantially more symmetric and structured than the so-far best known ones, due to Parczyk et al. (2022), who used search algorithms on Cayley graphs with considerable computational effort.
Joint work with Chaim Even-Zohar.

In their study of the giant component in inhomogeneous random graphs, Bollobás, Janson, and Riordan introduced a class of branching processes parametrized by a possibly unbounded graphon. We prove that two such branching processes have the same distribution if and only if the corresponding graphons are fractionally isomorphic, a notion introduced by Grebík and Rocha.
This is joint work with Eng Keat Hng and Jan Hladký.

Multiplex graphs—collections of graphs over a shared vertex set—encode complex dependency structures across multiple layers. In this talk, I will present a framework of graphon information-theoretic measures for exchangeable multiplex graphs—including mutual information, total correlation, and higher-order interaction functionals—that quantify redundancy, synergy, and (conditional) independence between graph-generating mechanisms. Multiplex graphs are modeled as jointly exchangeable arrays based on the multivariate Bernoulli distribution with the graph limit representation. We develop consistent estimators for these information-theoretic measures, starting from the single-layer case by constructing estimators for graphon entropy. We then extend our framework explicitly to the multiplex setting, addressing estimation challenges arising in higher dimensions. This approach provides a principled foundation for analyzing higher-order complexity and dependence in exchangeable multiplex graphs. I will conclude by discussing several future research directions.

A permutation class \(\mathcal{F}\) is said to be small if it has growth-rate less than \(\kappa\), where \(\kappa\approx2.20557\). Vatter established a structural classification result for small permutation classes, and later Albert, Ru\v{s}kuc and Vatter proved that every small permutation class has a rational generating function. In an upcoming work, together with Markstr\"{o}m, we prove a strengthening of this result and as a consequence conclude that every small permutation class satisfies a first-order convergence law.
Recently, Albert, Bouvel, F\'{e}ray and Noy proved a first-order convergence law on the avoidance class Av(231), and proved that the set of possible limit values for first-order sentences is a dense subset of \([0,1]\). In this talk, I will discuss our aforementioned result on the first-order convergence law on small permutation classes, and another upcoming joint work with Falgas-Ravry, Skerman and Markstr\"{o}m, in which we prove that
(i) when \(\mathcal{F}\) is a small permutation class whose growth is exponential, the set of possible limits values for first-order sentences is a dense subset of \([0,1]\)
(ii) when \(\mathcal{F}\) is a small permutation class whose growth is bounded by a polynomial, the set of possible limit values is a finite subset of \([0,1]\), and we determine this set explicitly
(iii) in particular, every Geometric grid class Geom(M) of a signed permutation matrix M satisfies a 0-1 -law for first-order sentences. We also give another proof of this fact by constructing an infinite model that is equivalent for each such permutation class.

[No abstract]

The random-connection model is a random graph in which nodes are positioned according to a point process, and edges are formed with location-dependent connection probabilities between nodes. We will present normal approximation results with convergence rates in the Kolmogorov distance for the distributions of subgraph counts in the Poisson and binomial random-connection models as the number of nodes tends to infinity. Our approach relies on the derivation of cumulant identities and cumulant growth rates by the convex analysis of planar diagrams used to enumerate the partitions involved in cumulant expansions.
(joint work with Qingwei Liu)

Asymptotic behaviour of small subgraphs count is a problem with a very long history in the theory of random graphs. While a lot in known in the case of the classical binomial model \(G(n, p)\), other models seem not that easy to approach.
In this talk, we address this problem in the context of the random intersection graph model \(G(n, m, p)\). Here, the threshold function for subgraph containment is known and the distribution of the number of copies on the threshold has been already determined. However, the normal approximation of the number of copies of small subgraphs remains open. Recently only a partial result on triangles count has appeared.
We propose a new method that allows us effectively deal with number of edges and triangles, and might be adapted to other cliques as well. We establish necessary and sufficient conditions for the asymptotic normality and complement them with corresponding convergence rates in both the Wasserstein and the Kolmogorov distances.
This is joint work with Katarzyna Rybarczyk.

Given a graph \(H\), let \(X_H\) be the number of the copies of \(H\) in the random graph \(G(n,p)\). In 2004 Janson and Rucinski formulated the Upper Tail Problem: what are the asymptotics of \(\log P(X_H > t E[X_H])\) for fixed \(t > 1\), as \(n\) grows. Harel, Mousset and Samotij (2022) made a breakthrough that lead to a solution for every connected regular \(H\) for essentially all sequences \(p = p(n)\) of interest. We determine the asymptotics for \(H\) being a star, thus giving a first class of irregular graphs for which the Upper Tail Problem is solved for the whole range of \(p\), including the transition between Poisson and localized regimes.
(Joint work with M. Akhmejanova)

The question of whether the central limit theorem (CLT) holds for the total number of edges in exponential random graph models (ERGMs) in the subcritical region of parameters has remained an open problem. In this paper, we establish the CLT. As a result of our proof, we also derive a convergence rate for the CLT, an explicit formula for the asymptotic variance, and the CLT for general subgraph counts. To establish our main result, we develop Stein's method for the normal approximation of general functionals of nonlinear exponential families of random variables, which is of independent interest. In addition to ERGMs, our general theorem can also be applied to other models. A key ingredient needed in our proof for the ERGM is a higher-order concentration inequality, which was known in a subset of the subcritical region called Dobrushin's uniqueness region. We use Stein's method to partially generalize such inequalities to the subcritical region.

A tuple \((G_1,\dots,G_n)\) of graphs on the same vertex set of size \(n\) is said to be Hamilton-universal if for every map \(\chi: [n]\to[n]\) there exists a Hamilton cycle such that the \(i\)-th edge comes from \(G_{\chi(i)}\). Bowtell, Morris, Pehova and Staden proved an analog of Dirac's theorem in this setting, namely that if \(\delta(G_i)\geq (1/2+o(1))n\) then \((G_1,\dots,G_n)\) is Hamilton-universal. Combining McDiarmid coupling and a colorful version of the Friedman-Pippenger tree embedding technique, we establish a similar result in the sparse setting of random graphs, showing that there exists \(C\) such that if the \(G_i\) are independent random graphs sampled from \(G(n,p)\), where \(p\geq C\log n/n\), then \((G_1,\dots,G_n)\) is Hamilton-universal with high probability.

Two-colorability of hypergraphs is a well-studied problem. Significant results have been obtained for random instances, which, for a number of questions, provide the best-known extremal examples.
However, the most notable results are primarily stated in the context of uniform hypergraphs, leaving the impact of edges with varying sizes unexplored. Most of the extremal hypergraph questions for uniform hypergraphs have natural non-uniform counterparts, where the number of edges is replaced by the sum of the weights of the edges. The most intuitive weight of an edge is the probability that it becomes monochromatic under a uniformly random coloring. It turns out, however, that generalizing theorems to non-uniform cases is considerably more challenging.
Our work focuses on random non-uniform hypergraphs. We aim to formulate precise bounds on the sum of the weights of edges that guarantee two-colorability. We approach this from two perspectives: non-constructive, where we are only interested in the existence of a proper two-coloring, and algorithmic, where we require that such a coloring can be found by a polynomial-time algorithm.
Surprisingly, non-uniformity has a drastically different impact on these problems. In the algorithmic version, if the edge sizes are sufficiently different, they are unlikely to interact in a way that affects a significant number of potential colorings. This has enabled us to provide improved conditions for two-colorability that account for the non-uniform structure of a hypergraph. Conversely, in the non-constructive two-coloring, after applying the natural weighting, different edge sizes essentially cease to matter.

The concept of discrepancy for Hamilton cycles is well developed: for a graph G with edges coloured red or blue, we are interested in finding a Hamilton cycle with many more edges in the dominant colour. Bounds for discrepancy for Hamilton cycles were explored by Balogh, Csaba, Jing and Pluhar, and in the random graph by Gishboliner, Krivelevich and Michaeli. Following a result of Krivelevich, Lee and Sudakov on the robustness of Dirac graphs with respect to Hamiltonicity, we examine the discrepancy for Hamilton cycles in random subgraphs of graphs with high minimum degree.
More precisely, we show that for \(c > 0\) there exists \(k > 0\) such that for G a graph on \(n\) vertices with minimum degree at least \((3/4 + c)n\), a random subgraph \(G_p\) with \(p\) above the Hamiltonicity threshold asymptotically almost surely satisfies that any 2-colouring of its edges leads to a Hamilton cycle with discrepancy at least \(kn\). Both the minimum degree and the bound on \(p\) are asymptotically optimal.

A graph is "proportional" if every 3-vertex graph occurs in it exactly the same number of times as the expected value in a random graph. We extend this notion to proportional edge-colorings of the complete graph with any number of colors, rather than two. In large random graphs/colorings, they provide examples for degenerate distributions of their number of occurrences. We give a probabilistic construction of proportional edge-colorings with respect to random models where every edge is independently assigned a random color according to some rational probability vector, extending a result on graphs by Janson and Spencer. The idea of this construction is algorithmic, and we find an explicit minimal example of an 81-vertex proportional 3-coloring via a computer search which follows a similar approach.

We investigate subsets with small sumset in arbitrary abelian groups. For an abelian group \(G\) and an \(n\)-element subset \(Y \subseteq G\) we show that if \(m \ll s^2/(\log n)^2\), then the number of subsets \(A \subseteq Y\) with \(|A| = s\) and \(|A + A| \leq m\) is at most \(2^{o(s)}\binom{\frac{m+\beta}{2}}{s},\) where \(\beta\) is the size of the largest subgroup of \(G\) of size at most \(\left(1+o(1)\right)m\). This bound is sharp for \(\mathbb{Z}\) and many other groups. Our result improves the one of Campos and nearly bridges the remaining gap in a conjecture of Alon, Balogh, Morris, and Samotij.
We also explore the behaviour of uniformly chosen random sets \(A \subseteq \{1,\ldots,n\}\) with \(|A| = s\) and \(|A + A| \leq m\). Under the same assumption that \(m \ll s^2/(\log n)^2\), we show that with high probability there exists an arithmetic progression \(P \subseteq \mathbb{Z}\) of size at most \(m/2 + o(m)\) containing all but \(o(s)\) elements of \(A\). Analogous results are obtained for asymmetric sumsets, improving results by Campos, Coulson, Serra, and Wötzel.
The main tool behind our results is a more efficient container-type theorem developed for sets with small sumset, which gives an essentially optimal collection of containers. The proof of this combines an adapted hypergraph container lemma, that caters to the asymmetric setup as well, with a novel ``preprocessing'' graph container lemma, which allows the hypergraph container lemma to be called upon significantly less times than was necessary before.
Joint work with D. Liu and T. Szabó.

The Cayley sum graph \(G_A\) of a set \(A \subseteq Z_n\) is defined to have vertex set \(Z_n\) and an edge between two distinct vertices \(x, y \in Z_n\) if \(x + y \in A\). Green and Morris proved that if the set \(A\) is a \(p\)-random subset of \(Zn\) with \(p = 1/2\), then the independence number of \(G_A\) is asymptotically equal to the \(G(n, 1/2)\) with high probability. Our main theorem is the first extension of their result to \(p = o(1)\): we show that, with high probability, \(α(G_A ) = (1 + o(1))α(G(n, p))\) as long as \(p \geq (\log n)^{−1/80}\). One of the tools in our proof is a geometric-flavoured theorem that generalizes Freiman’s lemma, the classical lower bound on the size of high dimensional sumsets.
Using similar techniques, we are able to determine, up to a factor of \(2^{o(k)}\) , the number of k-sets \(A \subset [n]\) such that \(|A + A| \leq m\), where \(k = \Theta(\log n)\) and \(m \leq k^{1+\delta}\), for small \(\delta > 0\). This solves a question posed by Green and Morris in a strong form.

The doubling factor of a finite set of integers \(A\) is defined as the ratio \(\lambda = |A+A|/|A|\). The classical Freiman-Rusza result states that \(A\) is contained in a generalised arithmetic progression of size \(f(\lambda)|A|\) and dimension \(d(\lambda)\). The current best bound on \(d(\lambda)\) is polynomial in \(\lambda\), and the best bound on \(f(\lambda)\) is exponential in \(\lambda\). We refine this by showing that whenever \(\lambda = o(k^{1/4})\) we have that for a random set \(A \subseteq [n]\), chosen uniformly among all sets of size \(k\) and doubling factor \(\lambda\), with high probability \(A\) is contained in an arithmetic progression of size \((1 + o(1))\lambda k/2\). Previously this was only known for \(\lambda = o(k^{1/31})\).
Joint work with Rajko Nenadov.

A subset \(A\) of \(A_n\) is \(k\)-product-free if for all \(a_1,a_2,\dots,a_k\in A\), \(a_1a_2\dots a_k\) \(\notin A\). We determine the largest \(3\)-product-free and \(4\)-product-free subsets of \(A_n\) for sufficiently large \(n\). We also obtain strong stability results and results on multiple sets with forbidden cross products. The principal technical ingredient in our approach is the theory of hypercontractivity in \(S_n\).
Joint work with Peter Keevash.

In 1782, Euler conjectured that no Latin square of order \(n \equiv 2 \bmod 4\) has a decomposition into transversals. While confirmed for \(n = 6\) by Tarry in 1900, Bose, Parker, and Shrikhande constructed counterexamples in 1960 for each \(n \equiv 2 \bmod 4\) with \(n \geq 10\). We show that, in fact, counterexamples are extremely common, by showing that if a Latin square of order \(n\) is chosen uniformly at random then with high probability it has a decomposition into transversals.

A well-known question in combinatorial group theory, going back to a conjecture of Graham from 1971, asks if given a subset S of some abelian group, whether it is possible to permute S as \(s_1,...,s_t\) so that the partial sums \(s_1+...+s_j\) are all distinct for each \(j < t\). We discuss recent progress on this question.
Joint work with Benjamin Bedert, Matija Bucic, Noah Kravitz, and Richard Montgomery.

In 1975, Stein made a wide generalisation of the Ryser-Brualdi-Stein conjecture on transversals in Latin squares, conjecturing that every equi-n-square (an \(n \times n\) array filled with n symbols where each symbol appears exactly n times) has a transversal of size \(n - 1\). That is, it should have a collection of \(n - 1\) entries that share no row, column, or symbol. In 2017, Aharoni, Berger, Kotlar, and Ziv showed that equi-n-squares always have a transversal with size at least \(2n/3\). In 2019, Pokrovskiy and Sudakov disproved Stein’s conjecture by constructing equi-n-squares without a transversal of size \(n − (\log n)/42\) , but asked whether Stein’s conjecture is approximately true. I.e., does an equi-n-square always have a transversal with size \((1 − o(1))n\)?
We answer this question in the positive. More specifically, we improve both known bounds, showing that there exist equi-n-squares with no transversal of size \(n − \Omega(\sqrt{n})\) and that every equi-n-square contains \(n − n^{1-\Omega(1)}\) disjoint transversals of size \(n − n^{1-\Omega(1)}\).
This is joint work with Debsoumya Chakraborti, Micha Christoph, Zach Hunter and Richard Montgomery.

A conjecture of Cameron states that the distribution of the number of odd rows in an \(n \times n\) uniformly random Latin square is approximately binomial with \(n\) trials and success probability \(1/2\). We prove this conjecture in several different senses, including total variation convergence, a local central limit theorem, and a large deviation principle. In fact, we prove a generalisation for the joint distribution of the number of odd rows, odd columns and odd symbols, showing they behave roughly as independent binomials. Along the way, we introduce several general techniques for the study of random Latin squares, including a new re-randomisation technique via ``stable intercalate switchings'', and a new approximation theorem comparing random Latin squares with a certain independent model.
This is joint work with Matthew Kwan and Mehtaab Sawhney.

A graph \(G\) on \(n\) vertices is semirandomly constructed when, repeatedly over time, a random vertex \(v\) is offered and a player adds to \(G\) an edge incident to \(v\). The goal is that \(G\) satisfy some property as quickly as possible, such as such as containment of a perfect matching, Hamilton cycle, or given graph \(H\).
A seminal result is that for any \(H\) of maximum degree \(\Delta\), this can be done (with high probability) in time \((3/2+o_\Delta(1)) \Delta n\). We improve this to \((1/2+o_\Delta(1)) \Delta n\), matching the natural lower bound, and extend it to a semirandom “tree” model.
The semirandom process also extends to \(r\)-uniform hypergraphs, where the player is offered \(s\) vertices and chooses \(r-s\) others to make a hyperedge. We show that in the 2-offer 3-uniform case it is possible to construct a perfect matching, or a loose Hamilton cycle, in time \(O(n)\). It is not possible to construct a tight Hamilton cycle in linear time: we show an \(\Omega(n^{5/4})\) lower bound and an \(O(n^{23/16})\)-time construction.
The constructions use progressively more sophisticated strategies.
This is based on three works, with Michael Anastos, Maur{\'i}cio Collares, Joshua Erde, Mihyun Kang, Michael Molloy, Olaf Parczyk, Pawe\l{} Pra\l{}at, and Dominik Schmid.

The List Colouring Conjecture posits that the list edge chromatic number of any graph is equal to the edge chromatic number, and thus is at most D+1 where D is the maximum degree. This means that if each edge is assigned a list of D + 1 colours then it is always possible to obtain a proper edge colouring by choosing one colour from each list.
In the 1990’s, Khan proved that one can always obtain a proper edge colouring from lists of size \(D + o(D)\), then Molloy and Reed obtained \(D + D^{1/2}poly(\log D)\).
We improve that bound to \(D + D^{2/5}poly(\log D)\)

In 1980, Akiyama, Exoo, and Harary conjectured that the edges of every graph with maximum degree \(\Delta\) can be decomposed into at most \(\lceil(\Delta+1)/2\rceil\) linear forests, where a linear forest is a collection of vertex-disjoint paths. This conjecture was confirmed asymptotically by Alon in 1988 who showed that \((1+o(1)) \cdot \Delta/2\) linear forests suffice. The current best bound is due to Lang and Postle who showed that there is a decomposition into at most \(\Delta/2 + \mathcal{O}(\sqrt{\Delta} \log^4\Delta)\) linear forests.
We show that any graph on \(n\) vertices can be decomposed into at most \(\Delta/2 + \mathcal{O}(\log n)\) linear forests. This improves the previous upper bounds for \(\Delta = \Omega(\log^2 n)\). Along the way, we show that any \(d\)-regular graph on \(n\) vertices has a spanning linear forest with at most \(2 \cdot n / (d+1)\) paths. This resolves a conjecture of Feige and Fuchs and confirms a well-known conjecture of Magnant and Martin up to a factor of 2.
This talk is based on joint work with Micha Christoph, Nemanja Draganić, António Girão, Eoin Hurley, and Alp Müyesser.

We study a generalisation of Vizing's theorem, where the goal is to simultaneously colour the edges of graphs \(G_1,\dots,G_k\) with few colours. We obtain asymptotically optimal bounds for the required number of colours in terms of the maximum degree \(\Delta\), for small values of \(k\) and for an infinite sequence of values of \(k\). This asymptotically settles a conjecture of Cabello for \(k=2\). Moreover, we show that \(\sqrt k \Delta + o(\Delta)\) colours always suffice, which tends to the optimal value as \(k\) grows. We also show that \(\ell \Delta + o(\Delta)\) colours are enough when every edge appears in at most \(\ell\) of the graphs, which asymptotically confirms a conjecture of Cambie. Finally, our results extend to the list setting. We also find a close connection to a conjecture of Füredi, Kahn, and Seymour from the 1990s and an old problem about fractional matchings.

At each step of the \(3\)-neighbor bootstrap percolation process on a graph \(G\), every uninfected vertex with at least three infected neighbors becomes infected. We say that an initial set of infected vertices percolates if eventually every vertex of \(G\) becomes infected. Building on the work of Dukes, Noel, and Romer, we completely determine the minimum number of initially infected vertices required to percolate on an \(m\times n\) grid. We then consider the same question for the torus grid graphs \(C_m\Box C_n\).
Joint work with Neal Bushaw.

We consider the following natural question. Given a matrix \(A\) with i.i.d. random entries, what are the moments of the determinant of \(A\)? In other words, what is \(\mathbb{E}[\det(A)^k]\)? While there is a general expression for \(\mathbb{E}[\det(A)^k]\) when the entries of \(A\) are Gaussian, much less is known when the entries of \(A\) have some other distribution.
In two recent papers, we answered this question for \(k = 4\) when the entries of \(A\) are drawn from an arbitrary distribution and for \(k = 6\) when the entries of \(A\) are drawn from a distribution which has mean \(0\). These analyses used recurrence relations and were highly intricate. In this paper, we show how these analyses can be simplified considerably by using analytic combinatorics on permutation tables.

A proper coloring of a graph labels each node of a graph with a color in \( \{ 1, \ldots, k \} \) such that no two nodes with the same color are connected by an edge. Counting the number of such colorings is #P-complete, and so approximate counting using uniform samples from the set of colorings is often used instead. Jerrum gave the first approximate sampling technique that requires a linear number of colors in the max degree of the graph, and ran in \( \Theta(n \ln(n)) \) time on an \( n \) node graph. Recent efforts have resulted in the development of exact sampling algorithms that also require a linear number of colors in the max degree, still requiring \( \Theta(n\ln(n)) \) time. This work presents the first exact sampling algorithm for this problem that uses a linear number of colors in the max degree and runs in \( \Theta(n) \) time.

We introduce an efficient algorithm for the uniform sampling of directed acyclic graphs (DAGs). Our sampler is based on the Boltzmann model developed by Duchon et al. in 2004, and thus extends the Boltzmann sampler toolbox.
Based on join work with Wojciech Gabryelski.

This work establishes novel optimum mixing bounds for the Glauber dynamics on the Hard-core and Ising models. These bounds are expressed in terms of the local connective constant of the underlying graph G. This is a notion of effective degree for G.
Our results have some interesting consequences for bounded degree graphs:
1. They include the max-degree bounds as a special case
2.They improve on the running time of the FPTAS considered in [Sinclair,Srivastava,Stefankonic andYin: PTRF 2017] for general graphs
3. They allow us to obtain mixing bounds in terms of the spectral radius of the adjacency matrix and improve on [Hayes: FOCS 2006].
We obtain our results using tools from the theory of high-dimensional expanders and, in particular, the Spectral Independence method [Anari, Liu, Oveis-Gharan: FOCS 2020]. We explore a new direction by utilising the notion of the k-non-backtracking matrix H in our analysis with the Spectral Independence. The results with H are interesting in their own right.

The introduction of geometry has proven instrumental in the efforts towards more realistic models for real-world networks.
A common model for social networks is the Geometric Inhomogeneous Random Graph (GIRG), in which vertices draw random positions in the unit cube, and the probability of two vertices forming an edge depends on their geometric distance. In classical GIRGs, the geometry is modelled using a norm, so in particular two points are close if they are close in all coordinates. However, geometries where the distance is defined in terms of more general positive boolean formulas, may sometimes be better suited to capture the formation of ties in social networks: Two people are more likely to know each other if their use of social media platforms is similar and they have similar niche hobbies, or if they are closely related in terms of kinship, or if their homes are close and they engage in similar sports.
Motivated by this observation, we introduce and study a large class of corresponding distance functions, which we call Boolean Distance Functions (BDF) - and the GIRGs they induce. The resulting family of graphs extends both classical GIRGs and GIRGs induced by the minimum component distance, which were studied by Lengler and Torodović.
It is known that - while many key properties of GIRGs, such as the log-log average distance and sparsity, are independent of the distance function - the Euclidean distance induces small separators, i.e. sublinear cuts of the unique giant component in GIRGs, whereas no such sublinear separators exist under the minimum component distance. Building on this work, we give a complete classification for the existence of small separators in BDF-GIRGs.
This talk is based on joint work with Marc Kaufmann, Raghu Raman Ravi and Ulysse Schaller.

We study high-dimensional random geometric graphs (RGGs) of edge-density p with vertices uniformly distributed on the d-dimensional torus and edges inserted between sufficiently close vertices with respect to an \(L_q\)-norm. In this setting, we focus on distinguishing an RGG from an Erdős–Rényi graph if both models have the same marginal edge probability p. So far, most results in the literature considered either spherical RGGs with \(L_2\)-distance or toroidal RGGs under \(L_\infty\)-distance. However, for general \(L_q\)-distances, many questions remained open, especially if p is allowed to depend on n. The main reason for this is that RGGs under \(L_q\)-distances can not easily be represented as the logical "AND" of their 1-dimensional counterparts as is the case for \(L_\infty\) geometries. To overcome this difficulty, we devise a novel technique for quantifying the dependence between edges based on modified Edgeworth expansions.
Our technique yields the first tight algorithmic upper bounds for distinguishing toroidal RGGs under general \(L_q\) norms from Erdős–Rényi graphs for any fixed p and q. We achieve this by showing that the signed triangle statistic can distinguish the two models when \(d \ll n^3p^3\) for the whole regime of edge probabilities \(c/n < p < 1\). Additionally, our technique yields an improved information-theoretic lower bound for this task, showing that the two distributions converge in total variation whenever \(d=\Omega(n^3p^2)\), which is just as strong as the currently best known lower bound for spherical RGGs in case of general p from Liu et al. [STOC'22]. Finally, our expansions allow us to tightly characterize the spectral properties of toroidal RGGs both under \(L_q\)-distances and \(L_\infty\)-distance. We find that these are quite different for \(q < \infty\) vs. \(q = \infty\). Our results partially resolve a conjecture of Bangachev and Bresler [COLT'24] and prove that the distance metric, rather than the underlying space, is responsible for the observed differences in the behavior of high-dimensional spherical and toroidal RGGs.

Fix \(d\ge2\) and consider a uniformly random set \(P\) of \(n\) points in \([0,1]^{d}\). Let \(G\) be the Hasse diagram of \(P\) (with respect to the coordinatewise partial order), or alternatively let \(G\) be the Delaunay graph of \(P\) with respect to axis-parallel boxes (where we put an edge between \(u,v\in P\) whenever there is an axis-parallel box containing \(u,v\) and no other points of \(P\)).
In each of these two closely related settings, we show that the chromatic number of \(G\) is typically \((\log n)^{d-1+o(1)}\) and the independence number of \(G\) is typically \(n/(\log n)^{d-1+o(1)}\). When \(d=2\), we obtain bounds that are sharp up to constant factors: the chromatic number is typically of order \(\log n/\log\log n\) and the independence number is typically of order \(n\log\log n/\log n\).
These results extend and sharpen previous bounds by Chen, Pach, Szegedy and Tardos. In addition, they provide new bounds on the largest possible chromatic number (and lowest possible independence number) of a \(d\)-dimensional box-Delaunay graph or Hasse diagram, in particular resolving a conjecture of Tomon.

Fix a uniform hypergraph \(H\). Consider the random graph process that, starting with a complete uniform hypergraph on \(n\) vertices, iteratively deletes the edges of a copy of \(H\) chosen uniformly at random among all remaining copies and that terminates when no copies of \(H\) remain. What can we say about the number \(R(n,H)\) of edges left after termination?
While the process is easy to formulate, showing that asymptotic estimates of the correct order of magnitude for \(R(n,H)\) hold with high probability turns out to be challenging.
Bohman, Frieze and Lubetzky achieved this for the case where \(H\) is a triangle by showing that in this case typically \(n^{3/2+o(1)}\) edges remain, but so far, there were no such estimates available for any other non-trivial choice of \(H\).
We extend this result by proving analogous bounds for all cases where \(H\) comes from a large natural class of hypergraphs. As this class in particular includes cliques, this confirms a major folklore conjecture in the area.
This is joint work with Felix Joos.

We study a semi-random (R\"odl nibble) variant of the random greedy independent set algorithm to construct a large independent set in a hypergraph. Let \(r \ge 2\) be a fixed integer and let \(\mathcal{H}\) be a \(r\)-uniform \(N\)-vertex hypergraph satisfying that each vertex is contained in at most \(D\) edges. Assuming \(\min\{ N^{r-1}/D, D \}\ge f\) for some \(f\ge (\log N)^c\) with \(c > 0\), we prove that if \(\mathcal{H}\) satisfies some degree and codegree conditions, then with high probability there are \(\Omega\Big(N\big(\frac{\log f}{D} \big)^{\frac{1}{r-1}} \Big)\) vertices in the independent set constructed by the algorithm.
A key improvement of this semi-random variant compared to Bennett and Bohman's previous random greedy version is that we replace their requirement of \(\mathcal{H}\) being \(D\)-regular by the maximum degree condition. We also prove that the independent set constructed by this algorithm has various pseudo-random properties, including those needed for applications in Ramsey theory. And we prove that the same holds for a random subhypergraph, i.e., the above properties remain true in the sparse setting.
Based on joint work with Lutz Warnke.

The well-known Ryser-Brualdi-Stein Conjecture states that any proper edge-coloring of the complete bipartite graph \(K_{n,n}\) contains a rainbow matching of size \(n-1\). In this talk, we will discuss a multiplicity extension of this conjecture, proposed recently by Anastos, Fabian, M\"uyesser, and Szab\'o, and prove a special case of it. More precisely, we will show that, for all positive integers \(n,a_1, a_2, a_3\) satisfying \(a_1+a_2+a_3 = n-1\), every bipartite graph on \(2n\) vertices that is the union of three perfect matchings \(M_1\), \(M_2\), and \(M_3\) contains a matching \(M\) such that \(|M\cap M_i| =a_i\) for \(i\in \{1,2,3\}\).
This is joint work with Micha Christoph and Tibor Szab\'o.

The canonical Ramsey theorem of Erd\H os and Rado implies that for any graph \(H\), there exists some minimum \(n=ER(H)\) such that every colouring of the edges of \(K_n\) results in a copy of \(H\) whose colouring is either monochromatic, rainbow, or lexicographic.
In a recent preprint, Gishboliner Milojevi\'c, Sudakov and Wigderson showed that \(k^{\Omega(1)}\le ER(H)\le k^{O(1)}\) when H is a bipartite graph of order \(k\) and bounded degree. We tighten these bounds for even cycles, showing that \(ER(H)=\Theta(k^2)\).
Authors: Sylwia Antoniuk, Alberto Larrauri, Amanda Montejano, Patrick Morris, T\'assio Naia, Miquel Ortega

The canonical van der Waerden theorem asserts that, for sufficiently large n, every colouring of \([n]\) contains either a monochromatic or a rainbow arithmetic progression of length \(k\) (\(k\)-AP, for short). In this talk, we will determine the threshold at which the binomial random subset \([n]_p\) almost surely inherits this canonical property. As an application, we construct sets \(S\subseteq [n]\) that satisfy the canonical van der Waerden property for \(k\)-APs and such that the \(k\)-APs in \(S\) define a \(k\)-uniform hypergraph of arbitrarily high girth.
(joint work with J. D. Alvarado, Y. Kohayakawa, G. O. Mota and M. Ortega)

Let \(\overrightarrow{H}\) be an oriented graph, and write \(G \to \overrightarrow{H}\) if every orientation of \(G\) contains \(\overrightarrow{H}\). We are interested in the threshold function for when the binomial random graph \(G(n,p)\) satisfies \(G(n,p) \to \overrightarrow{H}\) for an acyclic oriented graph \(\overrightarrow{H}\). Similarly to the classical Ramsey setting, natural intuition suggests that \(n^{-1/m_2(\overrightarrow{H})}\) (where \(m_2(\overrightarrow{H})\) denotes the maximum \(2\)-density of the underlying graph \(H\)) is the threshold, and it is known that this is an upper bound for the threshold. We prove that it is indeed the threshold for a very large number of cases, including when \(\overrightarrow{H}\) has a vertex of high in or out-degree, a long directed path, or is sufficiently dense.
Joint work with Joseph Hyde and T\'assio Naia.