Computer Science/Discrete Mathematics Seminar I

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.