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

rogramming.

This is based on a paper that appeared in LATIN and was joint work with Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, and Luca Trevisan. In additional to discussing this project (and it's already published paper), I will briefly remark about the experience of working with Luca (as a young queer PhD student).

The following is a brief abstract about the research talk:

"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 talk we propose an approach, based on semidefinite programming (SDP), to prove lower bounds on f(G). We discuss how this approach can be used to find large cuts in graphs with few triangles and in K_r-free graphs. This nicely generalizing the already established results for bounding f(G) when G is triangle-free (See https://lucatrevisan.wordpress.com/2017/09/16/beyond-worst-case-analysi…)."