March 2, 3:30pm, Wean 8220

Michael Krivelevich, Tel Aviv University

Improving graph's parameters through random perturbation

Michael Krivelevich, Tel Aviv University

Improving graph's parameters through random perturbation

Abstract:

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, launched in a paper by Bohman,
Frieze and Martin from 2003). Here are representative results, in
a somewhat approximate form:

- Assuming $\delta(G)\ge 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)\le t$ and adding $c$n random edges to $G$ typically produces a graph containing a minor of a graph of average degree of order $n/\sqrt t$.

A joint work with Elad Aigner-Horev and Dan Hefetz.