The maximum cut problem on blow-ups of multiprojective spaces

2012/07/17 by Mauricio Velasco, Velasco, Mauricio Junca Mauricio
Mathematics · #14N10 (Primary) 05C35 #52A27 (Secondary) #Algebraic Geometry (math.AG) #Algebraic Geometry and Number Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Optimization and Control (math.OC) #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.1207.4027

openalex publication_date 2012/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The maximum cut problem for a quintic del Pezzo surface \rm Bl₄(ℙ²) 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 X_a,b,c:=\rm Bl_b+c(ℙ^c-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.

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Related

• Packing curves on surfaces with few intersections
• On curves with high multiplicity on ℙ(a,b,c) for min(a,b,c)≤4
• Concurrent lines on del Pezzo surfaces of degree one
• On an analogue of the Markov equation for exceptional collections of length 4
• Intersection of curves in projective 4 space