Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 16, 2008, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Michael Krivelevich (Tel Aviv Univ.)
Let H be a graph on n vertices, where n is even. An equipartition V(H)=(V_1,V_2) is called perfectly balanced if both parts V_1, V_2 span the same number of edges. It is quite easy to see that not every graph has a perfectly balanced or even nearly perfectly balanced partition. Yet, a little use of randomness does wonders here (too): we prove that a random graph G, obtained from H by flipping every non-edge of H into an edge and every edge of H into a non-edge independently and with probability p=p(n) (i.e. G is a smoothened version of H), has a perfectly balanced partition with probability exponentially close to 1, as long as all degrees in H differ by at most \delta n, p(n) satisfies: \epsilon/n < p(n) <1-\epsilon n, and \delta is small enough compared to \epsilon. As a consequence we derive that the random graph G(n,p) (n is even again) has a perfectly balanced partition almost surely, for any choice of the edge probability p(n).
Joint work with Ido Ben-Eliezer (Tel Aviv Univ.).
Automatic MiSe System Software Version 1.4803M | admin login