REVIEW 2 cited by
Undecidability of polynomial inequalities in tournaments
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
Many fundamental problems in extremal combinatorics are equivalent to proving certain polynomial inequalities in graph homomorphism densities. In 2011, a breakthrough result by Hatami and Norine showed that it is undecidable to verify polynomial inequalities in graph homomorphism densities. Recently, Blekherman, Raymond and Wei extended this result by showing that it is also undecidable to determine the validity of polynomial inequalities in homomorphism densities for weighted graphs with edge weights taking real values. These two results resolved a question of Lov\'asz. In this paper, we consider the problem of determining the validity of polynomial inequalities in digraph homomorphism densities for tournaments. We prove that the answer to this problem is also undecidable.
Forward citations
Cited by 2 Pith papers
-
On Domination Exponents for Pairs of Graphs
Exact homomorphism density domination exponents are determined for all path pairs and for even cycles against Hamiltonian-cycle graphs, with asymptotically sharp bounds for odd cycles.
-
Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies
Deciding whether an arbitrary integer polynomial in subset densities and additive energies is nonnegative for all subsets of all finite abelian groups is undecidable.
Discussion (0). Continue with ORCID to comment.