Geodesic
The maximum cut problem on blow-ups of multiprojective spaces
Journal of Algebraic Combinatorics, Tome 38 (2013) no. 4, pp. 797-827.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

The maximum cut problem for a quintic del Pezzo surface Bl$_{4}(\mathbb P^{2})$ 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 }((\mathbb P^{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.
Classification : 14N05, 14C17, 05C85, 05C22
Keywords: blow-ups of multiprojective space, maximum cut problem, Goemans-Williamson algorithm 
@article{JAC_2013__38_4_a9,
     author = {Junca, Mauricio and Velasco, Mauricio},
     title = {The maximum cut problem on blow-ups of multiprojective spaces},
     journal = {Journal of Algebraic Combinatorics},
     pages = {797--827},
     publisher = {mathdoc},
     volume = {38},
     number = {4},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2013__38_4_a9/}
}
TY  - JOUR
AU  - Junca, Mauricio
AU  - Velasco, Mauricio
TI  - The maximum cut problem on blow-ups of multiprojective spaces
JO  - Journal of Algebraic Combinatorics
PY  - 2013
SP  - 797
EP  - 827
VL  - 38
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2013__38_4_a9/
LA  - en
ID  - JAC_2013__38_4_a9
ER  - 
%0 Journal Article
%A Junca, Mauricio
%A Velasco, Mauricio
%T The maximum cut problem on blow-ups of multiprojective spaces
%J Journal of Algebraic Combinatorics
%D 2013
%P 797-827
%V 38
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2013__38_4_a9/
%G en
%F JAC_2013__38_4_a9
Junca, Mauricio; Velasco, Mauricio. The maximum cut problem on blow-ups of multiprojective spaces. Journal of Algebraic Combinatorics, Tome 38 (2013) no. 4, pp. 797-827. http://geodesic.mathdoc.fr/item/JAC_2013__38_4_a9/