MaxCut in H)-Free Graphs

For a graph G, let f(G) denote the maximum number of edges in a cut of G. For an integer m and for a fixed graph H, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as G ranges over all graphs on m edges that contain no copy of H. In this paper we study this function for various graphs H. In particular we show that for any graph H obtained by connecting a single vertex to all vertices of a fixed nontrivial forest, there is a $c(H) >0$ such that f(m,H) ≥ m/2 + c(H) m4/5, and that this is tight up to the value of $c(H)$. We also prove that for any even cycle C₂ₖ there is a $c(k)>0$ such that f(m,C₂ₖ) ≥ m/2 + c(k) m(2k+1)/(2k+2), and that this is tight, up to the value of $c(k)$, for 2k∈ \4,6,10\. The proofs combine combinatorial, probabilistic and spectral techniques.