The maximum cut problem on blow-ups of multiprojective spaces

The maximum cut problem for a quintic del Pezzo surface Bl ₄(â FOR VERIFICATION ™²) asks: Among all partitions of the 10 exceptional curves into two disjoint sets, what is the largest possible number of pairwise intersections? In this article we show that the answer is 12. More generally, we obtain bounds for the maximum cut problem for the minuscule varieties X _a,b,c :=Bl _b+c ((™ ^c-1) ^a-1) studied by Mukai and Castravet-Tevelev and show that these bounds are asymptotically sharp for infinite families and exact in some cases. The key to our results is the fact that certain natural embeddings of the classes of (-1)-divisors on these varieties are optimal for the semidefinite relaxation of the maximum cut problem on graphs proposed by Goemans and Williamson. These results are a new optimality property of Weyl orbits of root systems of type A,D and E. Motivated by our results on the varieties X _a,b,c we show that the Goemans-Williamson maxcut stochastic approximation algorithm has provably optimal asymptotic performance in symmetric strongly regular graphs of bounded spectra, in marked contrast with its worst-case behavior.