Random graphs have many useful properties. For example, they have large spectral gaps, predictable counts of small subgraphs, and edges that are evenly distributed. Remarkably, Chung, Graham, and Wilson (Combinatorica 1989) proved that many of these properties are equivalent. In fact, even a condition as simple as having the correct number of 4-cycles is equivalent to many others. These are collectively known as quasirandom properties.
This workshop will focus on the algorithmic landscape of quasirandomness. Quasirandom structure can make difficult problems tractable and can also help prove lower bounds. The talks will cover a broad range of recent directions, including average-case algorithms, certificates of typical behavior, hypothesis testing for random graph models, sparse counting lemmas, and fine-grained complexity. Our goal is to understand how these directions are related, what new notions of quasirandomness they suggest, and how quasirandom properties appear in different computational problems.
Abstract: In this tutorial, we introduce the theory of quasirandomness, with a particular focus on quasirandom graphs. In 1987, Thomason introduced the notion of a "jumbled" graph, capturing structural properties characteristic of random graphs. In 1989, Chung, Graham, and Wilson developed a unifying theory of quasirandom graph properties and their equivalences. We will begin by understanding these properties, the surprising relationships between them, and the simple conditions that characterize quasirandomness. We will then explore their implications, including connections to graph regularity. Finally, we will turn to quasirandomness beyond graphs, discussing analogous theories in other settings, such as groups and permutations.
We will also introduce the framework of quality control (Marcussen, Rubinfeld, and Sudan, 2026) as an algorithmic example illustrating how quasirandom properties can be used to study new computational problems.
Abstract: The graph counting lemma of Chung, Graham, and Wilson (Combinatorica 1988) is a fundamental result in combinatorics, which states that if a large graph is pseudorandom (in a specific sense that we will define), then the number of copies of any small graph H in G is close to what is expected from a random graph of the same density. However, this result is only nontrivial when G is a dense graph. In this work, we obtain a counting lemma that works in the sparse setting and is well-suited for the density increment arguments in additive combinatorics. In a recent remarkable breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. We combine our counting lemma with other ideas to establish Kelley--Meka type bounds for all linear patterns defined by translation-invariant systems of binary linear forms, i.e., each form depends on exactly two variables. In particular, we obtain strong bounds for the Turan problem in Abelian Cayley sum graphs, i.e., an upper bound on the maximum edge density of an Abelian Cayley sum graph with a clique of a given size. To prove our results, we employ some of the recent technology developed by Kelley and Meka and also the follow-up work by Kelley, Lovett, and Meka (STOC 2024).
This talk is based on a joint work with Yuval Filmus, Hamed Hatami, and Kaave Hosseini (FOCS 2024, full version: arXiv:2311.12248)
Abstract: The celebrated theorem of Chung, Graham, and Wilson on quasirandom graphs implies that if the 4-cycle and edge counts in a graph G are both close to their typical number in G(n,1/2), then this also holds for the counts of subgraphs isomorphic to H for any H of constant size. We prove a similar statement where the notion of close is whether the given (signed) subgraph count can be used as a test between G(n,1/2) and a stochastic block model SBM.
Quantitatively, this is related to approximately maximizing H → |Φ(H)|1/|V(H)| where Φ(H) is the Fourier coefficient of SBM, indexed by subgraph H. This formulation turns out to be equivalent to approximately maximizing the partition function of a spin model over an alphabet given by the community labels in SBM.
We resolve the approximate maximization when SBM satisfies one of four conditions: 1) the probability of an edge between any two vertices in different communities is exactly 1/2; 2) the probability of an edge between two vertices from any two communities is at least 1/2 (this case is also covered in a recent work of Yu, Zadik, and Zhang); 3) the probability of belonging to any given community is at least c for some universal constant c > 0; 4) SBM has two communities. In each of these cases, we show that there is an approximate maximizer of H → |Φ(H)|1/|V(H)| which is a star or a 4-cycle. This implies that if there exists a constant-degree polynomial test distinguishing G(n,1/2) and SBM, then the two distributions can also be distinguished via the signed count of a star or a 4-cycle. We conjecture that the same holds true for distinguishing G(n,1/2) and any graphon if we also add triangles.
Authors: Kiril Bangachev and Guy Bresler
Abstract: We show that k-coloring a k-colorable graph can be done in expected time O(nk). Since almost all such graphs have Ω(n^2) edges, this is an average-case sublinear algorithm for a natural NP-complete problem. It turns out that a key to this algorithm is the ability to certify (with zero error) that a small random graph is uniquely k-colorable. I'll discuss the overall algorithm, and some details of how graph quasirandomness gives the key step.
Abstract: TBD