Graphs and Matroids | Emanuel Juliano Morais Silva, On the connection between max-cuts, the vector chromatic number, and random sphere graphs

Abstract: It is well known that the maximum cut size of a graph is at least half its number of edges. But how small can this difference be? Using random hyperplane rounding, a technique from semidefinite optimization, Balla, Janzer, and Sudakov obtained a lower bound on this difference in terms of the vector chromatic number, recovering known extremal bounds for $C_r$-free graphs. I will present their argument and show that the constant in their vector-chromatic bound is optimal by constructing a random sphere graph.