Beijing Institute of Mathematical Sciences and Applications

Benjamin Sudakov

Michael Krivelevich

Tuesday, February 21, 2023 5:05 PM - 6:15 PM

Online

Zoom 787 662 9899 (BIMSA)

Let $G$ be a graph on $n$ vertices, and assume that its minimum degree is at least $k$, or its independence number is at most $t$. What can be said then about various graph-theoretic parameters of $G$, such as connectivity, large minors and subdivisions, diameter, etc.? Trivial extremal examples (disjoint cliques, unbalanced complete bipartite graphs, random graphs and their disjoint unions) supply rather prosaic bounds for these questions. We show that the situation is bound to change dramatically if one adds relatively few random edges on top of $G$ (the so called randomly perturbed graph model). Here are representative results (in a somewhat approximate form): - Assuming $\delta(G)>=k$, and for $s < ck$, adding about $Cns*\log (n/k)/k$ random edges to $G$ results with high probability in an s-connected graph; - Assuming $\alpha(G)<= t$ and adding $cn$ random edges to $G$ typically produces a graph containing a minor of a graph of average degree of order $n/\sqrt{t}$. In this talk I will introduce and discuss the model of randomly perturbed graphs, and will present our results. A joint work with Elad Aigner-Horev and Dan Hefetz.

Michael Krivelevich is a Baumritter Professor of Combinatorics with the School of Mathematical Sciences of Tel Aviv University. He works in Extremal and Probabilistic Combinatorics and has coauthored two books and more than 230 papers. He gave an invited talk in the Combinatorics section at the International Congress of Mathematicians (ICM) in 2014, is a member of Academia Europaea and a fellow of the American Mathematical Society (AMS). Prof. Krivelevich is an Editor-in-Chief of Journal of Combinatorial Theory Series B (JCTB) and serves on the editorial boards of several other mathematical journals.