Combinatorics Seminar
When: Sunday, Dec. 19, 10am
Where: Schreiber 309
Speaker: Benny Sudakov, Princeton University
Title: Max Cut - a combinatorial perspective
Abstract:
The well-known Max Cut problem asks for the largest bipartite subgraph of a
graph G. This problem has been the subject of extensive research, both from
the algorithmic perspective in computer science and the extremal perspective
in combinatorics. Let n be the number of vertices and e the number
edges of G, and let b(G) denote the size of the largest bipartite
subgraph of G. The extremal part of the Max Cut problem asks to estimate
b(G) as a function of n and e. This question was first raised almost
forty years ago and attracted a lot of attention since then.
In this talk we survey some old and recent bounds on the size of the largest
bipartite subgraphs for various classes of graphs and obtain some new
results. In particular we show that every K_4-free graph G with n
vertices can be made bipartite by deleting at most n^2/9 edges. This
proves an old conjecture of Erdos.