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

decidability; quantum graph; Artin's theorem; graph homomorphism density

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

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

Related Items

Unnamed Item, Definability in First Order Theories of Graph Orderings, The Inducibility of Graphs on Four Vertices, On the 3‐Local Profiles of Graphs, Positive graphs, Counting flags in triangle-free digraphs, From quasirandom graphs to graph limits and graphlets, On possible Turán densities, Positivstellensätze for quantum multigraphs, Paths vs. stars in the local profile of trees, Symmetric sums of squares over \(k\)-subset hypercubes, Strong forms of stability from flag algebra calculations, On the maximum density of fixed strongly connected subtournaments, Contractors for flows, Random graphons and a weak Positivstellensatz for graphs, On the Local Profiles of Trees

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item