Two talks at HUJI: on the “infamous lower tail” and TOMORROW on recent advances in combinatorics

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 X denote the number of triangles in the random graph G_{n,p}. The problem of determining the asymptotics of the logarithmic lower tail probability of~X, that is, the function f_c(n,p) = - \log Pr(X \le c \mathbb E [X]), for c \in [0,1), has attracted considerable attention of both the combinatorics and the probability communities. In this talk, we explain how one can bound f_c(n,p) 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 f_c(n,p) in the case p = 1/2. 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.

This entry was posted in Combinatorics, Updates. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s