In this post I advertise my colloquium lecture tomorrow – Thursday 23/1/2020 14:30 – on recent advances in combinatorics, and also mention Wojtek Samotij’s lecture on our combinatorics seminar on The lower tail for triangles in random graphs. Click here for the previous post on MIP*=RE
Artist: Heidi Buck. “Catch a Dragon by the Tail” ( source )
A few months ago we briefly described the solution by to the infamous upper tail problem for random graph. More recently, Gadi Kozma and Wojciech Samotij solved the infamous lower tail problem.
My colloquium talk on Thursday January 23: Recent Advances in Combinatorics
Remark: I chose only a few advances only from the last few months and mainly in probabilistic and extremal combinatorics. In the lecture I will briefly mention others as well.
Colloquium: Gil Kalai (HUJI) – Some recent advances in combinatorics
I will discuss some recent advances in combinatorics, among them the disproof of Hedetniemi conjecture by Shitov, the proof of the sensitivity conjecture by Huang, the progress on the Erdos-Rado sunflower conjecture by Alweiss, Lovett, Wu, and Zhang, and the progress on the expectation threshold conjecture by Frankston, Kahn, Narayanan, and Park.
Thu, 23/01/2020 – 14:30 to 15:30
Manchester Building (Hall 2), Hebrew University Jerusalem
Combinatorics seminar last Monday: Kozma and Samotij solved the infamous lower tail problem for random graphs.
Combinatorics Seminar HUJI
When: Monday Jan 20, 10:00-11:45
Where: C-400, CS building
Speaker: Wojciech Samotij (TAU)
Title: The lower tail for triangles in random graphs
Let denote the number of triangles in the random graph . The problem of determining the asymptotics of the logarithmic lower tail probability of~, that is, the function , for , has attracted considerable attention of both the combinatorics and the probability communities. In this talk, we explain how one can bound from above by solving a natural combinatorial optimisation problem that generalises Mantel’s / Turán’s theorem. Moreover, we will prove a matching lower bound on in the case . Our argument, which employs ideas from an earlier joint work with Gady Kozma, Tom Meyerovitch, and Ron Peled, exploits connections between entropy and independence.
This is joint work with Gady Kozma.