## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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

## Perfectly balanced partitions of smoothed graphs

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

Information for students and suggested topics for student talks