Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming

Autor:	Carlson, Charles, Kolla, Alexandra, Li, Ray, Mani, Nitya, Sudakov, Benny, Trevisan, Luca
Rok vydání:	2018
Předmět:	Computer Science - Data Structures and Algorithms Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	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. Comment: 21 pages, to be published in LATIN 2020 proceedings, Updated version is rewritten to include additional results along with corrections to original arguments
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1810.10044 Zobrazit plný text záznamu View this record from Arxiv