Construction, Counting, and Finding Structure with Random Processes
Seminar
Speaker
Michael Simkin (M.I.T.)
Date
15/12/2024 - 13:00 - 12:00Add to Calendar
2024-12-15 12:00:00
2024-12-15 13:00:00
Construction, Counting, and Finding Structure with Random Processes
Random processes have played a central role in combinatorics since Paul Erdő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 Erdős. 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 nxn 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.
Zoom link
Math seminar room (building 216, room 201)
אוניברסיטת בר-אילן - Department of Mathematics
mathoffice@math.biu.ac.il
Asia/Jerusalem
public
Place
Math seminar room (building 216, room 201)
Abstract
Random processes have played a central role in combinatorics since Paul Erdő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 Erdős. 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 nxn 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.
Last Updated Date : 08/12/2024
