Undecidability of linear inequalities in graph homomorphism densities

DOI10.1090/S0894-0347-2010-00687-XzbMath1259.05088arXiv1005.2382MaRDI QIDQ5390541

Hamed Hatami, Serguei Norine

Publication date: 4 April 2011

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

decidabilityquantum graphArtin's theoremgraph homomorphism density

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Subgraph densities in a surface ⋮ Random graphons and a weak Positivstellensatz for graphs ⋮ Definability in First Order Theories of Graph Orderings ⋮ Inducibility and universality for trees ⋮ Unnamed Item ⋮ On the Local Profiles of Trees ⋮ A path forward: tropicalization in extremal combinatorics ⋮ Tropicalization of graph profiles ⋮ From quasirandom graphs to graph limits and graphlets ⋮ Real algebraic geometry with a view toward Koopman operator methods. Abstracts from the workshop held March 12--17, 2023 ⋮ New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023 ⋮ THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE ⋮ Undecidability of polynomial inequalities in weighted graph homomorphism densities ⋮ Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting) ⋮ Symmetric sums of squares over \(k\)-subset hypercubes ⋮ Strong forms of stability from flag algebra calculations ⋮ On possible Turán densities ⋮ Positive graphs ⋮ Simple graph density inequalities with no sum of squares proofs ⋮ Positivstellensätze for quantum multigraphs ⋮ Semantic limits of dense combinatorial objects ⋮ On the maximum density of fixed strongly connected subtournaments ⋮ Paths vs. stars in the local profile of trees ⋮ The Inducibility of Graphs on Four Vertices ⋮ Counting flags in triangle-free digraphs ⋮ An Extremal Graph Problem with a Transcendental Solution ⋮ Contractors for flows ⋮ On the 3‐Local Profiles of Graphs ⋮ The feasible region of induced graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The homomorphism domination exponent
• Limits of dense graph sequences
• The coloring of graphs
• On Sets of Acquaintances and Strangers at any Party
• Reflection positivity, rank connectivity, and homomorphism of graphs
• On the Minimal Density of Triangles in Graphs
• Flag algebras