English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $G$ be a graph with $m$ edges and let $\mathrm{mc}(G)$ denote the size ofa largest cut of $G$. The difference $\mathrm{mc}(G)-m/2$ is called the surplus$\mathrm{sp}(G)$ of $G$. A fundamental problem in MaxCut is to determine$\mathrm{sp}(G)$ for $G$ without specific structure, and the degree sequence$d_1,\ldots,d_n$ of $G$ plays a key role in getting lower bounds of$\mathrm{sp}(G)$. A classical example, given by Shearer, is that$\mathrm{sp}(G)=\Omega(\sum_{i=1}^n\sqrt d_i)$ for triangle-free graphs $G$,implying that $\mathrm{sp}(G)=\Omega(m^{3/4})$. It was extended to graphs withsparse neighborhoods by Alon, Krivelevich and Sudakov. In this paper, weestablish a novel and stronger result for a more general family of graphs withsparse neighborhoods.  Our result can derive many well-known bounds on surplus of $H$-free graphsfor different $H$, such as triangles, even cycles, graphs having a vertex whoseremoval 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{sp}(G)$ in$H$-free graphs $G$ when $H$ is any graph having a vertex whose removal resultsin a bipartite graph with relatively small Tur\'{a}n number, especially theeven wheel. This contributes to a conjecture raised by Alon, Krivelevich andSudakov. Moreover, we obtain new families of graphs $H$ such that$\mathrm{sp}(G)=\Omega(m^{3/4+\epsilon(H)})$ for some constant $\epsilon(H)>0$in $H$-free graphs $G$, giving evidences to a conjecture suggested by Alon,Bollob\'as, Krivelevich and Sudakov.

MaxCut in graphs with sparse neighborhoods