Tropicalization of graph profiles
From MaRDI portal
Abstract: A graph profile records all possible densities of a fixed finite set of graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known, and little is known about hypergraph profiles. We introduce the tropicalization of graph and hypergraph profiles. Tropicalization is a well-studied operation in algebraic geometry, which replaces a variety (the set of real or complex solutions to a finite set of algebraic equations) with its "combinatorial shadow". We prove that the tropicalization of a graph profile is a closed convex cone, which still captures interesting combinatorial information. We explicitly compute these tropicalizations for arbitrary sets of complete and star hypergraphs. We show they are rational polyhedral cones even though the corresponding profiles are not even known to be semialgebraic in some of these cases. We then use tropicalization to prove strong restrictions on the power of the sums of squares method, equivalently Cauchy-Schwarz calculus, to test (which is weaker than certification) the validity of graph density inequalities. In particular, we show that sums of squares cannot test simple binomial graph density inequalities, or even their approximations. Small concrete examples of such inequalities are presented, and include the famous Blakley-Roy inequalities for paths of odd length. As a consequence, these simple inequalities cannot be written as a rational sum of squares of graph densities.
Recommendations
Cites work
- scientific article; zbMATH DE number 3722700 (Why is no real title available?)
- scientific article; zbMATH DE number 193053 (Why is no real title available?)
- scientific article; zbMATH DE number 3489128 (Why is no real title available?)
- scientific article; zbMATH DE number 6437647 (Why is no real title available?)
- scientific article; zbMATH DE number 3189757 (Why is no real title available?)
- An approximate version of Sidorenko's conjecture
- Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
- Enumerative tropical algebraic geometry in ℝ²
- Flag algebras
- Graphs with maximal number of adjacent pairs of edges
- Large networks and graph limits
- Logarithmic limit sets of real semi-algebraic sets
- On 3-hypergraphs with forbidden 4-vertex configurations
- On the 3-local profiles of graphs
- On the Minimal Density of Triangles in Graphs
- On the boundary of the region defined by homomorphism densities
- On the number of pentagons in triangle-free graphs
- Positivstellensätze for quantum multigraphs
- Property testing and its connection to learning and approximation
- Random graphons and a weak positivstellensatz for graphs
- Simple graph density inequalities with no sum of squares proofs
- Some advances on Sidorenko's conjecture
- Sum of squares lower bounds from symmetry and a good story
- Symmetry in Turán sums of squares polynomials from flag algebras
- The clique density theorem
- The number of cliques in graphs of given order and size
- Tropical spectrahedra
- Tropicalizing the positive semidefinite cone
- Two approaches to Sidorenko's conjecture
- Undecidability of linear inequalities in graph homomorphism densities
Cited in
(8)- Undecidability of linear inequalities in graph homomorphism densities
- A path forward: tropicalization in extremal combinatorics
- On the 3-local profiles of graphs
- Asymptotic spectra: theory, applications, and extensions
- Tropicalizing the Graph Profile of Some Almost-Stars
- Positivstellensätze for quantum multigraphs
- Moments, sums of squares, and tropicalization
- Power mean inequalities and sums of squares
This page was built for publication: Tropicalization of graph profiles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5098834)
