***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Michael Krivelevich (Tel Aviv U)

Thursday 8th September, 3:00 in Fine Hall 224.

Title:  Improving a graph's parameters through random perturbation
 
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 results:

- 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 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.

Joint work with Elad Aigner-Horev and Dan Hefetz.  

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)