CS Theory seminar today

[Benjamin Landon]

Hi all,

The CS theory seminar today may be of interest:

Please join us for Theory Seminar this Friday, 8th November at 11am with Speaker Aditya Potukuchi from York University. The seminar will be held in person and via Zoom.

SEMINAR DETAILS:
DATE: 8TH NOVEMBER, 2024
TIME: 11AM TO 12NOON
LOCATION: SF3208-3210
SPEAKER: ADITYA POTUKUCHI (YORK UNIVERSITY)

Title: Random graphs with few triangles.

Abstract: Computing the probability that an Erd\"{o}s-R\'{e}nyi random graph $G_{n,p}$ (or the binomial random graph $G_{n,m}$) has significantly fewer triangles than expected is among the easiest problems to state in the study of random combinatorial structures. However, attempts to understand this problem uncover a surprising and insightful landscape that it, at the moment, not fully understood. I will talk briefly about the history of our understanding of the problem, and focus on some recent developments. I will largely talk about the case when $p = \Theta(1/\sqrt{n})$, and discuss some algorithmic and structural results for typical graphs sampled from the corresponding conditional distribution. I will also talk briefly about our proof methods that involve ingredients from algorithms and statistical physics including rapid mixing of Markov chains and the cluster expansion.

Joint work with Matthew Jenssen, Will Perkins, and Michael Simkin.