Program

Plenary Talks

➤ Noga Alon
Title: Random Norms
Abstract: Probabilistic Combinatorics, initiated in the 40s, is one of the most active areas in modern Discrete Mathematics, with its own conferences, books and journals. One of the main reasons for the impressive success of this discipline is the foundation of the journal and the conference Random Structures and Algorithms. After very brief comments about the history of this development and the leading role of Michał Karoński in it I will describe a recent joint work with Matia Bucić and Lisa Sauermann about random norms. The main message I will try to convey is that topology can replace probability in the investigation of extremal problems in discrete geometry by the study typical norms. This will be illustrated by the description of surprisingly tight solutions of the unit and distinct distances problems for typical norms, settling, in a strong form, questions and conjectures of Matoušek, of Brass and of Brass, Moser and Pach.

➤ Annika Heckel
Title: The chromatic number of \(G(n, 1/2)\): bounds, concentration and conjectures
Abstract: I will discuss the chromatic number of the random graph \(G(n,p)\), which is the minimum number of colours needed for a vertex colouring where neighbours are always coloured differently. In particular I will talk about the concentration (or lack thereof) of the chromatic number of \(G(n,1/2)\), and how the behaviour of the required number of colours changes drastically if we restrict the possible colouring types to exclude very large colour classes. For example, the equitable chromatic number of \(G(n,1/2)\) turns out to be extremely tightly concentrated. This leads to a number of conjectures about the exact limiting distribution of the chromatic number of \(G(n,1/2)\).

Based on joint work with Oliver Riordan and with Konstantinos Panagiotou.

➤ Jeff Kahn
Title: On the \(H\)-space of a random graph
Abstract: For a graph \(G\), write \({\mathcal E}(G)\) for its \emph{edge space} (that is, \(\mathbb{Z}_2^{E(G)}\) with members naturally identified with subgraphs of \(G\)) and \({\mathcal C}_H(G)\) for its \(H\)- space, the subspace of \({\mathcal E}(G)\) spanned by the copies of \(H\) in \(G\).

We are interested in understanding when \(G=G_{n,p}\) is likely to satisfy
\[
{\mathcal C}_H(G) = {\mathcal W}_H(G),
\]
where \({\mathcal W}_H\) takes one of four natural values; e.g. if \(G\) has all degrees even and an odd number of edges, then \({\mathcal W}_H (G)\) is the cycle space of \(G\), the subspace of \({\mathcal E}(G)\) spanned by the cycles of \(G\). We recall a natural, if optimistic, guess at a general answer to the above question, and show it's correct whenever \(H\) is strictly 2-balanced.

Joint with Quentin Dubroff.

➤ Sam Mattheus
Title: The asymptotics of \(r(4,t)\)
Abstract: For integers \(s,t \geq 2\), the Ramsey numbers \(r(s,t)\) denote the minimum \(N\) such that every \(N\)-vertex graph contains either a clique of order \(s\) or an independent set of order \(t\). I will give an overview of recent work, joint with Jacques Verstraete, which shows
\[ r(4,t) = \Omega\Bigl(\frac{t^3}{\log^4 \! t}\Bigr) \quad \quad \mbox{ as }t \rightarrow \infty\]
which determines \(r(4,t)\) up to a factor of order \(\log^2 \! t\), and solves a conjecture of Erdös.

➤ Richard Montgomery
Title: Transversals in Latin Squares
Abstract: A Latin square of order n is an n by n grid filled with n different symbols so that every symbol occurs exactly once in each row and each column. A transversal in a Latin square is a collection of cells which share no row, column or symbol, and the order of a transversal is its number of cells.

A Latin square of order n may not have even one transversal of order n, but Kwan has shown that if a Latin square of order n is chosen uniformly at random, then it is likely to have a transversal of order n. Euler considered Latin squares which can be decomposed into disjoint transversals of order n, and it seems likely that a typical random Latin square should have such a decomposition. I will discuss the challenges of proving this, and progress towards it, as well as finding large transversals in any Latin square.

This is based in part on joint work with Candy Bowtell

➤ Jinyoung Park
Title: p-smallness of increasing families
Abstract: For a finite set X, a family F of subsets of X is said to be increasing if any set A that contains B in F is also in F. The p-biased product measure of F increases as p increases from 0 to 1, and often exhibits a drastic change around a specific value, which is called a "threshold." Thresholds of increasing families have been of great historical interest and a central focus of the study of random discrete structures, with estimation of thresholds for specific properties the subject of some of the most challenging work in the area. M. Talagrand introduced the notion of "p-smallness" as an explicit certificate to show the p-biased product measure of a given increasing family F is small. In this talk, we will introduce various problems related to "p-smallness" of increasing families. Based on joint works with Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Huy Tuan Pham.

➤ Julian Sahasrabudhe
Title: An exponential improvement for diagonal Ramsey
Abstract: I will discuss the recent proof that \( R(k) < (4-c)^k\), for all \(k\), where \(R(k)\) denotes \(k\)th diagonal Ramsey number. This talk is based on joint work with Marcelo Campos, Simon Griffiths and Rob Morris.

➤ Joel Spencer
Title: Random Gems
Abstract: We give three gems of the Probabilistic Method. These problems have been worked on for decades but here we give the most beautiful arguments -- illustrating the increasingly sophisticated applications of probability.

From Erdös in 1963: How big can \(k\) be so that given any collection of less than \(m=2^{n-1}k\) sets,
all of size \(n\), there exists a two-coloring of the underlying vertices so that none of the sets are monochromatic. Erdös randomly colored but others have done better, using an ingenious randomized algorithm.

From the speaker in 1985. Given \(n\) vectors \(\vec{v_1},\ldots,\vec{v_n}\in R^n\), all with \(L^{\infty}\) norm at most one, some signed sum \(\pm\vec{v_1}\pm\cdots\pm\vec{v_n}\) has \(L^{\infty}\) norm at most \(K\sqrt{n}\), \(K\) constant. The original proof was "ugly", we give our choice for the Book proof, using a restricted Brownian motion.

From Bender, Canfield and McKay, 1990. Asymptotically, how many connected, labelled graphs are there with \(n\) vertices and (say) \(2n\) edges. We prefer our own proof, with van der Hofstad,
using a Brownian Bridge.

➤ Eric Vigoda
Title: Optimal Mixing of MCMC via Spectral Independence
Abstract: Markov Chain Monte Carlo (MCMC) algorithms are an important tool for sampling from high-dimensional distributions. The Glauber dynamics is the simplest example of a MCMC algorithm: its transitions update the configuration at a randomly chosen coordinate/vertex in each step. We prove that a new technique called spectral independence implies optimal mixing bounds for the Glauber dynamics. This yields an interesting computational phase transition: fast mixing of the simple Glauber dynamics in one region and NP-hardness in the other region. I will explain these results in the framework of generating a random independent set of a graph, and its generalization to independent sets weighted by a parameter \(\lambda>0\) known as the hard-core model.

This is joint work with Zongchen Chen (MIT) and Kuikui Liu (MIT).

Contributed Talks

(in alphabetical order of the speakers names)

Authors: Margarita Akhmejanova, Ilia Bogdanov, Grigori Chelnokov
Speaker: Margarita Akhmejanova
➤ Title: On-line colorings
Abstract: We introduce and analyze a continuous generalization of Chip Game, first defined by Spencer and later used by Aslam and Dhagat for modeling online coloring of hypergraphs. General Gold Sand game (\(S,\tau_{i\in \mathcal F}\)) is determined by a finite set \(S\), called the set of paths, an element \(dead\in S\), called death path, and a set of mappings \(\tau_{i\in\mathcal{F}}\colon S \to S\), satisfying \(\tau_i(dead)=dead\). The cells of the playing field are enumerated by \((\mathbb{N}\cup \{0\})\times S\), the cells \((0,path~m): m\neq dead\) are called winning cells. All cells contain real non-negative numbers, called \emph{gold sand}. There is only finite amount of non-zero numbers. In each round Pusher splits gold sand in each cell into two parts, called standing and running. Then Remover (knowing how Pusher shared and knowing the current amount of gold sand in each cell) picks one of the mappings \(\tau_i\). After that, each standing part keeps its cell, and each running part changes its cell according to the rule \((n,path~m) \to (n-1,path~\tau_i(m))\). Moreover, all sand from the dead path is removed from the field and all sand from the winning cells instantly becomes Pusher's win and is also removed from the field. Then the new round begins. The question: let \( x=[x_{i,path~j}]_{([N]\cup \{0\})\times S}\) denotes the vector of initial distribution of gold sand, in short, arrangement \( x\). Let \(\mathcal{X}\) be the set of all vectors of initial distribution of gold sand. Can one find the supremum of Pusher's win for any given arrangement \( x\in\mathcal{X}\)? We give a precise answer to the question for different types of colorings. For example, On-line property B in new terms can be formulated as \( S=\{0,1,2,dead\}, \tau_1:\{0,1,2\}\to \{1, 1, dead \}, \tau_2:\{0,1,2\}\to \{2, dead, 2\}\). And our first theorem says the following. Theorem 1. For each \(p \in[0,1]\) through \( w(p)\) denote the vector \( w_{p} \in \mathcal{X}\), such that \(w(p)_{0,path~0}=w(p)_{0,path~1}=w(p)_{0, path~2}=1\) and for all for all \(i\in\mathbb{N}\) \( w(p)_{i, p a t h~j}= \left\{\begin{array}{rll} p^{i}+(1-p)^{i} & \text { if } & j=0, \\ p^{i} & \text { if } & j=1, \\ (1-p)^{i} & \text { if } & j=2. \end{array}\right. \) Then the supremum of Pusher's win in Continuous on-line property B game on the initial arrangement \( x\) is \(\min _{p} x \cdot w(p)\).

Authors: Yahav Alon, Michael Anastos
Speaker: Yahav Alon
➤ Title: Completion to Hamiltonicity and pancyclicity in G(n,p)
Abstract: Is it well known since the eighties that a random graph \(G(n,p)\) becomes typically Hamiltonian for the edge probability \(p(n)\) around \((\log n+\log \log n)/n\). It is thus natural to ask how far is \(G\) drawn from \(G(n,p)\), with \(p(n)\) below the Hamiltonicity threshold, from being Hamiltonian, where we use edge distance from a nearest Hamiltonian graph as the measure. Improving upon an earlier result of Y. Alon and Krivelevich, we provide an accurate answer to this question for a wide range of \(p(n)\). We further show that in this range, typically, \(G(n,p)\) has a nearest Hamiltonian graph which is also pancyclic. A joint work with Michael Anastos (IST Austria).

Author: Michael Anastos
Speaker: Michael Anastos
➤ Title: Constructing Hamilton cycles efficiently
Abstract: Starting with the empty graph on \([n]\), at each round, a set of \(K=K(n)\) edges is presented chosen uniformly at random from the ones that have not been presented yet. We are then asked to choose at most one of the presented edges and add it to the current graph. Our goal is to construct a small Hamiltonian graph within few rounds. We show that in this process, one can build a Hamiltonian graph of size \((1+o(1))n\) in \((1+o(1))(1+(\log n)/2K) n\) rounds w.h.p. The case \(K=1\) answers a question of Frieze, Krivelevich and Michaeli on building a Hamiltonian graph in the random graph process in an online fashion efficiently. The case \(K=\Theta(\log n)\) implies that the Hamiltonicity threshold of the corresponding Achlioptas process is at most \((1+o(1))(1+(\log n)/2K) n\). This matches the \((1-o(1))(1+(\log n)/2K) n\) lower bound due to Krivelevich, Lubetzky and Sudakov. Our proof relies on a robust Hamiltonicity property of the strong \(4\)-core of the binomial random graph which we use as a black-box. This property allows it to absorb paths covering vertices outside the strong \(4\)-core into a cycle.

Authors: Patrick Bennett, Andrzej Dudek, Sean English
Speaker: Patrick Bennett
➤ Title: Random processes for generalized Ramsey problems
Abstract: A \((p, q)\)-coloring of \(K_n\) is an edge coloring such that every set of \(p\) vertices spans at least \(q\) different colors. We let \(f(n, p, q)\) be the smallest possible number of colors in such a coloring. In this talk we will discuss a new upper bound on \(f(n, p, q)\) that was recently obtained using a random coloring process.

Authors: Anton Bernshteyn, Anush Tserunyan, Spencer Unger
Speaker: Anton Bernshteyn
➤ Title: Flows on a torus
Abstract: The Banach--Tarski theorem famously asserts that a ball in \(\mathbb{R}^3\) can be decomposed into finitely many pieces that can be moved by isometries to form two copies of the original ball. This result is a starting point in a rich theory that studies similar equidecomposition problems. As recently demonstrated by Marks, Unger, and others, an important intermediate step in many equidecomposition constructions is to obtain a flow in an auxiliary graph with certain properties. In this talk, I will present a general method that yields a large family of such flows with different prescribed combinatorial behavior. This is joint work with Anush Tserunyan and Spencer Unger.

Authors: Abhinav Bhardwaj, Van Vu
Speaker: Abhinav Bhardwaj
➤ Title: Entry-wise dissipation for singular vector perturbation bounds
Abstract: Consider a random, symmetric perturbation of a symmetric, low rank matrix. The goal of this paper is to present entry-wise bounds on the perturbation of the singular vectors. In particular, our result shows that, under common incoherence assumptions, the entry-wise error is evenly dissipated. This improves a number of previous results and has algorithmic applications for many well known clustering problems, including the hidden clique, planted coloring, and planted bipartition.

Authors: Matija Bucic, Tung Nguyen, Alex Scott, Paul Seymour
Speaker: Matija Bucic
➤ Title: Towards the Erdős-Hajnal Conjecture
Abstract: The Erdős-Hajnal conjecture is one of the most classical and well-known problems in extremal and structural combinatorics dating back to 1977. It asserts that in stark contrast to the case of a general \(n\)-vertex graph if one imposes even a little bit of structure on the graph, namely by forbidding a fixed graph \(H\) as an induced subgraph, instead of only being able to find a polylogarithmic size clique or an independent set one can find one of polynomial size. Despite being the focus of considerable attention over the years the conjecture remains open. We obtain a first improvement to the classical lower bound of \(2^{\Omega(\sqrt{\log n})}\), due to Erdős and Hajnal from 1977, which applies for any forbidden graph \(H\). Namely, we show that any \(H\)-free \(n\)-vertex graph contains a clique or an independent set of size at least \(2^{\Omega(\sqrt{\log n \log \log n})}\). This bound arises from reaching a certain natural "halfway" point in the classical approach for attacking the full conjecture, and was suggested as an intermediate goal by Conlon, Fox and Sudakov. In addition, we break this barrier in the smallest open case of the conjecture. Namely, we show that any \(P_5\)-free \(n\) vertex graph contains a clique or an independent set of size at least \(2^{\Omega(\log n)^{2/3}}\). This gives rise to the same improvement for an infinite family of graphs.

Authors: Boris Bukh, Amzi Jeffs
Speaker: Boris Bukh
➤ Title: Enumeration of interval graphs and \(d\)‑representable complexes
Abstract: How many essentially distinct ways are there to arrange \(n\) convex sets in \(\mathbb{R}^d\)? Here, ‘essentially distinct’ means ‘with different intersection pattern’. We discuss this question both in the dimension \(1\), where it amounts to counting the interval graphs, and in higher dimensions.

Author: Charles Burnette
Speaker: Charles Burnette
➤ Title: Fixed-point free involution factorizations
Abstract: The problem of factoring random permutations into the product of two involutions with a prescribed number of fixed points has connections to arithmetic dynamics, comparative genomics, and the analysis of perfect shuffle algorithms. Given a permutation \(\sigma\) of \([n],\) let \(\mathsf{invol}(\sigma)\) denote the number of ways that \(\sigma\) can be expressed as a composition of two involutions of \([n].\) In a joint paper with Eric Schmutz, we proved that \(\mathsf{invol}\) is asymptotically lognormal for uniform random permutations. In this talk though, we will consider the permutations that admit fixed-point free involution factorizations, which are precisely the permutations with an even number of \(k\)-cycles for \(k = 1, 2, \ldots.\) Through a combination of singularity analysis, the method of moments, and an appeal to the classical Shepp-Lloyd model, we will see that the distribution of the number of fixed-point free factorizations for such permutations has a discrete limit law instead of a Gaussian one.

Author: Ting-Wei Chao
Speaker: Ting-Wei Chao
➤ Title: Empty Boxes, Nets, and Convex Holes
Abstract: What's the best way to put \(n\) points in \([0,1]^d\) to avoid large empty axis-parallel boxes? We gave a good construction which is a random subset of the Halton–Hammersley construction. The same idea also helps us to construct an approximation version of \((t,m,s)\)-nets. These constructions can be transformed into point sets in \(\mathbb{R}^d\) that avoid large convex holes.

Based on joint work with Boris Bukh and Ron Holzman.

Authors: József Balogh, Ce Chen, Grace McCourt, Cassie Murley
Speaker: Ce Chen
➤ Title: Ramsey-Turán problems with small independence numbers
Abstract: Given a graph \(H\) and a function \(f(n)\), the Ramsey-Turán number \(RT(n,H,f(n))\) is the maximum number of edges in an \(n\)-vertex \(H\)-free graph with independence number at most \(f(n)\). For \(H\) being a small clique, many results about \(RT(n,H,f(n))\) are known and we focus our attention on \(H=K_s\) for \(s\leq 13\). By applying Szemerédi's Regularity Lemma, the dependent random choice method and some weighted Turán-type results, we prove that these cliques have the so-called phase transitions when \(f(n)\) is around the inverse function of the off-diagonal Ramsey number of \(K_r\) versus a large clique \(K_n\) for some \(r\leq s\).

Authors: Domagoj Bradac, Micha Christoph, Lior Gishboliner
Speaker: Micha Christoph
➤ Title: Minimum Degree Threshold for \(H\)-factors with High Discrepancy
Abstract: Given a graph \(H\), a perfect \(H\)-factor in a graph \(G\) is a collection of vertex-disjoint copies of \(H\) spanning \(G\). K{\"u}hn and Osthus showed that the minimum degree threshold for a graph \(G\) to contain a perfect \(H\)-factor is either given by \(1-1/\chi(H)\) or by \(1-1/\chi_{cr}(H)\) depending on certain natural divisibility considerations. Given a graph \(G\) of order \(n\), a \(2\)-edge-coloring of \(G\) and a subgraph \(G'\) of \(G\), we say that \(G'\) has high discrepancy if it contains significantly (linear in \(n\)) more edges of one color than the other. Balogh, Csaba, Pluhar and Treglown asked for the minimum degree threshold guaranteeing that every 2-edge-coloring of \(G\) has an \(H\)-factor with high discrepancy and they settled the case where \(H\) is a clique. In this talk, we give a different prove for the case where \(H\) is a clique and discuss the ideas behind resolving this question completely.

Authors: Asaf Cohen Antonir, Asaf Shapira
Speaker: Asaf Cohen Antonir
➤ Title: Bounding the number of odd paths in planar graphs via convex optimization
Abstract: Let \(N_{\mathcal{P}}(n,H)\) denote the maximum number of copies of \(H\) in an \(n\) vertex planar graph. The problem of bounding this function for various graphs \(H\) has been extensively studied since the 70's. A special case that received a lot of attention recently is when \(H\) is the path on \(2m+1\) vertices, denoted \(P_{2m+1}\). We will sketch a proof of the following estimation: \( N_{\mathcal{P}}(n,P_{2m+1})=O(m^{-m}n^{m+1})\;. \) This improves upon the previously best known bound (of Cox and Martin) by a factor \(e^{m}\). The proof uses graph theoretic arguments together with (simple) arguments from the theory of convex optimization.

Authors: Anurag Bishnoi, Simona Boyadzhiyska, Shagnik Das, Yvonne den Bakker
Speaker: Shagnik Das
➤ Title: Covering grids with multiplicity
Abstract: Given a finite grid in \(\mathbb{R}^2\), how many lines are needed to cover all but one point at least \(k\) times? Problems of this nature have been studied for decades, with a general lower bound having been established by Ball and Serra. In this talk, we will solve this problem for various types of grids, in particular showing the tightness of the Ball-Serra bound when one side is much larger than the other. In other cases, we prove new lower bounds that improve upon Ball-Serra and provide an asymptotic answer for almost all grids. For the standard grid \(\{0,\dots,n-1\} \times \{0,\dots,n-1\}\), we prove nontrivial upper and lower bounds on the number of lines needed. To prove our results, we combine linear programming duality with some combinatorial arguments. This is joint work with Anurag Bishnoi, Simona Boyadzhiyska and Yvonne den Bakker.

Authors: Stoyan Dimitrov, Luz Grisales, Yan Zhuang
Speaker: Stoyan Dimitrov
➤ Title: BFS vs DFS for a random target node in plane trees
Abstract: Assume that we are at the root of an unknown plane tree T with n edges. Our goal is to find a specific target node x in T. If we do not have any prior information about x, it is reasonable to use either BFS or DFS to search for x. We investigate the question, which of the two algorithms is a better choice, if x is a random node at a given level l? When l is small, BFS should perform better, while DFS will certainly have an advantage for big l. But where exactly is the threshold? We obtain explicit formulas for the expected number of steps when using both BFS and DFS for given n and l. This allows us to obtain a nontrivial upper bound for the threshold. The problem when l is known in advance is also considered. We ask some other important further questions.

Authors: Sahar Diskin, Joshua Erde, Mihyun Kang, Michael Krivelevich
Speaker: Sahar Diskin
➤ Title: Supercritical percolation on the hypercube - typical properties of the giant component
Abstract: A random subgraph of the binary \(d\)-dimensional hypercube \(Q^d\) is one of the most classical and researched models of bond (edge) percolation. In this model, the base graph is the binary hypercube \(Q^d\) (vertices are 0/1-vectors with \(d\) coordinates, two are adjacent if they differ in exactly one coordinate), and each edge of \(Q^d\) is retained independently with probability \(p=p(d)\). It is known since the classical work of Ajtai, Komlos and Szemeredi in 1982 that the model undergoes phase transition at \(p=1/d\), and in the supercritical regime \(p=(1+\epsilon)/d, \epsilon>0\) a small constant, there is typically a unique component of size linear in \(|V(Q^d)|=2^d\), the so-called giant component. We investigate typical combinatorial properties of the giant component, with an emphasis on, and a key being, its typical expansion. In particular, we determine up to small polylogarithmic factors in \(d\) the typical diameter and mixing time of a lazy random walk on the giant. Our methods extend smoothly to the general setup of supercritical percolation on high-dimensional product graphs. A joint work with Joshua Erde, Mihyun Kang and Michael Krivelevich.

Authors: Colin Cooper, Martin Dyer, Catherine Greenhill
Speaker: Martin Dyer
➤ Title: Encouraging triangles in graphs with given degree sequence
Abstract: In a uniform random graph with given degree sequence, if the maximum degree is not too large then the number of triangles in the graph is approximately Poisson. Thus a uniform random graph is not a good model for networks which contains many triangles, such as social networks. So how can we generate graphs with more triangles?

The switch chain is a well-studied Markov chain on the set of all graphs with given degrees, having a uniform stationary distribution. The triangle switch chain is a variant, designed to generate random graphs with given degree sequence, but having more triangles than appear under the uniform distribution. Transition probabilities of the chain are governed by a parameter \(\lambda\), with larger values encouraging more triangles. The first question is whether this chain is even ergodic. We show that this is the case whenever the minimum degree is at least 3.

If so, is the chain rapidly mixing? We study the mixing rate of a Metropolis version, in which a graph \(G\) has stationary probability proportional to \(\lambda^{t(G)}\), where \(t(G)\) is the number of triangles in \(G\).

We show that this chain is rapidly mixing if \(\lambda\) and the maximum degree of \(G\) are not too large, and the number of triangles remains approximately Poisson.

Author: Charilaos Efthymiou
Speaker: Charilaos Efthymiou
➤ Title: Spectral Independence Beyond Uniqueness
Abstract: We present novel results for fast mixing of Glauber dynamics using the newly introduced and powerful Spectral Independence method from [Anari, Liu, Oveis-Gharan: FOCS 2020]. In our results, the parameters of the Gibbs distribution are expressed in terms of the spectral radius of the adjacency matrix of G, or that of the Hashimoto non-backtracking matrix. The analysis relies on new techniques that we introduce to bound the maximum eigenvalue of the pairwise influence matrix I_G for the two spin Gibbs distribution \mu. There is a common framework that underlies these techniques which we call the topological method. The idea is to systematically exploit the well-known connections between I_G and the topological construction called Tree of Self-avoiding walks. Our approach is novel and gives new insights to the problem of establishing spectral independence for Gibbs distributions. More importantly, it allows us to derive new -- improved -- rapid mixing bounds for Glauber dynamics on distributions such as the Hard-core model and the Ising model for graphs that the spectral radius is smaller than the maximum degree.

Author: Chaim Even-Zohar
Speaker: Chaim Even-Zohar
➤ Title: Explicit Existentially-Complete Hypergraphs
Abstract: A hypergraph G is k-existentially complete (k-ec) if for every induced subhypergraph H on k vertices of G, every potential extension of H to a hypergraph on k+1 vertices is realized by at least one additional vertex in the hypergraph G. Random hypergraphs are k-ec with high probability. Graham--Spencer (1971), Blass--Exoo--Harary (1981), and Bollobas--Thomason (1981) showed that Paley graphs and tournaments also possess the analogous property of k-existential completeness. However, standard number-theoretic constructions of explicit quasirandom hypergraphs are not k-ec. We present an infinite family of explicit quasirandom k-ec hypergraphs, obtained by "iterating" the Paley construction in a certain manner. This construction answers a question posed by Dugald Macpherson (2011) in the model-theory literature. The construction of k-ec hypergraphs also gives rise to explicit k-ec simplicial complexes, which are defined analogously. We explore the geometric and topological properties of k-ec simplicial complexes in general. Based on joint work with Michael Farber and Lewis Mead.

Authors: David Conlon, Jacob Fox, Huy Pham, Liana Yepremyan
Speaker: Jacob Fox
➤ Title: Ramsey Cayley graphs, random graph models, and information theory
Abstract: A graph is *Ramsey* if its largest clique or independent set is of size logarithmic in the number of vertices. While almost all graphs are Ramsey, there is still no known explicit construction of Ramsey graphs. Alon conjectured that every finite group has a Ramsey Cayley graph. We prove that for almost all \(n\), all abelian groups of order \(n\) satisfy Alon's conjecture. We also verify a conjecture of Alon and Orlitsky motivated by information theory that there are self-complementary Ramsey Cayley graphs. We further prove general results for clique numbers of random graph models. Along the way, we study some fundamental problems in additive combinatorics, and discover that group structure is superfluous for these problems.

Authors: Alan Frieze, Wes Pegden
Speaker: Alan Frieze
➤ Title: Sequentially constrained Hamilton Cycles in random graphs
Abstract: We discuss the existence of Hamilton cycles in the random graph \(G_{n,p}\) where there are restrictions caused by (i) coloring sequences, (ii) a subset of vertices must occur in a specific order and (iii) there is a bound on the number of inversions in the associated permutation.

Authors: David Eppstein, Daniel Frishberg
Speaker: Daniel Frishberg
➤ Title: Improved mixing for the convex polygon triangulation flip walk
Abstract: We prove that the well-studied triangulation flip walk on a convex point set mixes in time \(O(n^3 log^3 n)\), the first progress since McShine and Tetali’s \(O(n^5 log n)\) bound in 1997. In the process we give lower and upper bounds of respectively \(Omega(1/(sqrt n log n))\) and \(O(1/sqrt n)\)---asymptotically tight up to an O(log n) factor—for the expansion of the associahedron graph \(K_n\). To obtain these results, we introduce a framework consisting of a set of sufficient conditions under which a given Markov chain mixes rapidly. This framework is a purely combinatorial analogue that in some circumstances gives better results than the projection-restriction technique of Jerrum, Son, Tetali, and Vigoda.

Authors: Jane Gao, Peter Nelson
Speaker: Jane Gao
➤ Title: Minors of random representable matroid over finite fields
Abstract: Consider a random n by m matrix A over GF(q) where every column has k nonzero elements, and let M[A] be the matroid represented by A. In the case that q=2, Cooper, Frieze and Pegden (RSA 2019) proved that given a fixed binary matroid N, if k is sufficiently large, and m/n is sufficiently large (both depending on N), then a.a.s. M[A] contains N as a minor. We improve their result by determining the sharp threshold (of m/n) for the appearance of a fixed q-nary matroid N as a minor of M[A], for every k \(\ge\) 3, and every prime q. This is joint work with Peter Nelson.

Author: Nikita Gladkov
Speaker: Nikita Gladkov
➤ Title: A strong FKG inequality for multiple events
Abstract: We give an extension of the FKG inequality to the case of multiple events with equal pairwise intersections. We then apply this inequality to resolve Jeff Kahn's question on positive associated (PA) measures.

Authors: Benjamin Gunby, Xiaoyu He, Bhargav Narayanan, Sam Spiro
Speaker: Benjamin Gunby
➤ Title: Antichain Codes
Abstract: Let \(S\) be a subset of the Boolean cube \(2^{[n]}\) that is both an antichain and a distance-\(r\) code. How large can \(S\) be? I will discuss the solution to this problem and its connections with combinatorial proofs of anticoncentration theorems. Based on joint work with Xiaoyu He, Bhargav Narayanan, and Sam Spiro.

Authors: Candida Bowtell, Robert Hancock, Joseph Hyde
Speaker: Robert Hancock
➤ Title: A resolution of the Kohayakawa Kreuter conjecture for almost all pairs of graphs
Abstract: We study asymmetric Ramsey properties of the random graph \(G(n,p)\). For \(r \geq 2\) and a graph \(H\), Rödl and Ruciński (1993-5) provided the asymptotic threshold for \(G(n,p)\) to have the following property: whenever we \(r\)-colour the edges of \(G(n,p)\) there exists a monochromatic copy of \(H\) as a subgraph. In 1997, Kohayakawa and Kreuter conjectured an asymmetric version of this result, where one replaces \(H\) with a set of graphs \(H_1,\dots,H_r\) and we seek the threshold for when every \(r\)-colouring contains a monochromatic copy of \(H_i\) in colour \(i\) for some \(i \in \{1,\dots,r\}\).

The \(1\)-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij in 2020. We extend upon the many partial results for the \(0\)-statement, by resolving it for almost all cases. We reduce the remaining cases to a deterministic colouring problem.

Authors: Asaf Ferber, Liam Hardiman
Speaker: Liam Hardiman
➤ Title: A Quantum Algorithm for Learning a Hidden Graph of Bounded Degree
Abstract: We are presented with a graph, \(G\), on \(n\) vertices whose edges are completely unknown. Our goal is to learn the edges of \(G\) with as few queries to an oracle as possible. When we submit a set \(S\) of vertices to the oracle, it tells us whether or not \(S\) induces at least one edge in \(G\). This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of \(O(m \log n)\) for a general graph \(G\) with \(m\) edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where \(G\) has maximum degree \(d\), Montanaro and Shao recently presented an algorithm that learns the edges of \(G\) in at most \(\tilde{O}(d^2m^{3/4})\) quantum queries. This gives an upper bound of \(\tilde{O}(m^{3/4})\) quantum queries when \(G\) is a matching or a Hamiltonian cycle, which is significantly larger than the lower bound of \(\Omega(\sqrt{m})\) queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where \(G\) has bounded degree. In particular, we present an algorithm that learns cycles and matchings in \(\tilde{O}(\sqrt{m})\) quantum queries, matching the theoretical lower bound up to logarithmic factors.

Authors: David Conlon, Jacob Fox, Xiaoyu He, Dhruv Mubayi, Andrew Suk, Jacques Verstraete
Speaker: Xiaoyu He
➤ Title: Set-coloring Ramsey numbers via codes
Abstract: The set-coloring Ramsey number \(R(n; r, s)\) is the minimum \(N\) such that if every edge of the complete graph \(K_N\) receives a set of \(s\) colors from a palette of \(r\) colors, then there must be a monochromatic clique of size \(n\). Determining the growth rate of \(R(n;r,s)\) when \(s=1\) (the classical multicolor Ramsey number) and when \(s=r-1\) are both famous open questions in Ramsey theory. We solve the problem away from these two extremes by showing that if \(s/r\) is bounded away from \(0\) and \(1\), then \(R(n;r,s) = 2^{\Theta(nr)}\). The key idea for the lower bound is to restrict the product construction to a subgraph induced on an error-correcting code.

Author: Pawel Hitczenko
Speaker: Pawel Hitczenko
➤ Title: A class of polynomial recurrences resulting in \(N(n/log n, n/log^2 n)\) asymptotic normality
Abstract: We consider sequences of polynomials that satisfy differential--difference recurrences. Polynomials satisfying such recurrences frequently appear as generating polynomials of integer valued random variables that are of interest in discrete mathematics. It is, therefore, of interest to understand the properties of such polynomials and their probabilistic consequences. We identify a class of polynomial recurrences that lead to a normal law with the expected value and the variance proportional to \(n/\log~n\) and \(n/\log^2n\), respectively. Examples include Stirling number of the second kind and other polynomials concerning set partitions as well as polynomials related to Whitney numbers of Dowling lattices. This complements the case of Eulerian type recurrences which lead to asymptotically normal distribution with both parameters proportional to \(n\).

Authors: Sahar Diskin, Ilay Hoshen, Maksim Zhukovskii
Speaker: Ilay Hoshen
➤ Title: Saturation Number in Random Graphs
Abstract: For graphs \(G\) and \(F\), the saturation number \(\text{sat}(G,F)\) is the minimum number of edges in an inclusion-maximal \(F\)-free subgraph of \(G\). In 2017, KorÃ¡ndi and Sudakov initiated the study of saturation in random graphs. They showed that for constant \(p\in (0,1)\), whp \(\text{sat}\left(G(n,p),K_s\right)=\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n\). We show that for every graph \(F\) and every constant \(p\in (0,1)\), whp \(\text{sat}\left(G(n,p), F\right)=O(n \log n)\). We conjecture that \(\text{sat}\left(G(n,p), F\right)=\Theta(n \log n)\) if every edge of \(F\) belongs to a triangle, and \(\text{sat}\left(G(n,p), F\right)=O(n)\) otherwise. We show that the conjecture is true for all \(F\) having all edges in triangles and for all bipartite graphs. We also prove the conjecture for some other families of graphs and show that the saturation number equals \(\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n\) for all complete multipartite \(F\) and \(p \geq \frac{1}{2}\).

Author: Mark Huber
Speaker: Mark Huber
➤ Title: Tight relative error estimation in the mean of Bernoulli random variables
Abstract: Given a stream of independent, identically distributed Bernoulli random variables of mean \(p\), consider the problem of estimating \(p\) within a specified relative error \(\epsilon\) with a specified failure probability \(\delta\). Until now, the Gamma Bernoulli Approximation Scheme (GBAS) was the method that accomplished this goal using the smallest number of average samples, but this failed to include a factor of \(1 - p\) in the number of samples needed. In this work, a new method is introduced that captures this missing factor as \(\epsilon\) and \(\delta\) go to zero. The process uses a two-stage process together with some novel inequalities to get rigorous bounds on the error probability.

Authors: António Girão, Eoin Hurley
Speaker: Eoin Hurley
➤ Title: Induced Bounded Degree Trees in Sparse Graphs.
Abstract: In this talk we will show how to find any induced tree of bounded degree and linear order in sparse graphs of high average degree. In particular any tree of max degree \(\Delta\) and order at most \(C_\Delta n\) is, with high probability, an induced subgraph of \(G(n,d)\), where \(d\) is a constant that is sufficiently large relative to \(\Delta\). This shows, for the first time, that induced and size induced ramsey numbers of bounded degree trees are linear. A byproduct of our proof is an online algorithm to embed such trees.

Author: R. Amzi Jeffs
Speaker: R. Amzi Jeffs
➤ Title: Colorful Words and d-Tverberg Complexes
Abstract: For every fixed d, we classify the intersection combinatorics that must arise in every sufficiently large general position point set in R^d. Here, by "intersection combinatorics" we mean the nerve complex of convex hulls whose vertices are chosen from the point set. Such complexes are called weakly d-Tverberg complexes, and generalize the recently introduced d-Tverberg complexes of De Loera, Hogan, Oliveros, and Yang. We use our classification to answer a question of De Loera, Hogan, Oliveros, and Yang, by showing that for every fixed d there exist graphs that are not weakly d-Tverberg. This talk is based on joint work with Florian Frick.

Authors: Ryan Jeong, Steven J. Miller
Speaker: Ryan Jeong
➤ Title: On the Relative Sizes of Complements of Generalized Sumsets
Abstract: Given a subset \(A\) of \(\{1, 2, \ldots, N\}\), its sum and difference sets are \begin{align*} & A+A \ = \ \{a_1 + a_2: a_1, a_2 \in A\}, & A-A \ = \ \{a_1 - a_2: a_1, a_2 \in A\}. \end{align*} A fundamental problem of the subject is to understand the relative sizes of these sets. Martin and O'Bryant proved that a positive proportion of the \(2^N\) subsets \(A\) of \(\{1, 2, \ldots, N\}\) are sum-dominated for \(N \geq 15\), while Hegarty and Miller established a threshold phenomenon if we independently include elements of \(\{1,2,\ldots,N\}\) in \(A\) with probability \(p(N)\): \(\frac{|A-A|}{|A+A|} \sim 2\) if \(p(N) = o(N^{-1/2})\), this ratio converges in probability to computable constants \(\theta_c\) when \(p(N) = c N^{-1/2}\) (with \(\theta_c\) decreasing to 1 as \(c \to \infty\)), and the ratio of complements \(\frac{|(A+A)^c|}{|(A-A)^c|} \sim 2\) if \(N^{-1/2} = o(p(N))\). More recently, Hogan and Miller studied the relative sizes of generalized sumsets \(A_{s,d} = A+A+\cdots+A-A-A-\cdots-A\), with \(s\) sums and \(d\) differences, \(s+d = h\) and \(p(N) =cN^{-\delta}\). They generalized the results of Hegarty and Miller in the sparse \(A\) regime, namely by establishing that \(\frac{|A_{s_1,d_1}|}{|A_{s_2,d_2}|} \sim \frac{s_2!d_2!}{s_1!d_1!}\) if \(\delta > \frac{h-1}{h}\). We complete this inquiry by showing that \(\frac{|A_{s_1,d_1}|}{|A_{s_2,d_2}|}\) converges in probability to a ratio converging to \(1\) as \(c \to \infty\) when \(p(N) = cN^{-\frac{h-1}{h}}\), and that if \(\delta < \frac{h-1}{h}\), \begin{align*} \frac{|A_{s_1,d_1}^c|}{|A_{s_2,d_2}^c|} \sim \left(\frac{s_1!d_1!}{s_2!d_2!}\right)^{\frac{1}{h-1}}. \end{align*} Our methods rely on a seminal Poisson convergence theorem due to Arratia, Goldstein, and Gordon, as well as the martingale machinery of Vu.

Authors: Recep Altar Çiçeksiz, Zhihan Jin, Eero Räty, István Tomon
Speaker: Zhihan Jin
➤ Title: Exponential Erdős-Szekeres theorem for matrices
Abstract: In 1993, Fishburn and Graham established the following qualitative extension of the classical ErdÅ‘s-Szekeres theorem. If \(N\) is sufficiently large with respect to \(n\), then any \(N\times N\) real matrix contains an \(n\times n\) submatrix in which every row and every column is monotone. We prove that the smallest such \(N\) is at most \(2^{n^{4+o(1)}}\), greatly improving the previously best known double-exponential upper bound, and getting close to the best known lower bound \(n^{n/2}\). In particular, we prove the following surprising sharp transition in the asymmetric setting. On one hand, every \(8n^2\times 2^{n^{4+o(1)}}\) matrix contains an \(n\times n\) submatrix, in which every row is mononote. On the other hand, there exist \(n^{2}/6\times 2^{2^{n^{1-o(1)}}}\) matrices containing no such submatrix.

Authors: Amarja Kathapurkar, Richard Mycroft
Speaker: Amarja Kathapurkar
➤ Title: Transversal cycle factors in multipartite graphs
Abstract: Let \(G\) be an \(n\)-vertex graph and \(H\) a \(k\)-vertex graph, with \(k \mid n\). We say that \(G\) contains an \(H\)-factor if \(G\) contains \(n/k\) vertex-disjoint copies of \(H\). In this talk, we discuss an analogue of this notion in the multipartite setting, in the case when \(H\) is a cycle.

More precisely, let \(G\) be a \(k\)-partite graph with vertex classes \(V_1, \ldots, V_k\), each of size \(n\). We show that for any even \(k \geq 4\), if \(n\) is sufficiently large and \(\delta(G[V_i,V_{i+1}]) \geq (1+1/k)n/2\) for each \(i \in [k]\) (indices taken with addition modulo \(k\)), then \(G\) contains a \(C_k\)-factor in which each copy of \(C_k\) contains exactly one vertex from each vertex class \(V_i\). We call this a transversal \(C_k\)-factor. When \(k\) is odd, we show that under the same conditions, either \(G\) contains a transversal \(C_k\)-factor, or \(G\) is `close to' extremal. In the case when \(k\) is even, this gives an exact version of an earlier asymptotic result by Ergemlidze and Molla, and resolves independent conjectures of Fischer and Häggkvist.

This is joint work with Richard Mycroft.

Authors: Kyriakos Katsamaktsis, Shoham Letzter
Speaker: Kyriakos Katsamaktsis
➤ Title: Rainbow Hamilton cycles in randomly coloured perturbed graphs
Abstract: Let G be a graph of order n with linear minimum degree, and suppose that we ‘perturb’ G by adding the edges of the binomial random graph on the same vertex set. It is well known that if the random graph has edge probability at least C/n for some constant C, then with high probability the perturbed graph is Hamiltonian. We show that if each edge of the perturbed graph gets a colour independently and uniformly at random from a set of n colours, then with high probability the perturbed graph has a rainbow Hamilton cycle, i.e. one with each edge having a different colour. This talk is based on joint work with Shoham Letzter.

Author: Brett Kolesnik
Speaker: Brett Kolesnik
➤ Title: The asymptotic number of score sequences
Abstract: A tournament is an orientation of the complete graph. The score sequence lists the out-degrees in non-decreasing order. Works by Erdős and Moser, Winston and Kleitman, and Kim and Pittel bounded the number of score sequences. In this talk, we locate the precise asymptotics. These agree numerically with those conjectured by Takács. We will discuss connections to geometry, renewal theory, infinitely divisible probability distributions, the Erdős–Ginzburg–Ziv numbers, and random lattice walks.

Based on arXiv:2209.13563 (Combinatorica, in press).

Authors: Petra Berenbrink, Max Hahn-Klimroth, Dominik Kaaser, Lena Krieg, Malin Rau
Speaker: Lena Krieg
➤ Title: Inference of a Rumor’s Source in the Independent Cascade Model
Abstract: We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al. [2003]. In this model, a small subset of nodes from a network are the source of a rumor. In discrete time steps, each informed node "infects" each of its uninformed neighbors with probability \(p\). While many facets of this process are studied in the literature, less is known about the inference problem: given a number of infected nodes in a network, can we learn the source of the rumor? In the context of epidemiology this problem is often referred to as patient zero problem. It belongs to a broader class of problems where the goal is to infer parameters of the underlying spreading model, see, e.g., Lokhov [NeurIPS’16] or Mastakouri et al. [NeurIPS’20]. In this work we present a maximum likelihood estimator for the rumor’s source, given a snapshot of the process in terms of a set of active nodes \(X\) after \(t\) steps. Our results show that, for cycle-free graphs, the likelihood estimator undergoes a non-trivial phase transition as a function \(t\). We provide a rigorous analysis for two prominent classes of acyclic network, namely \(d\)-regular trees and Galton-Watson trees, and verify empirically that our heuristics work well in various general networks.

Authors: Tom Johnston, Gal Kronenberg, Alexander Roberts, Alex Scott
Speaker: Gal Kronenberg
➤ Title: Shotgun reconstruction of random graphs
Abstract: We say that a graph G is reconstructible from its r-neighbourhoods if all graphs H having the same collection of r-balls as G up to isomorphism, are isomorphic to G. We are interested in the reconstruction of the Erdo ̋s–Renyi graph G(n,p) for a wide range of values of r, aiming to determine the values of p for which G(n, p) is r-reconstructible with high probability. Mossel and Ross showed that the the graph G(n,p) can be reconstructed from its 3-neighbourhoods with high probability provided that p ≫ log^2(n)/n. Later, Gaudio and Mossel studied reconstruction from the 1- and 2-neighbourhoods, giving bounds on the values of p for which G(n,p) is reconsructible. For 1-neighbourhoods, this was improved very recently by Huang and Tikhomirov who determined the correct threshold up to logarithmic factors, around n^{−1/2}. In this talk we will show new bounds on p for the r-reconstructibility problem in G(n, p). We improve the bounds for 2-neighbourhoods given by Gaudio and Mossel by polynomial factors. We also improve the result of Huang and Tikhomirov for 1-neighbourhoods, showing that the logarithmic factor is necessary. Finally, we determine the exact thresholds for r-reconstructibility for r ≥ 3. This is a joint work with Tom Johnston, Alexander Roberts, and Alex Scott.

Authors: József Balogh, Robert Krueger
Speaker: Robert Krueger
➤ Title: Sharp threshold for random Sperner's Theorem
Abstract: Sperner's Theorem states that the largest antichain in the Boolean lattice is a middle layer. If we now take a random subset of the Boolean lattice, keeping each member independently with probability \(p\), what is the largest antichain of this random poset? Hamm and Kahn proved that for some constant \(p<1\), the largest antichain is still (whatever remains of) a middle layer. We extend this result to the optimal \(p=3/4\), and we characterize the largest antichains for \(p>1/2\). Our proof uses some variations on Sapozhenko's graph containers. I will also discuss related (open) problems.

Authors: Ehud Friedgut, Eden Kuperwasser, Wojciech Samotij, Mathias Schacht
Speaker: Eden Kuperwasser
➤ Title: Sharp thresholds for Ramsey properties
Abstract: Given an integer \(r \ge 2\) and a graph \(H\), we say that a graph \(G\) is \(r\)-Ramsey for \(H\) if any \(r\)-coloring of the edges of \(G\) admits a monochromatic copy of \(H\). In their seminal paper, Rödl and Ruciński located the threshold for this property for any \(H\) and \(r\), hence opening the door to the study of threshold phenomena in other Ramsey-type properties. In this talk we will discuss a unified approach to establish sharp thresholds for these properties, and apply it to the graph case. There, our methods show that the threshold is sharp for a family containing all cycles and cliques, and for any number of colors; this extends the results of Friedgut, Rödl, Ruciński, and Tetali, and of Schacht and Schulenburg.

Joint work with Ehud Friedgut, Wojciech Samotij, and Mathias Schacht.

Author: Manuel Lladser
Speaker: Manuel Lladser
➤ Title: Resolvability of Jaccard Metric Spaces
Abstract: Resolvability is a generalization of the notion of trilateration of the plane to an arbitrary metric space. Given a finite metric space \((X,d)\), a subset \(R=\{r_1,\ldots,r_k\}\subset X\) is said to resolve \((X,d)\) when the transformation \(x\longrightarrow\big(d(x,r_1),\ldots,d(x,r_k)\big)\), with \(x\in X\), is one-to-one. In particular, this transformation uniquely represents points in \(X\) as Euclidean vectors. Further, due to the triangular inequality, points close by in \(X\) are represented as vectors with similar coordinates in \(\mathbb{R}^k\). Resolving sets can therefore produce feature vectors for points in abstract metric spaces, which may find applications in classification problems of symbolic objects under suitably chosen metrics. Unfortunately, the problem of resolving optimally large metric spaces (i.e., minimizing the cardinality of \(R\)) is NP-complete. In fact, the state-of-the-art algorithm, the Information Content Heuristic (ICH), has complexity \(O(|X|^3)\) and is only guaranteed to find a resolving set of cardinality at most \(1+\big(1+o(1)\big)\cdot\ln|X|\) times the optimal one. In this talk, we use linear algebra and probabilistic arguments to find comparatively small resolving sets in Jaccard spaces, i.e., metric spaces of the form \((2^X,\text{Jac})\), where \(2^X\) is the power set of a finite set \(X\), and \(\text{Jac}\) is the Jaccard distance. Namely, for all \(A,B\subset X\), \(\text{Jac}(A,B):=|A\Delta B|/|A\cup B|\), where \(|\cdot|\) denotes cardinality and \(\Delta\) the symmetric difference of sets. This work is partially funded by the NSF grant No. 1836914.

Authors: Allan Lo, Viresh Patel, Mehmet Akif Yıldız
Speaker: Allan Lo
➤ Title: Cycle Partition of Dense Regular Digraphs and Oriented Graphs
Abstract: Magnant and Martin conjectured that every \(d\)-regular graph on \(n\) vertices can be covered by \(n/(d+1)\) vertex-disjoint paths. Gruslys and Letzter verified this conjecture in the dense case, even for cycles rather than paths. We prove the analogous result for directed graphs and oriented graphs, that is, for all \(\alpha>0\), there exists \(n_0=n_0(\alpha)\) such that every \(d\)-regular digraph on \(n\) vertices with \(d \ge \alpha n \) can be covered by at most \(n/(d+1)\) vertex-disjoint cycles. Moreover if \(G\) is an oriented graph, then \(n/(2d+1)\) cycles suffice. This also establishes Jackson's long standing conjecture for large \(n\) that every \(d\)-regular oriented graph on \(n\) vertices with \(n\leq 4d+1\) is Hamiltonian.

Authors: József Balogh, Ce Chen, Kevin Hendrey, Ben Lund, Haoran Luo, Casey Tompkins, Tuan Tran
Speaker: Haoran Luo
➤ Title: Maximal 3-wise Intersecting Families
Abstract: A family \(\mathcal{F}\) on ground set \([n]:=\{1,2,\ldots, n\}\) is *maximal \(k\)-wise intersecting* if every collection of at most \(k\) sets in \(\mathcal{F}\) has non-empty intersection, and no other set can be added to \(\mathcal{F}\) while maintaining this property. In 1974, Erdős and Kleitman asked for the minimum size of a maximal \(k\)-wise intersecting family. We answer their question for \(k=3\) and sufficiently large \(n\). We show that the unique minimum family is obtained by partitioning the ground set \([n]\) into two sets \(A\) and \(B\) with almost equal sizes and taking the family consisting of all the proper supersets of \(A\) and of \(B\).

This is joint work with József Balogh, Ce Chen, Kevin Hendrey, Ben Lund, Casey Tompkins, and Tuan Tran.

Author: Tamas Makai
Speaker: Tamas Makai
➤ Title: The dispersion process on complete graphs within the critical window
Abstract: In the synchronous dispersion process we move particles between the vertices of a graph according to the following rules. Initially every particle is assigned to a fixed origin vertex. In a step of the process every particle, which occupies a vertex with at least one other particle present moves to one of its neighbours uniformly at random at the same time. The remaining particles, that is the ones which are the sole occupant of a vertex, keep their position. The process stops once every particle is the sole occupant of a vertex. When the underlying graph is the complete graph on \(n\) vertices, Cooper, McDowell, Radzik, Rivera and Shiraga (2018) identified a phase transition in the running time of the process, when the number of initial particles is \(n/2\). In particular, with high probability, if the number of particles is less than \(n/2\) the process stops in a logarithmic number of steps, however an exponential number of steps is required when the number of particles is larger than \(n/2\). We analyse the process in the critical window around \(n/2\) in order to show that there is a smooth phase transition with respect to the running time and provide matching upper and lower bounds on the typical running time. This is joint work with Umberto De Ambroggio and Konstantinos Panagiotou.

Author: Shuhei Mano
Speaker: Shuhei Mano
➤ Title: Sampling from toric models and hypergeometric functions
Abstract: The toric model is an important class of stochastic models and sampling from toric models has various applications. The sampling problem is related to hypergeometric functions because the normalizing constant of the probability function is a multi-variable polynomial and satisfies a GKZ-hypergeometric system. In this talk, I will review several problems in which the relationship works effectively.

Authors: Alan Frieze, Michael Krivelevich, Peleg Michaeli
Speaker: Peleg Michaeli
➤ Title: Fast construction on a restricted budget
Abstract: We introduce a model of a controlled random graph process. In this model, the edges of the complete graph are ordered randomly and then revealed, one by one, to a player called Builder. He must decide, immediately and irrevocably, whether to purchase each observed edge. The observation time is bounded by parameter *t*, and the total budget of purchased edges is bounded by parameter *b*. Builder’s goal is to devise a strategy that, with high probability, allows him to construct a graph of purchased edges possessing a target graph property, all within the limitations of observation time and total budget.

In this talk, I will present results in this model for natural graph properties, such as connectivity, Hamiltonicity and containment of fixed-size subgraphs. In particular, I will describe a strategy for creating a Hamilton cycle at the hitting time for Hamiltonicity by purchasing linearly many edges; this substantially extends the classical hitting time result for Hamiltonicity due to Ajtai–Komlós–Szemerédi and Bollobás.

The talk is based on joint work with Alan Frieze and Michael Krivelevich.

Authors: Yoshiharu Kohayakawa, Rafael Miyazaki
Speaker: Rafael Miyazaki
➤ Title: Bounds for the threshold function of arithmetic progressions in sumsets of random sets
Abstract: Given a set \(A\), its sumset \(A+A\) is defined as the set of all sums of two elements, not necessarily distinct, in \(A\). Given a function \(p \colon \mathbb{N}\to [0,1]\), we consider the sequence of independent random sets \(\{A_n\}_{n\in \mathbb{N}}\), where \(A_n\) is obtained by choosing independently each integer \(1\le i \le n\) with probability \(p(n)\). We employ the classical probabilistic tools of the first and second moment methods as well as a recently proven theorem of Park and Pham, formerly known as the Kahnâ€“Kalai Conjecture, regarding the relationship between the threshold function and the expectation threshold of increasing properties in order to find lower and upper bounds for the threshold for the existence of arithmetic progressions of \(m(n)\) elements in the sumset of the random set \(A_n\).

Authors: Michael Molloy, Erlang Surya, Lutz Warnke
Speaker: Michael Molloy
➤ Title: The degree process is far from uniform
Abstract: Suppose you wish to generate a random graph on vertices \(v_1,...,v_n\) where the degree of each \(v_i\) is specified to be \(d_i\). Perhaps the most natural approach is: Repeatedly add an edge joining two vertices chosen uniformly from all non-adjacent pairs that are not yet full (i.e.\ whose current degrees are less than their specified degrees). The graph we obtain is not distributed uniformly amongst all graphs with the specified degree sequence (except for some trivial sequences). But is the distribution close to uniform in the sense that every property which holds with high probability in one model holds with high probability in the other? We answer that question in the negative for bounded degree sequences that are not regular or close to regular.

Author: Jiaxi Nie
Speaker: Jiaxi Nie
➤ Title: Random Turán numbers of some degenerate hypergraphs
Abstract: Let \(H\) be an \(r\)-uniform hypergraph. The random Turán number \(\mathrm{ex}(G^r_{n,p},H)\) is the maximum number of edges in an \(H\)-free subgraph of \(G^r_{n,p}\), where \(G^r_{n,p}\) is the Erdös-Rényi random \(r\)-graph with parameter \(p\). When \(H\) is not \(r\)-partite, \(\mathrm{ex}(G^r_{n,p},H)\) has been essentially determined independently by Conlon and Gower, and Schacht. In this talk, we introduce some recent results on random Turán numbers for some \(r\)-partite \(r\)-graphs, which include linear cycles, expansions of tight trees, and expansions of complete hypergraphs.

Authors: Laura Eslava, Sergio I. López, Marco L. Ortiz
Speaker: Marco L. Ortiz
➤ Title: Targeted cutting of random recursive trees
Abstract: *Increasing trees* are rooted trees, where each vertex has a unique label and the labels along paths away from the root are in increasing order. A *Random recursive tree* on \(n\) vertices (abbreviated as RRTs) is a tree chosen uniformly at random from the set of increasing trees with vertex labels \(\{1,\dots, n\}\). The idea of cutting random recursive trees was introduced by Meir and Moon in 1974. They studied the following procedure: Start with a random recursive tree on \(n\) vertices. Choose an edge at random and remove it, along with the cut subtree that does not contain the root. Repeat until the remaining tree consists only of the root; at which point, we say that the tree has been *deleted*. Let \(X_n\) be the number of edge removals needed to delete a RRT with \(n\) vertices. The random variable \(X_n\) has been thoroughly studied and analogous variables under distinct models of random trees have been analyzed; in particular, \(X_n\) grows asymptotically as \(\frac{n}{\ln(n)}\). In this talk we propose a method for cutting down a random recursive tree that focuses on its largest degree vertices. Enumerate the vertices of a random recursive tree of size \(n\) according to a decreasing order of their degrees; namely, let \((v^{(i)})_{i=1}^{n}\) be so that \(\deg(v^{(1)}) \geq \cdots \geq \deg (v^{(n)})\). The targeted, vertex-cutting process is performed by sequentially removing vertices \(v^{(1)}\), \(v^{(2)}, \ldots, v^{(n)}\) and keeping only the subtree containing the root after each removal. The algorithm ends when the root is picked to be removed. We obtain that the first order growth in probability of \(X_n^{targ}\), the total number of steps for this procedure, is upper bounded by \(n^{1-\ln 2}\), which is substantially smaller than \(X_n\). More precisely, \(X_n^{targ}\) is upper bounded by \(Z_{\geq D}\), which denotes the number of vertices that have degree at least as large as the degree of the root. We prove that \(\ln(Z_{\geq D})\) grows as \(\ln (n)\) asymptotically and obtain its limiting behavior in probability. Moreover, we obtain that the \(k\)-th moment of \(\ln(Z_{\geq D})\) is proportional to \((\ln(n))^k\).

Authors: Tom Bohman, Fei Peng
Speaker: Fei Peng
➤ Title: Coprime Mappings and Lonely Runners
Abstract: For \(x\) real, let \(\{x\}\) be the fractional part of \(x\) (i.e. \(\{x\} = x ?\lfloor x\rfloor\)). The lonely runner conjecture can be stated as follows: for any \(n\) positive integers \(v_1 < v_2 < \dots < v_n\) there exists a real number \(t\) such that \(1/(n + 1) \le \{v_it\} ? n/(n + 1)\) for \(i = 1,\dots , n\). In this paper we prove that if \(\epsilon > 0\) and \(n\) is sufficiently large (relative to \(\epsilon\)) then such a \(t\) exists for any collection of positive integers \(v_1 < v_2 < \dots < v_n\) such that \(v_n < (2 - \epsilon)n\). This is an approximate version of a natural next step for the study of the lonely runner conjecture suggested by Tao.

The key ingredient in our proof is a result on coprime mappings. Let \(A\) and \(B\) be sets of integers. A bijection \(f : A \to B\) is a coprime mapping if \(a\) and \(f(a)\) are coprime for every \(a\in A\). We show that if \(A,B\subset[n]\) are intervals of length \(2m\) where \(m = e^{\Omega((\log\log n)^2)}\) then there exists a coprime mapping from \(A\) to \(B\). We do not believe that this result is sharp.

Authors: Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, Emo Welzl
Speaker: Kalina Petrova
➤ Title: On Connectivity in Random Graph Models with Limited Dependencies
Abstract: For any positive edge density \(p\), a random graph in the Erdös-Rényi \(G_{n,p}\) model is connected with non-zero probability, since all edges are mutually independent. We consider random graph models in which edges that do not share endpoints are independent while incident edges may be dependent and ask: what is the minimum probability \(\rho(n)\), such that for any distribution \(\mathcal{G}\) (in this model) on graphs with \(n\) vertices in which each potential edge has a marginal probability of being present at least \(\rho(n)\), a graph drawn from \(\mathcal{G}\) is connected with non-zero probability?

As it turns out, the condition "edges that do not share endpoints are independent" needs to be clarified and the answer to the question above is sensitive to the specification. In fact, we formalize this intuitive description into a strict hierarchy of five independence conditions, which we show to have at least three different behaviors for the threshold \(\rho(n)\). For each condition, we provide upper and lower bounds for \(\rho(n)\). In the strongest condition, the *coloring model* (which includes, e.g., random geometric graphs), we prove that \(\rho(n)\rightarrow 2-\phi\approx 0.38\) for \(n\rightarrow\infty\). This separates it from the weaker independence conditions we consider, as there we prove that \(\rho(n)>0.5-o(n)\).

In stark contrast to the coloring model, for our weakest independence condition — pairwise independence of non-adjacent edges — we show that \(\rho(n)\) lies within \(O(1/n^2)\) of the threshold \(1-2/n\) for completely arbitrary distributions.

This is joint work with Johannes Lengler, Anders Martinsson, Patrick Schnider, Raphael Steiner, Simon Weber, and Emo Welzl.

Authors: Dong Yeap Kang, Tom Kelly, Daniela Kühn, Deryk Osthus, Vincent Pfenninger
Speaker: Vincent Pfenninger
➤ Title: Perfect matchings in random sparsifications of Dirac hypergraphs
Abstract: For \(n \geq k > d \geq 1\) with \(k \mid n\), let \(m_{d}(k,n)\) be the minimum integer \(D \geq 0\) such that every \(n\)-vertex \(k\)-uniform hypergraph \(\mathcal H\) with minimum \(d\)-degree \(\delta_{d}(\mathcal H) \geq D\) has a perfect matching.

For \(k \geq 3\), we show that for \(n\) such that \(k \mid n\) and \(p = \Omega(n^{-k+1} \log n)\), if \(\mathcal H\) is an \(n\)-vertex \(k\)-uniform hypergraph with \(\delta_{k-1}(\mathcal H) \geq m_{k-1}(k,n)\), then asymptotically almost surely its \(p\)-random subhypergraph \(\mathcal H_p\) contains a perfect matching. Moreover, for \(d < k\) and \(\gamma > 0\), we show that the same conclusion holds if \(\mathcal H\) is an \(n\)-vertex \(k\)-uniform hypergraph with \(\delta_d(\mathcal H) \geq m_{d}(k,n) + \gamma{{n - d}\choose{k - d}}\).

Both of these results strengthen Johansson, Kahn, and Vu's seminal solution to Shamir's problem and can be viewed as robust versions of hypergraph Dirac-type results.

This is joint work with Dong Yeap Kang, Tom Kelly, Daniela Kühn, and Deryk Osthus.

Authors: Igor Araujo, József Balogh, Robert Krueger, Simón Piga, Andrew Treglown
Speaker: Simón Piga
➤ Title: On oriented cycles in randomly perturbed digraphs
Abstract: In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every \(\alpha>0\), there exists a constant \(C\) such that for every \(n\)-vertex digraph of minimum semi-degree at least \(\alpha n\), if one adds \(Cn\) random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree \(1\). Our proofs make use of a variant of an absorbing method of Montgomery.

Author: Boris Pittel
Speaker: Boris Pittel
➤ Title: Perfect partitions of a random set of integers
Abstract: Let \(X_1,\dots, X_n\) be independent integers distributed uniformly on \(\{1,\dots, M\}\), \(M=M(n)\to\infty\) however slow. A partition \(S\) of \([n]\) into \(\nu\) non-empty subsets \(S_1,\dots, S_{\nu}\) is called perfect, if all \(\nu\) values \(\sum_{j\in S_{\alpha}}X_j\) are equal. For a perfect partition to exist, \(\sum_j X_j\) has to be divisible by \(\nu\). For \(\nu=2\), Borgs et al. proved, among other results, that, conditioned on \(\sum_j X_j\) being even, with high probability a perfect partition exists if \(\kappa:=\lim \frac{n}{\log M}>\frac{1}{\log 2}\), and that w.h.p. no perfect partition exists if \(\kappa<\frac{1}{\log 2}\). We prove that w.h.p. no perfect partition exists if \(\nu\ge 3\) and \(\kappa<\frac{2}{\log \nu}\). We identify the range of \(\kappa\) in which the expected number of perfect partitions is exponentially high. We show that for \(\kappa> \frac{2(\nu-1)}{\log[(1-2\nu^{-2})^{-1}]}\) the total number of perfect partitions is exponentially high with probability \(\ge(1+\nu^2)^{-1}\).

Authors: David Aldous, Boris Pittel
Speaker: Boris Pittel
➤ Title: The critical beta-splitting random tree: heights and related results
Abstract: In the critical beta-splitting model of a random \(n\)-leaf binary tree, leaf-sets are recursively split into subsets, and a set of \(m\) leaves is split into subsets containing \(i\) and \(m-i\) leaves with probabilities proportional to \(1/{i(m-i)}\). We study the continuous-time model in which the holding time before that split is exponential with rate \(h_{m-1}\), the harmonic number. We (sharply) evaluate the first two moments of the time-height \(D_n\) and of the edge-height \(L_n\) of a uniform random leaf (that is, the length of the path from the root to the leaf), and prove the corresponding CLTs. We find the limiting value of the correlation between the heights of two random leaves of the same tree realization, and analyze the expected number of splits necessary for a set of \(t\) leaves to partially or completely break away from each other. We give tail bounds for the time-height and the edge-height of the {\em tree}, that is the maximal leaf heights. Our proofs are based on asymptotic analysis of the attendant (sum-type) recurrences. The essential idea is to replace such a recursive equality by a pair of recursive inequalities for which matching asymptotic solutions can be found, allowing one to bound, both ways, the elusive explicit solution of the recursive equality. We show that the sequence of distributions for the size of the uniformly random subtree is tight, but that the expected size of the subtree is asymptotic to \(\frac{3}{2\pi^2}\log^2 n\).

Authors: Tomasz Przybylowski, Oliver Riordan
Speaker: Tomasz Przybylowski
➤ Title: Thresholds: from small p regime to general
Abstract: Let \(p_c\) and \(q_c\) be the threshold and the expectation threshold, respectively, of an increasing family \(F\) of subsets of a finite set \(X\), and let \(l\) be the size of a largest minimal element of \(F\). Recently, Park and Pham proved the Kahn–Kalai conjecture, which says that \(p_c \leq K q_c \log_2 l\) for some universal constant \(K\). Here we slightly strengthen their result by showing that \(p_c \leq 1 − \exp( −Kq_c \log_2 l)\). The idea is to apply the Park–Pham Theorem to an appropriate ‘cloned’ family \(F_k\). While the improvement is tiny, we believe that the ‘cloning’ idea might be of interest. Based on joint work with Oliver Riordan.

Authors: Hariharan Narayanan, Amit Rajaraman, Piyush Srivastava
Speaker: Amit Rajaraman
➤ Title: Sampling from convex sets with a cold start using multiscale decompositions
Abstract: Running a random walk in a convex body \(K\subseteq\mathbb{R}^n\) is a standard approach to sample approximately uniformly from the body. The requirement is that from a suitable initial distribution, the distribution of the walk comes close to the uniform distribution \(\pi_K\) on \(K\) after a number of steps polynomial in \(n\) and the aspect ratio \(R/r\) (i.e., when \(rB_2 \subseteq K \subseteq RB_{2}\)).

Proofs of rapid mixing of such walks often require the probability density \(\eta_0\) of the initial distribution with respect to \(\pi_K\) to be at most \(\mathrm{poly}(n)\): this is called a "warm start". Achieving a warm start often requires non-trivial pre-processing before starting the random walk. This motivates proving rapid mixing from a "cold start", wherein \(\eta_0\) can be as high as \(\exp(\mathrm{poly}(n))\). Unlike warm starts, a cold start is usually trivial to achieve. However, a random walk need not mix rapidly from a cold start: an example being the well-known "ball walk". On the other hand, Lovász and Vempala proved that the "hit-and-run" random walk mixes rapidly from a cold start. For the related coordinate hit-and-run (CHR) walk, which has been found to be promising in computational experiments, rapid mixing from a warm start was proved only recently but the question of rapid mixing from a cold start remained open.

We construct a family of random walks inspired by classical decompositions of subsets of \(\mathbb{R}^n\) into countably many axis-aligned dyadic cubes. We show that even with a cold start, the mixing times of these walks are bounded by a polynomial in \(n\) and the aspect ratio. Our main technical ingredient is an isoperimetric inequality for \(K\) for a metric that magnifies distances between points close to the boundary of \(K\). As a corollary, we show that the CHR walk also mixes rapidly both from a cold start and from a point not too close to the boundary of \(K\).

Author: Peter Ralli
Speaker: Peter Ralli
➤ Title: A bound on the lowest eigenvalue of Cayley graphs
Abstract: Let G be a finite, undirected, d-regular graph and A its normalized adjacency matrix. It is a classical fact that the last eigenvalue of A is -1 if and only if G is bipartite. For Cayley graphs, we give a lower bound on the separation of the last eigenvalue from −1 in terms of the geometric expansion. We show that if G is a non-bipartite Cayley graph with outer vertex isoperimetric constant h then the "lower spectral gap" is bounded by λ ≥ ch^2/d^2 , where c is an absolute constant. This improves upon the best previous result which instead uses h^4, and we exhibit graphs for which this result is tight up to a factor depending on d.

Author: Mirabel Reid, Santosh Vempala
Speaker: Mirabel Reid
➤ Title: The k-cap process on Geometric Random Graphs
Abstract: The \(k\)-cap (or \(k\)-winners-take-all) process on a graph works as follows: in each iteration, a subset of \(k\) vertices of the graph are identified as winners; the next round winners are the vertices that have the highest total degree from the current winners, with ties broken randomly. This natural process is a simple model of firing activity and inhibition in the brain and has been found to have desirable robustness properties as an activation function. We study its convergence on directed geometric random graphs in any constant dimension, revealing rather surprising behavior, with the support of the current active set converging to lie in a small ball and the active set itself remaining essentially random within that.

Author: Jacob Richey
Speaker: Jacob Richey
➤ Title: Critical density for activated random walk and the stochastic sandpile
Abstract: In this talk I will discuss recent results related to activated random walk (ARW) and the stochastic sandpile (SSM), two interacting particle systems which are prototypical models exhibiting self organized criticality (SOC) and complex dynamics. SOC is a (loosely defined) set of statistical properties in systems with many particles, exhibited by a diverse group of natural processes including earthquakes, forest fires, and evolutionary speciation. Initially introduced as toy models of SOC in the 1980s, little mathematical progress was made on SSM and ARW until recently. In particular, establishing rigorous evidence for SOC in ARW or SSM, even in the one-dimensional setting, is an open question and remains the guiding light for research in this area. In this talk, I will cover the current state of the art, focusing on results related to critical densities for ARW and SSM, and mention many open problems.

Authors: Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, Maurice Rolvien
Speaker: Maurice Rolvien
➤ Title: The k-XORSAT threshold revisited
Abstract: We provide a simplified proof of the random k-XORSAT satisfiability threshold theorem. As an extension we also determine the full rank threshold for sparse random matrices over finite fields with precisely k non-zero entries per row. This result is an extension of a result from [Ayre, Coja-Oghlan, Gao, Müller: Combinatorica 2020]. The proof combines physics-inspired message passing arguments with a surgical moment computation.

Author: Andrzej Ruciński
Speaker: Andrzej Ruciński
➤ Title: Probability of non-saturation of the degree restricted random graph process
Abstract: A graph \(d\)-process starts with an empty graph on \(n\) vertices, and adds one edge at each time step, chosen uniformly at random from those pairs which are not yet edges and whose both vertices have current degree less than \(d\). If, in the final graph, at most one vertex has degree \(d-1\) and all other have degree \(d\), we call the process saturated. I will present a new approach to analysing this process based on random allocation of balls in bins which allows us to get improved results on the degree distribution throughout the process and, consequently, to determine the asymptotic probability of non-saturation of the process. (Joint work with Nick Wormald.)

Author: Maya Sankar
Speaker: Maya Sankar
➤ Title: The Turán Number of Homeomorphs
Abstract: Let \(X\) be a 2-dimensional simplicial complex. Denote by \(\text{ex}_{\hom}(n,X)\) the maximum number of 2-simplices in an \(n\)-vertex simplicial complex in which no sub-complex is homeomorphic to \(X\). It was recently shown that \(\text{ex}_{\hom}(n,X)=\Theta(n^{5/2})\) for any fixed (closed, connected) surface \(X\), and it is conjectured that \(n^{5/2}\) is an asymptotic upper-bound on this quantity for an arbitrary 2-dimensional simplicial complex \(X\). I will discuss recent progress on this conjecture, showing that \(\text{ex}_{\hom}(n,X)=O(n^{8/3})\) for any fixed \(X\). Using our techniques, one can also simplify the proof of the upper bound for surfaces.

Author: Aliaksei Semchankau
Speaker: Aliaksei Semchankau
➤ Title: On the sequence n! mod p
Abstract: Let \(p\) be a prime, and let \(\mathcal{A}\) be a set of residues of the sequence \(1!, 2!, 3!, \ldots\) modulo \(p\). We prove \( |\mathcal{A}| > (\sqrt{2} + o(1))\sqrt{p}. \) Now consider an interval \(\mathcal{I} \subseteq \{0, 1, \ldots, p - 1\}\) of length \(N > p^{7/8 + \varepsilon}\) and denote by \(\mathcal{A}_{\mathcal{I}}\) the set of residues modulo \(p\) it produces. Then we prove \( |\mathcal{A}_{\mathcal{I}}| > (1 + o(1))\sqrt{p}. \) Tools used are results from Algebraic Geometry as black boxes and simple combinatorial observations.

Authors: Ashwin Sah, Mehtaab Sawhney, Michael Simkin
Speaker: Michael Simkin
➤ Title: Efficient and optimal high-dimensional random planar assignment
Abstract: In the \(k\)-dimensional planar assignment problem we are given a cost array \(M\), indexed by \([n]^k\). The objective is to find a \(\{0,1\}\)-matrix \(A\) that minimizes \(\sum_{x \in [n]^k} A_xM_x\), subject to the constraint that every axis-parallel line in \(A\) contains exactly one \(1\) (so that the \(2\)-dimensional problem is equivalent to finding a minimal weight perfect matching in a bipartite graph). We show that if the entries of \(M\) are i.i.d. \(\mathrm{Exp}(1)\) random variables then both the expected and typical cost of an optimal assignment is \(\Theta(n^{k-2})\). Moreover, we describe a randomized algorithm that finds such an assignment with high probability. The main tool is iterative absorption, as developed by Glock, Kühn, Lo, and Osthus. The results answer questions of Frieze and Sorkin. The algorithmic result is in contrast to the axial assignment problem (in which \(A\) contains exactly one \(1\) in each axis-parallel co-dimension \(1\) hyperplane). Here, the best known bounds (which are due to Frankston, Kahn, Narayanan, and Park) exploit the connection between ``spread'' distributions and optimal assignments. Due to this reliance, no efficient algorithm is known. Joint work with Ashwin Sah and Mehtaab Sawhney.

Author: Sam Spiro
Speaker: Sam Spiro
➤ Title: The Random Turan Problem
Abstract: Let \(G_{n,p}\) denote the random \(n\)-vertex graph obtained by including each edge independently and with probability \(p\). Given a graph \(F\), let \(\mathrm{ex}(G_{n,p},F)\) denote the size of a largest \(F\)-free subgraph of \(G_{n,p}\). When \(F\) is non-bipartite, the asymptotic behavior of \(\mathrm{ex}(G_{n,p},F)\) was determined in breakthrough work done independently by Conlon-Gowers and by Schacht. In this talk we discuss some recent results for bipartite \(F\) (where much less is known), as well as for the analogous problem for \(r\)-partite \(r\)-graphs.

Author: Shannon Starr
Speaker: Shannon Starr
➤ Title: About Ross Pinsky's combinatorial formula for moments of the generalized Ulam problem
Abstract: Consider a random variable \(Z_{n,k}\) based on a uniform random permutation \(\pi \in S_n\). Let \(Z_{n,k}\) be equal to the number of increasing subsequences of length \(k\): \(|\{(i_1,\dots,i_k) \in \mathbb{Z}^k\, :\, 1\leq i_1<\dots<i_k\leq n\, ,\ \pi_{i_1}<\dots<\pi_{i_k}\}|\). In an important paper, Ross Pinsky proved \(\mathbf{E}\big[Z_{n,k}^2\big]\) is equal to \(\sum_{i} A(k-i,i)B(n,2k-i)\), where for any nonnegative integers \(N\) and \(j\), we have \(B(N,j) = {N\choose j}/j!\) and \(A(N,j)\) is a particular nonnegative integer, which Pinsky characterized in two different ways, one of which involves the occupation time of the \(x\)-axis prior to a first return to the origin. Using this, he proved a law of large numbers for the sequence \(Z_{n,k_n}\) when \(k_n=o(n^{2/5})\) as \(n \to \infty\). In a follow-up paper, he also proved the sequence \(Z_{n,k_n}\) fails to obey a law of large numbers when \(1/k_n = o(1/n^{4/9})\) as \(n \to \infty\). Here, we return to his combinatorial formula for the the second moment of \(Z_{n,k}\), and we obtain a generating function for the \(A(N,j)\) triangular array. We are motivated by the hope of applying spin glass techniques to the well-known Ulam's problem to see if this gives a new perspective.

Authors: Charilaos Efthymiou, Thomas Hayes, Daniel Stefankovic, Eric Vigoda
Speaker: Daniel Stefankovic
➤ Title: Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
Abstract: We study the mixing time of the single-site update Markov chain, known as the Glauber dynamics, for generating a random independent set of a tree. Our focus is obtaining optimal convergence results for arbitrary trees. We consider the more general problem of sampling from the Gibbs distribution in the hard-core model where independent sets are weighted by a parameter λ > 0; the special case λ = 1 corresponds to the uniform measure. Previous work of Martinelli, Sinclair and Weitz (2004) obtained optimal mixing time bounds for the complete d-regular tree for all λ. However, Restrepo et al. (2014) showed that for sufficiently large λ there are bounded-degree trees where optimal mixing does not hold. In particular, on the complete, regular tree with a fixed boundary condition corresponding to the broadcasting measure the Glauber dynamics slows down at the reconstruction threshold. Recent work of Eppstein and Frishberg (2022) proved rapid mixing of the Glauber dynamics for arbitrary trees, and more generally graphs of bounded tree-width; the polynomial exponents in their bounds are a function of λ but independent of the maximum degree.

We establish an optimal bound on the relaxation time (i.e., inverse spectral gap) of O(n) for the Glauber dynamics for unweighted independent sets on arbitrary trees. Moreover, for λ ≤ .44 we prove an optimal mixing time bound of O(n log n). We stress that our results hold for arbitrary trees and there is no dependence on the maximum degree ∆. Interestingly, our results extend (far) beyond the uniqueness threshold for ∆-regular trees, which is on the order of λ = O(1/∆). Our proof approach is inspired by recent work on spectral independence. In fact, we prove that spectral independence holds with a constant independent of the maximum degree for any tree when λ ≤ 1.3. This implies optimal mixing for any tree with constant maximum degree. To obtain our results for arbitrary trees, we utilize the combinatorial nature of independent sets to directly prove approximate tensorization of variance/entropy via a non-trivial inductive proof. We are able to approximate tensorization of entropy when λ ≤ 0.44, and our proof extends to λ ≤ 1.05 modulo a conjectured inequality that we can numerically verify.

Authors: Jacob Fox, Maya Sankar, Michael Simkin, Jonathan Tidor, Yunkun Zhou
Speaker: Jonathan Tidor
➤ Title: Skeletal degeneracy for hypergraph Turán and Ramsey problems
Abstract: The degeneracy of a graph is an important parameter in extremal graph theory. The Burr–Erdős conjecture, now a theorem of Lee, states that for graphs with bounded degeneracy, the Ramsey number is linear in the number of vertices. Additionally, a conjecture of Erdős from 1966 states that the Turán number of a \(d\)-degenerate graph is at most \(O(n^{2-1/d})\). While this conjecture is still open, the bound \(O(n^{2-1/(4d)})\) is known.

We define the skeletal degeneracy of a \(k\)-uniform hypergraph to be the degeneracy of its 1-skeleton (i.e., the graph formed by replacing every \(k\)-edge by a \(k\)-clique). Unlike the usual notion of hypergraph degeneracy (which gives no control over the Turán- and Ramsey-type properties of a hypergraph), we show that the skeletal degeneracy of a hypergraph gives good bounds on its Turán and Ramsey numbers.

We prove the hypergraph analogue of the Burr–Erdős conjecture: \(k\)-uniform hypergraphs with bounded skeletal degeneracy have Ramsey number linear in their number of vertices. In addition, we give upper and lower bounds on the Turán number of a \(k\)-uniform \(k\)-partite hypergraph that are of the same shape. The proofs of both results use the technique of dependent random choice. In addition, the proof of our Ramsey result uses the "random greedy process" introduced by Lee in his resolution of the Burr–Erdős conjecture for graphs.

Joint work with Jacob Fox, Maya Sankar, Michael Simkin, and Yunkun Zhou.

Author: Thuy-Duong Vuong
Speaker: Thuy-Duong Vuong
➤ Title: Generalized log-concave polynomials and applications
Abstract: Log-concave/Lorentzian generating polynomials have been instrumental in resolving open problems on sampling matroid bases. We show how generalized notions of log-concavity, which include fractional log-concavity, entropic independence, and spectral independence, can be established through the root-freeness of polynomials and/or decay of correlation. We discuss applications of our framework in establishing concentration inequalities and in designing sampling, counting, and optimization algorithms.

Authors: Erlang Surya, Lutz Warnke, Emily Zhu
Speaker: Lutz Warnke
➤ Title: Isomorphisms between dense random graphs
Abstract: Applied benchmark tests for the famous "subgraph isomorphism problem" empirically discovered interesting phase transitions in random graphs. This motivates our rigorous study of two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p_1,p_2. In particular, (i) we prove a sharp threshold result for the appearance of G_{n,p_1} as an induced subgraph of G_{N,p_2}, (ii) we show two-point concentration of the size of the maximum common induced subgraph of G_{N, p_1} and G_{N,p_2}, and (iii) we show that the number of induced copies of G_{n,p_1} in G_{N,p_2} has a "squashed lognormal" limiting distribution. These results confirm simulation-based phase transition predictions of McCreesh-Prosser-Solnon-Trimble, and resolve several open problems of Chatterjee-Diaconis. The proofs are based on careful refinements of the first and second moment method, using several extra twists to (a) take the non-standard behavior into account, and (b) work around the large variance issues that prevent standard applications of the second moment method, using in particular pseudorandom properties and multi-round exposure arguments to tame the variance. Based on joint work with Erlang Surya and Emily Zhu; see arXiv:2305.04850

Authors: Lior Gishboliner, Asaf Shapira, Yuval Wigderson
Speaker: Yuval Wigderson
➤ Title: Asymmetric graph removal
Abstract: The triangle removal lemma of Ruzsa and Szemerédi is a fundamental result in extremal graph theory; very roughly speaking, it says that if a graph is "far" from triangle-free, then it contains "many" triangles. Despite decades of research, there is still a lot that we don't understand about this simple statement; for example, our understanding of the quantitative dependencies is very poor.

In this talk, I will discuss asymmetric versions of the triangle removal lemma, where in some cases we can get almost optimal quantitative bounds. The proofs use a mix of ideas coming from graph theory, number theory, probabilistic combinatorics, and Ramsey theory.

Based on joint work with Lior Gishboliner and Asaf Shapira.

Author: Peter Winkler
Speaker: Peter Winkler
➤ Title: Sets that Support a Joint Distribution
Abstract: Given a closed set on the plane and two probability distributions on the real line, when are there random variables with the given distributions whose joint distribution is supported by the given set? We consider both discrete and continuous distributions; in the latter case, the problem is equivalent to asking which sets in the unit square can support a permuton. Joint work with Chris Coscia and Martin Tassy.

Authors: Jun-ting Hsieh, Pravesh Kothari, Aaron Potechin, Jeff Xu
Speaker: Jeff Xu
➤ Title: Ellipsoid Fitting Up to a Constant
Abstract: What is the largest \(m = m(d)\) such that there is an ellipsoid in \(R^d\) that passes through \(v_1, v_2,\dots, v_m\) with high probability when the \(v_i\)s are chosen independently from the standard Gaussian distribution N(0, Id). Saunderson, Parrilo and Willsky conjectured that \(m = (1 − o(1))\frac{d^2}{4} \) with high probability. Very recently, Potechin, Turner, Venkat and Wein [PTVW22] and Kane and Diakonikolas [KD22] proved that \(m ≳ \frac{d^2}{ log^{O(1)}(d)}\) via a certain natural, explicit construction of an ellipsoid.

In this work, we give a substantially tighter analysis of their construction to prove that \(m \geq \frac{d^2}{C}\) for an absolute constant C > 0. This resolves one direction of the SPW conjecture up to a constant.

Author: Max Xu
Speaker: Max Xu
➤ Title: Recent progress in random multiplicative functions
Abstract: Random multiplicative functions are probabilistic models for arithmetic functions that number theorists care about. It also has strong connections to problems in additive combinatorics and becomes an active area. In this talk, I will survey the subject and describe some recent progress as well as some open problems.

		Rashid	Room 4307	Room 4303	Room 4405
Monday, June 12
09:00am – 10:00am		Plenary talk: Noga Alon, Random Norms
10:00am – 10:30am	Coffee
10:30am – 11:00am		Robert Hancock, A resolution of the Kohayakawa Kreuter conjecture for almost all pairs of graphs	Vincent Pfenninger, Perfect matchings in random sparsifications of Dirac hypergraphs	Abhinav Bhardwaj, Entry-wise dissipation for singular vector perturbation bounds
11:00am – 11:30am		Zhihan Jin, Exponential Erdős-Szekeres theorem for matrices	Simón Piga, On oriented cycles in randomly perturbed digraphs	Peter Ralli, A bound on the lowest eigenvalue of Cayley graphs
11:30am – 12:00pm		Eoin Hurley, Induced Bounded Degree Trees in Sparse Graphs	Amarja Kathapurkar, Transversal cycle factors in multipartite graphs	Alan Frieze, Sequentially constrained Hamilton Cycles in random graphs
12:00pm – 12:30pm	PHOTO
12:30pm – 2:30pm	LUNCH
2:30pm – 3:30pm		Plenary talk: Jinyoung Park, p-smallness of increasing families
3:30pm – 4:00pm	Coffee
4:00pm – 4:30pm		Michael Simkin, Efficient and optimal high-dimensional random planar assignment	Lutz Warnke, Isomorphisms between dense random graphs	Sam Spiro, The Random Turan Problem	Marco L. Ortiz, Targeted cutting of random recursive trees
4:30pm – 5:00pm		Rafael Miyazaki, Bounds for the threshold function of arithmetic progressions in sumsets of random sets	Ilay Hoshen, Saturation Number in Random Graphs	Jiaxi Nie, Random Turán numbers of some degenerate hypergraphs	Stoyan Dimitrov, BFS vs DFS for a random target node in plane trees
5:00pm – 5:30pm		Tomasz Przybylowski, Thresholds: from small p regime to general	Kalina Petrova, On Connectivity in Random Graph Models with Limited Dependencies	Charles Burnette, Fixed-point free involution factorizations	Boris Pittel, The critical beta-splitting random tree: heights and related results

		Rashid	Room 4307	Room 4303	Room 4405
Tuesday, June 13
09:00am – 10:00am		Plenary talk: Jeff Kahn, On the \(H\)-space of a random graph
10:00am – 10:30am	Coffee
10:30am – 11:00am		Boris Bukh, Enumeration of interval graphs and \(d\)‑representable complexes	Michael Anastos, Constructing Hamilton cycles efficiently	Nikita Gladkov, A strong FKG inequality for multiple events	Jeff Xu, Ellipsoid Fitting Up to a Constant
11:00am – 11:30am		Ting-Wei Chao, Empty Boxes, Nets, and Convex Holes	Mirabel Reid, The k-cap process on Geometric Random Graphs	Asaf Cohen Antonir, Bounding the number of odd paths in planar graphs via convex optimization	Lena Krieg, Inference of a Rumor's Source in the Independent Cascade Model
11:30am – 12:00pm		R. Amzi Jeffs, Colorful Words and d-Tverberg Complexes	Michael Molloy, The degree process is far from uniform	Shagnik Das, Covering grids with multiplicity	Liam Hardiman, A Quantum Algorithm for Learning a Hidden Graph of Bounded Degree
12:00pm – 12:30pm		Peter Winkler, Sets that Support a Joint Distribution	Andrzej Ruciński, Probability of non-saturation of the degree restricted random graph process	Yahav Alon, Completion to Hamiltonicity and pancyclicity in G(n,p)
12:30pm – 2:30pm	LUNCH
2:30pm – 3:30pm		Plenary talk: Annika Heckel, The chromatic number of \(G(n, 1/2)\): bounds, concentration and conjectures
3:30pm – 4:00pm	Coffee
4:00pm – 4:30pm		Jane Gao, Minors of random representable matroid over finite fields	Max Xu, Recent progress in random multiplicative functions	Brett Kolesnik, The asymptotic number of score sequences
4:30pm – 5:00pm		Robert Krueger, Sharp threshold for random Sperner's Theorem	Boris Pittel, Perfect partitions of a random set of integers	Pawel Hitczenko, A class of polynomial recurrences resulting in \(N(n/log n, n/log^2 n)\) asymptotic normality
5:00pm – 5:30pm		Peleg Michaeli, Fast construction on a restricted budget	Aliaksei Semchankau, On the sequence n! mod p	Shannon Starr, About Ross Pinsky's combinatorial formula for moments of the generalized Ulam problem

		Rashid	Room 4307	Room 4303	Room 4405
Wednesday, June 14
09:00am – 10:00am		Plenary talk: Julian Sahasrabudhe, An exponential improvement for diagonal Ramsey
10:00am – 10:30am	Coffee
10:30am – 11:00am		Xiaoyu He, Set-coloring Ramsey numbers via codes	Kyriakos Katsamaktsis, Rainbow Hamilton cycles in randomly coloured perturbed graphs	Martin Dyer, Encouraging triangles in graphs with given degree sequence
11:00am – 11:30am		Ce Chen, Ramsey-Turán problems with small independence numbers	Gal Kronenberg, Shotgun reconstruction of random graphs	Amit Rajaraman, Sampling from convex sets with a cold start using multiscale decompositions
11:30am – 12:00pm		Jonathan Tidor, Skeletal degeneracy for hypergraph Turán and Ramsey problems	Maurice Rolvien, The k-XORSAT threshold revisited	Daniel Frishberg, Improved mixing for the convex polygon triangulation flip walk
12:00pm – 12:30pm		Jacob Fox, Ramsey Cayley graphs, random graph models, and information theory	Sahar Diskin, Supercritical percolation on the hypercube - typical properties of the giant component	Thuy-Duong Vuong, Generalized log-concave polynomials and applications
12:30pm – 2:30pm	LUNCH
2:30pm – 3:30pm		Plenary talk: Richard Montgomery, Transversals in Latin Squares
3:40pm – 4:40pm		Plenary talk: Sam Mattheus, The asymptotics of \(r(4,t)\)
6:00pm	Random Run

		Rashid	Room 4307	Room 4303	Room 4405
Thursday, June 15
09:00am – 10:00am		Plenary talk: Joel Spencer, Random Gems
10:00am – 10:30am	Coffee
10:30am – 11:00am		Matija Bucic, Towards the Erdős-Hajnal Conjecture	Benjamin Gunby, Antichain Codes	Anton Bernshteyn, Flows on a torus
11:00am – 11:30am		Charilaos Efthymiou, Spectral Independence Beyond Uniqueness	Allan Lo, Cycle Partition of Dense Regular Digraphs and Oriented Graphs	Manuel Lladser, Resolvability of Jaccard Metric Spaces
11:30am – 12:00pm		Eden Kuperwasser, Sharp thresholds for Ramsey properties	Haoran Luo, Maximal 3-wise Intersecting Families	Maya Sankar, The Turán Number of Homeomorphs
12:00pm – 12:30pm		Yuval Wigderson, Asymmetric graph removal	Micha Christoph, Minimum Degree Threshold for \(H\)-factors with High Discrepancy	Chaim Even-Zohar, Explicit Existentially-Complete Hypergraphs
12:30pm – 2:00pm	LUNCH
2:00pm – 6:00pm	Excursion-Carnegie
6:00pm – 7:30pm	Cocktails
7:30pm – 10:00pm	Banquet

		Rashid	Room 4307	Room 4303	Room 4405
Friday, June 16
9:30am – 10:00am		Daniel Stefankovic, Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees	Fei Peng, Coprime Mappings and Lonely Runners	Mark Huber, Tight relative error estimation in the mean of Bernoulli random variables
10:00am – 10:30am		Patrick Bennett, Random processes for generalized Ramsey problems	Ryan Jeong, On the Relative Sizes of Complements of Generalized Sumsets	Tamas Makai, The dispersion process on complete graphs within the critical window
10:30am – 11:00am		Shuhei Mano, Sampling from toric models and hypergeometric functions	Jacob Richey, Critical density for activated random walk and the stochastic sandpile	Margarita Akhmejanova, On-line colorings
11:00am – 11:30am	Coffee
11:30am – 12:30pm		Plenary talk: Eric Vigoda, Optimal Mixing of MCMC via Spectral Independence

The 21st International Conference on
RANDOM STRUCTURES & ALGORITHMS

Abstracts

Plenary Talks

Contributed Talks

The 21st International Conference on RANDOM STRUCTURES & ALGORITHMS

Program

Abstracts

Plenary Talks

Contributed Talks

The 21st International Conference on
RANDOM STRUCTURES & ALGORITHMS