Randomized algorithms in combinatorics

03/14/2023 12:00 pm - 1:00 pm
CMSA Room G10
Address: CMSA, 20 Garden Street, Cambridge, MA 02138 USA

Member Seminar

Speaker: Michael Simkin

Title: Randomized algorithms in combinatorics

Abstract: Randomized algorithms have been a computational workhorse for almost as long as there have been computers. Surprisingly, such algorithms can also be used to attack problems that are neither algorithmic nor probabilistic. Time permitting I will discuss the following combintorial examples:

  1. Enumerative combinatorics and the n-queens problem: In how many ways can one place n queens on an n x n chessboard so that no queen threatens any other?
  2. Constructions of combinatorial designs and the Erdos high-girth Steiner triple system problem: An order-n Steiner triple system (STS) is a collection of triples on n vertices such that every pair of vertices is contained in exactly one triple. In 1973 Erdos conjectured that there exist STSs with arbitrary large girth (informally, no small set of vertices spans many triples). I will discuss the use of randomized algorithms to prove this conjecture. Joint work with Kwan, Sah, and Sawhney.
  3. Thresholds in random graphs and hypergraphs: I will discuss how randomized algorithms can be combined with the recent resolution of the Kahn–Kalai conjecture to determine thresholds in random (hyper) graph theory. Joint work with Pham, Sah, and Sawhney.