The reviewed record of science sign in
Pith

arxiv: 2412.04972 · v2 · pith:6CLJTWBW · submitted 2024-12-06 · math.CO

Undecidability of polynomial inequalities in tournaments

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:6CLJTWBWrecord.jsonopen to challenge →

classification math.CO
keywords inequalitiespolynomialdensitieshomomorphismundecidablegraphproblemresult
0
0 comments X
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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.