Alon–Tarsi for hypergraphs

Marcin Anholcer, Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń, Jakub Przybyło, Oriol Serra, Michał Tuczyński, Lluís Vena, Mariusz Zając · 2025

Read Alon–Tarsi for hypergraphs by Marcin Anholcer, Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń, Jakub Przybyło, Oriol Serra, Michał Tuczyński, Lluís Vena, Mariusz Zając (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00157.txt.

Description

The Alon-Tarsi number links a polynomial built from a network to how that network can be colored or listed. Marcin Anholcer and co-authors extend that link in this paper, first published in 2024, from plain graphs to hypergraphs, where each edge can join many vertices at once.

They prove an exact formula when all edge coefficients are equal and the number system is tame. When coefficients differ, the coefficients can be shuffled within edges to keep the number within twice that bound. The authors conjecture the bound holds with no shuffling at all, which would settle a sweeping generalization of a famous coloring conjecture.

Catalog record

CREATORMarcin Anholcer, Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń, Jakub Przybyło, Oriol Serra, Michał Tuczyński, Lluís Vena, Mariusz Zając
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-00157

Browse the full library · About the Tower of Babel