Undecidability of polynomial inequalities in weighted graph homomorphism densities

DOI10.1017/FMS.2024.19MaRDI QIDQ6131051zbMATH OpenFDO

Authors

Publication date 4 April 2024

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2207.12378

zbMATH Keywords

homomorphism densities of graphspolynomial inequalities

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Extremal problems in graph theory (05C35) Decidability and field theory (12L05)

Abstract: Many problems and conjectures in extremal combinatorics concern polynomial inequalities between homomorphism densities of graphs where we allow edges to have real weights. Using the theory of graph limits, we can equivalently evaluate polynomial expressions in homomorphism densities on kernels $W$, i.e., symmetric, bounded, and measurable functions $W$ from $[0,1{]}^{2}omathbbR$. In 2011, Hatami and Norin proved a fundamental result that it is undecidable to determine the validity of polynomial inequalities in homomorphism densities for graphons (i.e., the case where the range of $W$ is $[0,1]$, which corresponds to unweighted graphs, or equivalently, to graphs with edge weights between $0$ and $1$). The corresponding problem for more general sets of kernels, e.g., for all kernels or for kernels with range $[-1,1]$, remains open. For any $a>0$, we show undecidability of polynomial inequalities for any set of kernels which contains all kernels with range $0,a$. This result also answers a question raised by Lov'asz about finding computationally effective certificates for the validity of homomorphism density inequalities in kernels.

Recommendations

• Undecidability of linear inequalities in graph homomorphism densities
• Simple graph density inequalities with no sum of squares proofs
• A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
• Solvability of Graph Inequalities
• On a theorem of Lovász that \((\cdot, H)\) determines the isomorphism type of \(H\)

Cites work

• A correlation inequality for bipartite graphs
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Explicit Ramsey graphs and orthonormal labelings
• Flag algebras
• scientific article; zbMATH DE number 4135981 (Why is no real title available?)
• scientific article; zbMATH DE number 3508542 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• Large networks and graph limits
• Non-bipartite \(k\)-common graphs
• On the local approach to Sidorenko's conjecture
• On the Minimal Density of Triangles in Graphs
• Random graphons and a weak positivstellensatz for graphs
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
• Undecidability of linear inequalities in graph homomorphism densities

Cited in

(7)

• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Ubiquity of power sums in graph profiles
• Undecidability of polynomial inequalities in subset densities and additive energies
• Undecidability of polynomial inequalities in tournaments
• MFO-RIMS tandem workshop: Optimization, theoretical computer science and algebraic geometry: convexity and beyond. Abstracts from the MFO-RIMS tandem workshop held February 16--21, 2025
• Undecidability of polynomial inequalities in subset densities and additive energies
• The wonderful geometry of the Vandermonde map

This page was built for publication: Undecidability of polynomial inequalities in weighted graph homomorphism densities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131051)