Solving Large SDPs from Flag Algebra Problems
Abstract
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án problems. We use this method to obtain numerical bounds for Turán 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án densities of 7-vertex 3-graphs using flag algebras, which was not possible before.
Related
- Solving Large-Scale Sparse Linear Complementarity Problems Using a Relaxed Shifted Matrix-Splitting Modulus-Based Iteration Method
- McADMM: A Multi-Clique Augmented Lagrangian-Based Algorithm for Large-Scale Sparse SDPs with Bound Constraints
- Solving Inverse Dirac-weighted Sturm-Liouville Problems via Cauchy problems
- Solving Multiobjective Linear Set Optimization Problems
- Error Analysis for Solving Elliptic Interface Problems with Randomized Neural Networks
BibTeX
@misc{lidicky2026solving,
title = {{Solving Large SDPs from Flag Algebra Problems}},
author = {Bernard Lidický and Jan Volec},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33850},
eprint = {2610.33850},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33850},
}
RIS
TY - UNPB
TI - Solving Large SDPs from Flag Algebra Problems
AU - Bernard Lidický
AU - Jan Volec
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33850
UR - https://arxiv.org/abs/2610.33850
AB - 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án problems. We use this method to obtain numerical bounds for Turán 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án densities of 7-vertex 3-graphs using flag algebras, which was not possible before.
ER -