%0 Generic %1 carlson2018lower %A Carlson, Charles %A Kolla, Alexandra %A Li, Ray %A Mani, Nitya %A Sudakov, Benny %A Trevisan, Luca %D 2018 %K combinatorics maxcut %T Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming %U http://arxiv.org/abs/1810.10044 %X For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming (SDP), to prove lower bounds on $f(G)$. We use this approach to find large cuts in graphs with few triangles and in $K_r$-free graphs.

@misc{carlson2018lower, abstract = {For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming (SDP), to prove lower bounds on $f(G)$. We use this approach to find large cuts in graphs with few triangles and in $K_r$-free graphs.}, added-at = {2022-02-14T08:28:29.000+0100}, author = {Carlson, Charles and Kolla, Alexandra and Li, Ray and Mani, Nitya and Sudakov, Benny and Trevisan, Luca}, biburl = {https://www.bibsonomy.org/bibtex/239609029a4907955177da137f0e540b3/iliyasnoman}, description = {Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming}, interhash = {11672dedf8b7f301f5af65c07e9eff21}, intrahash = {39609029a4907955177da137f0e540b3}, keywords = {combinatorics maxcut}, note = {cite arxiv:1810.10044Comment: 21 pages, to be published in LATIN 2020 proceedings, Updated version is rewritten to include additional results along with corrections to original arguments}, timestamp = {2022-02-14T08:28:29.000+0100}, title = {Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming}, url = {http://arxiv.org/abs/1810.10044}, year = 2018 }