ÍâÍøÌìÌÃ

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 upper 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 some representativeÌý°ù±ð²õ³Ü±ô³Ù²õ:ÌýAssuming delta(G)>=k, and for s<ck, adding about ns log n/kÌýrandom edges to G results with high probability in an s-connectedÌý²µ°ù²¹±è³ó;Ìý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.

Ìý

Ìý