TY - GEN
T1 - Lower Bounds for Max-Cut via Semidefinite Programming
AU - Carlson, Charles
AU - Kolla, Alexandra
AU - Li, Ray
AU - Mani, Nitya
AU - Sudakov, Benny
AU - Trevisan, Luca
N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - 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 Kr-free graphs.
AB - 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 Kr-free graphs.
KW - K-free graphs
KW - Max-Cut
KW - Semidefinite programming
UR - https://www.scopus.com/pages/publications/85097720344
U2 - 10.1007/978-3-030-61792-9_38
DO - 10.1007/978-3-030-61792-9_38
M3 - Conference contribution
AN - SCOPUS:85097720344
SN - 9783030617912
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 479
EP - 490
BT - LATIN 2020
A2 - Kohayakawa, Yoshiharu
A2 - Miyazawa, Flávio Keidi
PB - Springer Science and Business Media Deutschland GmbH
T2 - 14th Latin American Symposium on Theoretical Informatics, LATIN 2020
Y2 - 5 January 2021 through 8 January 2021
ER -