Undecidability of polynomial inequalities in tournaments
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916514172502016 |
|---|---|
| author | Chen, Hao Lin, Yupeng Ma, Jie Wei, Fan |
| author_facet | Chen, Hao Lin, Yupeng Ma, Jie Wei, Fan |
| contents | 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ász. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04972 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Undecidability of polynomial inequalities in tournaments Chen, Hao Lin, Yupeng Ma, Jie Wei, Fan Combinatorics 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ász. 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. |
| title | Undecidability of polynomial inequalities in tournaments |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.04972 |