Colloquium Ical Atom Mailing List

Random processes have played a central role in combinatorics since Paul Erdos’s “probabilistic revolution” eight decades ago. Traditionally, such processes are used to define a probability space in which an object with desired properties is sampled with positive probability, thereby proving its existence. Drawing on three case studies, I will explore how recent advances extend the utility of random processes beyond existence proofs, enabling us also to count and understand the structure of combinatorial objects.

To begin, I will discuss the construction of high-girth Steiner triple systems, which proved a 1973 conjecture of Erdos. This builds on Keevash’s breakthrough proof — combining probability and algebra — of the existence of designs, but uses random processes to overcome limitations of the algebraic component.

Next, I will consider triangle-free graphs. The basic problem is to estimate the number of triangle-free graphs with a specified number of vertices and edges. This prototypical forbidden substructure problem motivated the development of key tools in probabilistic combinatorics, essentially solving the problem for graphs that are somewhat sparse or somewhat dense. However, the intermediate-density regime, in which triangle-free graphs undergo a phase transition, remained elusive. I will present the first formula for the number of triangle-free graphs in this regime. Crucial to the proof is a random process to sample these graphs.

Finally, I will discuss the $n$-queens problem: In how many ways can $n$ queens be placed on an $n \times n$ chessboard so that no two threaten each other? It turns out that random processes can be used to reduce the combinatorial question to an infinite-dimensional convex optimization problem. This also sheds light on the typical structure of $n$-queens configurations.

TBA

TBA

TBA

The Aldous-Lyons conjecture from probability theory states that every (unimodular) infinite graph can be (Benjamini-Schramm) approximated by finite graphs. This conjecture is an analogue of other influential conjectures in mathematics concerning how well certain infinite objects can be approximated by finite ones; examples include Connes’ embedding problem (CEP) in functional analysis and the soficity problem of Gromov-Weiss in group theory. These became major open problems in their respective fields, as many other long standing open problems, that seem unrelated to any approximation property, were shown to be true for the class of finitely-approximated objects. For example, Gottschalk’s conjecture and Kaplansky’s direct finiteness conjecture are known to be true for sofic groups, but are still wide open for general groups.

In 2019, Ji, Natarajan, Vidick, Wright and Yuen resolved CEP in the negative. Quite remarkably, their result is deduced from complexity theory, and specifically from undecidability in certain quantum interactive proof systems. Inspired by their work, we suggest a novel interactive proof system which is related to the Aldous-Lyons conjecture in the following way: If the Aldous-Lyons conjecture was true, then every language in this interactive proof system is decidable. A key concept we introduce for this purpose is that of a Subgroup Test, which is our analogue of a Non-local Game. By providing a reduction from the Halting Problem to this new proof system, we refute the Aldous-Lyons conjecture.

This talk is based on joint work with Lewis Bowen, Alex Lubotzky, and Thomas Vidick.

No special background in probability theory or complexity theory will be assumed.

Manifolds are locally rectifiable (at each point) to R^n or C^n. The local Geometry, Topology, Algebra of singular spaces is much richer. Such a germ X is homeomorphic to the cone over Link[X]. In ‘most cases’ this homeomorphism cannot be chosen differentiable. This brings various pathologies.

The Lipschitz equivalence of space-germs has been under investigation in the last 30 years. It excludes various pathologies of homeomorphisms, but is ‘rough enough’ to prevent moduli.

The first natural question is whether/when the homeomorphism X ~ Link[X] can be chosen bi-Lipschitz. The first obstructions to this are fast vanishing cycles on Link[X]. We detect lots of fast cycles. This gives countable (multi-index) series of `exotic Lipschitz structures’ on the germ (R^n,o), all realizable as complex-analytic hypersurface germs.