THE MAXIMUM CUT PROBLEM ON BLOW-UPS OF MULTIPROJECTIVE SPACES.

Abstract. The maximum cut problem for a quintic del Pezzo surface Bl4(P2) 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 twelve. More generally, we obtain bounds for the maximum cut problem for the minuscule varieties Xa,b,c: = Blb+c(Pc−1)a−1 studied by Mukai and Castravet-Tevelev and show that these bounds are asymptotically sharp for infinite families. We prove our results by constructing embeddings of the classes of (−1)-divisors on these varieties which are optimal for the semidefinite relaxation of the maximum cut problem on graphs proposed by Goemans and Williamson. These results give a new optimality property of the Weyl orbits of root systems of type A,D and E. 1