MaxCut in graphs with sparse neighborhoods

Let $G$ be a graph with $m$ edges and let $\mathrm{m}\mathrm{c}(G)$ denote the size of a largest cut of $G$. The difference $\mathrm{m}\mathrm{c}(G)-m\mathrm{/}2$ is called the surplus $\mathrm{s}\mathrm{p}(G)$ of $G$. A fundamental problem in MaxCut is to determine $\mathrm{s}\mathrm{p}(G)$ for $G$ without specific structure, and the degree sequence $d_1,\dots ,d_n$ of $G$ plays a key role in getting lower bounds of $\mathrm{s}\mathrm{p}(G)$. A classical example, given by Shearer, is that $\mathrm{s}\mathrm{p}(G)=\mathrm{\Omega }({\sum }_{i=1}^n{\sqrt{d}}_i)$ for triangle-free graphs $G$, implying that $\mathrm{s}\mathrm{p}(G)=\mathrm{\Omega }(m^{3\mathrm{/}4})$. It was extended to graphs with sparse neighborhoods by Alon, Krivelevich and Sudakov. In this paper, we establish a novel and stronger result for a more general family of graphs with sparse neighborhoods. Our result can derive many well-known bounds on surplus of $H$-free graphs for different $H$, such as triangles, even cycles, graphs having a vertex whose removal makes them acyclic, or complete bipartite graphs $K_{s,t}$ with $s\in \{2,3\}$. It can also deduce many new (tight) bounds on $\mathrm{s}\mathrm{p}(G)$ in $H$-free graphs $G$ when $H$ is any graph having a vertex whose removal results in a bipartite graph with relatively small Turán number, especially the even wheel. This contributes to a conjecture raised by Alon, Krivelevich and Sudakov. Moreover, we obtain new families of graphs $H$ such that $\mathrm{s}\mathrm{p}(G)=\mathrm{\Omega }(m^{3\mathrm{/}4+\epsilon (H)})$ for some constant $\epsilon (H)>0$ in $H$-free graphs $G$, giving evidences to a conjecture suggested by Alon, Bollobás, Krivelevich and Sudakov.