Source-linked AI summary
Solving Large SDPs from Flag Algebra Problems
Bernard Lidický, Jan Volec
TL;DR
Flag-algebra relaxations grow rapidly with the number of admissible configurations, making large instances difficult for standard SDP solvers. The paper applies linear programming with cutting planes to approximate these relaxations, reaching instances with almost 10,000,000 coefficient constraints and reporting bounds for 3-graphs, including seven-vertex cases.
Problem
Flag-algebra bounds typically strengthen at larger orders, but the rapidly growing number of constraints makes large semidefinite programs difficult to solve.
Source: §1 · p. 1Method
The authors approximate flag-algebra SDP solutions with linear programming and cutting planes, adding constraints iteratively while retaining feasible solutions.
Source: §4 · pp. 6–7Results
Takeaways & Limitations
The authors report a systematic approach that solves flag-algebra problems at larger instances than previous methods.
Source: §8 · p. 13The cutting-plane procedure guarantees neither strict objective improvement at each iteration nor finite termination.
Source: §4 · p. 7
Abstract
from arXiv · showhide
The flag algebra method is a general tool in extremal combinatorics, which has been useful in tackling open problems concerning graphs, hypergraphs, permutations, point sets, and other structures. The method establishes combinatorial inequalities via sums of squares, which are usually obtained by a semidefinite relaxation of the original combinatorial problem. A typical application of the method in graph theory starts with fixing a parameter $n$ followed by constructing a semidefinite program based on the (subgraph) structure of all $n$-vertex graphs. In the standard formulation before symmetry reductions, there is a coefficient constraint for every admissible $n$-vertex graph up to isomorphism. For 3-uniform hypergraphs, there are 2,136 of them on 6 vertices and 7,013,320 on 7 vertices. While solving the resulting program for $n=6$ is an easy task on any modern computer, the programs for $n = 7$ seems out of reach, mainly because the SDP solvers need too much RAM. Yet solving such programs for as large $n$ as possible is desirable because they typically yield better bounds for the original combinatorial problems. We bypass the aforementioned memory requirements by linear programming with cutting planes. Although we do not guarantee that this cutting-plane procedure reaches an optimum in finitely many iterations, in many flag algebra instances it uses much less memory and yields improved bounds for well-known hypergraph Tur\'an problems. We use this method to obtain numerical bounds for Tur\'an densities and codegree squared densities of several 3-uniform hypergraphs including the tetrahedron, where we obtained the upper bound 0.55753 and tetrahedron without one edge with a new upper bound 0.2865. It also allows to tackle bounds on Tur\'an densities of 7-vertex 3-graphs using flag algebras, which was not possible before.
1 Introduction
Flag algebras turn extremal-combinatorics questions into semidefinite relaxations built from subgraph densities. Because the number of constraints grows rapidly with the chosen order, this paper applies cutting planes to approximate solutions at a scale difficult for standard solvers.
1 Introduction
- Flag algebras seek non-negative asymptotic inequalities expressed as sums of squares of small induced-subgraph densities through semidefinite relaxation.The method has applications across extremal combinatorics, including graphs, hypergraphs, permutations, and other structures.Source: §1 · p. 1
- A standard formulation has one coefficient constraint per admissible n-vertex graph or hypergraph up to isomorphism, and larger n typically gives stronger bounds.The number of configurations grows rapidly for unrestricted r-graphs; forbidden-subgraph restrictions can reduce it.Source: §1 · pp. 1–2
- CSDP instances with more than 500,000 configurations are exceptional computational challenges, mainly because of memory use.MOSEK can be faster but requires even more memory.Source: §1 · p. 2
- The authors apply a cutting-plane method to flag-algebra instances with almost 10,000,000 coefficient constraints.Even a partially solved order-n relaxation can improve on the optimum at order n−1.Source: §1 · p. 2
- The introduction situates the method in a paper presenting new bounds and describing the cutting-plane approach in a later section.Some numerical bounds close to conjectured exact values allowed certificates for rounded tight bounds.Source: §1 · p. 2
2 Results on 3-graphs
The section reports numerical bounds for Turán densities and codegree-squared densities of 3-graphs, using calculations that can reach larger instances than standard approaches. The reported runs stop when progress becomes small, so the bounds are not established as optimal.
2 Results on 3-graphs
- The method is particularly useful for 3-graph Turán problems, where moving from six to seven vertices can improve numerical bounds but seven-vertex instances are typically out of reach.There are 2,136 non-isomorphic 3-graphs on six vertices and 7,013,320 on seven; calculations stopped when progress became small, and longer runs may improve the bounds.Source: §2 · p. 2
- The reported bounds cover both Turán density and its ℓ2 variant, with the latter described as slightly more approachable because maximizers are more often unique.The ℓ2 variant concerns the norm of the vector of pair codegrees, with a normalized asymptotic maximum defined for F-free 3-graphs.Source: §2 · p. 3
- The section tests the implementation on selected 3-graphs and summarizes its bounds alongside the best known values at the time of writing.A separate table summarizes SDP sizes and resources required to solve them.Source: §2 · p. 3
3 Introduction to Flag Algebras
This section introduces flag algebras through graphs, then describes how their inequalities yield semidefinite relaxations for Turán densities and their ℓ2 variant. Its scope is introductory rather than comprehensive.
3 Introduction to Flag Algebras
- The section presents a brief, graph-focused introduction rather than a comprehensive treatment, although the method applies to other combinatorial structures.The table captions identify reported bounds and program-size and resource summaries.Source: §3 · p. 3, Table 2 · p. 4, Table 3 · p. 4
- The introduction defines graph notation and flags: a flag is a graph with a fixed labeled copy of a type, and isomorphisms preserve that labeling.It defines the family of non-isomorphic flags, their induced flag densities, and pair densities.Source: §3 · pp. 3–5
- Flag algebras form a quotient algebra of formal linear combinations of flags, with multiplication defined using pair densities.For the null type, a flag is identified with its underlying graph.Source: §3 · p. 5
- The framework connects graph limits to positive homomorphisms, allowing valid subgraph-counting inequalities to be generated from squares of linear combinations of flags.Every graph sequence has a convergent subsequence, and the limit-object homomorphisms correspond to convergent sequences.Source: §3 · pp. 5–6
3.1 The Turán densities π(·) and πℓ2(·) in Flag Algebras
- For a fixed forbidden hypergraph, flag-algebra relaxations are organized by order k, with inequalities rewritten as linear combinations of k-vertex subgraph densities.The Turán-density ℓ2 objective can also be expressed as a linear combination of densities of 4-vertex 3-graphs.Source: §3.1 · p. 6
4 Solving large Flag Algebra relaxations
The section adapts an established cutting-plane approach to large flag-algebra SDPs by replacing positive-semidefinite constraints with iteratively added linear cuts. It illustrates the approach on Mantel’s theorem and describes certificate generation, implementation, and verification.
4 Solving large Flag Algebra relaxations
- Each iteration solves a linear relaxation, then adds a cut from a negative-eigenvalue direction when a block is not positive semidefinite.Cuts preserve feasible solutions and make the relaxation’s minimum nondecreasing, but strict improvement and finite termination are not guaranteed.Source: §4 · pp. 6–7
4.1 Application to flag algebras
- In the Mantel example, the successive cuts bring the LP objective to 1.500002283054241, close to the optimum 1.5.The reported solution has y1 = 0.24999885847287948, y2 = 0, and y3 = 0.7500011415271205, matching the stated combinatorial solution.Source: §4.1 · p. 9
4.2 Certificate of correctness
- Dual solutions yield certificates as linear combinations of sums of squares, with eigenvectors supplying square coefficients and LP dual variables supplying combination coefficients.The certificate does not require the original semidefinite program and is described as compact.Source: §4.2 · p. 9
4.3 Implementation
- The authors provide C and C++ implementations, using MOSEK or GUROBI for the linear programs, and report good performance when few objective coefficients are large.Memory and time per iteration grow as cuts accumulate; checkpoints allow runs stopped by time or memory limits to restart from a smaller retained constraint set.Source: §4.3 · p. 10
4.4 Software for verification
- A separate C program verifies upper bounds by generating flag-algebra coefficients in parallel and using interval arithmetic to evaluate the stored dual certificates.It uses OpenMP, MPFI, and MPFR.Source: §4.4 · p. 10
5 Constructions
The section presents explicit constructions giving lower bounds for several 3-graph Turán and codegree-squared densities, with separate constructions for F4−,2, F4,2, and J5.
5.1 A construction for π (F4−,2) ≥
- For F4−,2, the five-part Hn construction yields π(F4−,2) ≥ 86/175 and ℓ2(F4−,2) ≥ 1552/5375.Hn includes triples meeting three distinct parts and inserts a K4−-free 3-graph of density 2/7 inside each part.Source: §5.1 · p. 11
5.2 A construction for π (F4,2) ≥0.618782 and ℓ2 (F4,2) ≥0.4240915
- For F4,2, the Xn construction yields π(F4,2) ≥ 0.618782 and πℓ2(F4,2) ≥ 0.4240915.The authors choose a simpler construction although they note that splitting A may further improve its Turán-density bound.Source: §5.2 · p. 12
5.3 A construction for π (J5) ≥
- For J5, the iterated blow-ups of P yield π(J5) ≥ 9/14 and πℓ2(J5) ≥ 27/61.P is formed from the noncollinear triples of PG(2, 3); its vertex links are K3,3,3,3, which is K5-free.Source: §5.3 · p. 12
6 New results using CSDP
The section reports CSDP’s C5 bound and an improved bound for the inducibility of P4. It also notes that the calculations are available with the paper’s other results.
6 New results using CSDP
- CSDP gives π(C5) ≤ 0.465031, slightly better than the method’s π(C5) ≤ 0.46507, using a reported 1,855 GB allocation.The allocation allowed the instance to run on a machine with approximately 2 TB of RAM, subject to additional memory overhead.Source: §6 · p. 12
- Using 9-vertex subgraph densities, the paper improves the upper bound to I(P4) ≤ 0.20332375.The prior best known bound used flag algebras on 8 vertices; P4 is self-complementary, allowing symmetry reduction for the 9-vertex calculation.Source: §6 · pp. 12–13
- The solutions for π(C5) and I(P4) are available together with the paper’s other calculations.Source: §6 · p. 13
7 Graph drawing and other applications
This section discusses graph-drawing conjectures and flag-algebra bounds, alongside applications to 4-graph Turán problems and hypercube Turán density.
7 Graph drawing and other applications
- The section defines cr(G) as the minimum pairwise edge crossings in a plane drawing and introduces Hill’s conjecture for cr(Kn).Source: §7 · p. 13
- Using this paper’s solver and method, Balogh et al. improved flag-algebra lower bounds to cr(Kn,n) ≥ (0.96937 − o(1))·Z(n,n) and cr(Kn) ≥ (0.9899 − o(1))·H(n).The earlier bounds were (0.9118 − o(1))·Z(n,n) and (0.985 − o(1))·H(n), respectively.Source: §7 · p. 13
- A follow-up paper with Pfender and Sankar proves the referenced 4-graph Turán conjecture, which Corrêa also reported resolving.The passage gives the value 31/64 for the Turán density of K(4)5.Source: §7 · p. 13
- For πQ(C4), Layman and Lidický claimed the method could push the upper bound below 0.59143.Earlier flag-algebra work gave πQ(C4) ≤ 0.6068.Source: §7 · p. 13
8 Conclusion
The conclusion presents a systematic approach for solving larger flag-algebra relaxations and identifies current scale limits for 3-graphs. It notes that bounds may improve with more solver time or regularity constraints.
8 Conclusion
- The approach solves larger semidefinite-relaxation instances than previous methods, though the reported bounds could improve with more solver time or regularity constraints.The constraints correspond to a flag-algebra translation of Zykov’s symmetrization argument.Source: §8 · p. 13
- For 3-graphs, the authors expect current methods to reach at most 7-vertex densities; f8 > 10^12 makes 8-vertex densities unlikely in the near future.Source: §8 · p. 13
- For undirected graphs, calculations using 10-vertex densities appear promising.Source: §8 · p. 13
9 Use of AI
The authors describe which research and editorial tasks they performed themselves and where ChatGPT-6 assisted. They report checking the paper’s content for correctness.
9 Use of AI
- The authors say they alone developed the hypergraph Turán approach, solver implementation, bound verifiers, and particular applications.Source: §9 · p. 13
- ChatGPT-6 helped find constructions in Sections 5.1–5.3 and obtain exact rounding for dagger-marked Table 2 entries, which the authors verified programmatically.Source: §9 · p. 13
- ChatGPT-6 also assisted with English correction and mathematical-error checks; the authors state they checked all paper content for correctness.Source: §9 · p. 13