The maximum cut problem on blow-ups of multiprojective spaces (Q2435039)

Let \(X_{a,b,c}\) be the blow-up of the multiprojective space \((\mathbb{P}^{c-1})^{a-1}\) at \(b+c\) points in general position. In this article the following problem is being investigated: ``Among all partitions of the \((-1)\)-divisors on \(X_{a,b,c}\) into two sets, what is the largest possible number of pairwise intersections?'' (p. 798) The original question about \((-1)\)-divisors is translated into a maximal cut problem on graphs \(G_{a,b,c}\), where vertices of \(G_{a,b,c}\) correspond to \((-1)\)-divisors on \(X_{a,b,c}\) and an edge between distinct vertices \(U\) and \(V\) has weight \(U \cdot V\). The Goemans-Williamson semidefinite relaxation algorithm is used to find bounds on the maximal cut of \(G_{a,b,c}\). In particular, upper and lower bounds for the following four classes of graphs \(G_{a,b,c}\) are derived: \(G_{s+1,1,n+1}\), \(G_{2,2,n}\), \(G_{2,3,3}\) and \(G_{2,4,3}\). It is shown that for the first two families the upper bounds are asymptotically sharp and for the families \(G_{2,2,n}\) and \(G_{n+1,1,n+1}\) the values of the maximum cuts coincide with the upper bounds.