check
Combinatorics: Maksim Zhukovskii (Weizmann) | Einstein Institute of Mathematics

Combinatorics: Maksim Zhukovskii (Weizmann)

Date: 
Mon, 06/06/202211:00-13:00
Location: 
Sprinzak 202


HUJI Combinatorics Seminar 


When: Monday June 6th, 2022, at 11AM (Israel time)
Where: Sprinzak 202


Link to live session:
https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=e46b511c-861b...



Speaker: Maksim Zhukovskii (Weizmann)
Title: On anti-stochastic properties of graphs


Abstract: 
A graph property is a set of graphs closed under isomorphism relation. We call a graph property A anti-stochastic if the probability that a random graph satisfies A is small but, with high probability, there is a small perturbation transforming G into a graph satisfying A. While without the isomorphism requirement such a set of graphs is easy to obtain from binary covering codes, for graph properties this is not so evident.  If an admissible perturbation is either the addition or the deletion of one edge, we exhibit an anti-stochastic property that is satisfied by G(n,1/2) with probability (2 + o(1))/n^2, which is as small as possible. We also express another anti-stochastic property in terms of the degree sequence of a graph. This property has probability (2 + o(1))/(n ln n), which is optimal up to a factor of 2.
This is joint work with S. Kiselev, A. Kupavskii, O. Verbitsky