The maximum cut problem on blow-ups of multiprojective spaces (Q2435039): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2160295603 / rank | |||
Normal rank |
Revision as of 19:09, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The maximum cut problem on blow-ups of multiprojective spaces |
scientific article |
Statements
The maximum cut problem on blow-ups of multiprojective spaces (English)
0 references
3 February 2014
0 references
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.
0 references
blow-ups of multiprojective space
0 references
maximum cut problem
0 references
Goemans-Williamson algorithm
0 references