Alon-Tarsi for hypergraphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912174567325696 |
|---|---|
| author | Anholcer, Marcin Bosek, Bartłomiej Gutowski, Grzegorz Lasoń, Michał Przybyło, Jakub Serra, Oriol Tuczyński, Michał Vena, Lluís Zając, Mariusz |
| author_facet | Anholcer, Marcin Bosek, Bartłomiej Gutowski, Grzegorz Lasoń, Michał Przybyło, Jakub Serra, Oriol Tuczyński, Michał Vena, Lluís Zając, Mariusz |
| contents | Given a hypergraph $H=(V,E)$, define for every edge $e\in E$ a linear expression with arguments corresponding with the vertices. Next, let the polynomial $p_H$ be the product of such linear expressions for all edges. Our main goal was to find a relationship between the Alon-Tarsi number of $p_H$ and the edge density of $H$. We prove that $AT(p_H)=\lceil ed(H)\rceil+1$ if all the coefficients in $p_H$ are equal to $1$. Our main result is that, no matter what those coefficients are, they can be permuted within the edges so that for the resulting polynomial $p_H^\prime$, $AT(p_H^\prime)\leq 2\lceil ed(H)\rceil+1$ holds. We conjecture that, in fact, permuting the coefficients is not necessary. If this were true, then in particular a significant generalization of the famous 1-2-3 Conjecture would follow. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_00157 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Alon-Tarsi for hypergraphs Anholcer, Marcin Bosek, Bartłomiej Gutowski, Grzegorz Lasoń, Michał Przybyło, Jakub Serra, Oriol Tuczyński, Michał Vena, Lluís Zając, Mariusz Combinatorics Discrete Mathematics 05C65, 05C31, 05D40, 05C15 Given a hypergraph $H=(V,E)$, define for every edge $e\in E$ a linear expression with arguments corresponding with the vertices. Next, let the polynomial $p_H$ be the product of such linear expressions for all edges. Our main goal was to find a relationship between the Alon-Tarsi number of $p_H$ and the edge density of $H$. We prove that $AT(p_H)=\lceil ed(H)\rceil+1$ if all the coefficients in $p_H$ are equal to $1$. Our main result is that, no matter what those coefficients are, they can be permuted within the edges so that for the resulting polynomial $p_H^\prime$, $AT(p_H^\prime)\leq 2\lceil ed(H)\rceil+1$ holds. We conjecture that, in fact, permuting the coefficients is not necessary. If this were true, then in particular a significant generalization of the famous 1-2-3 Conjecture would follow. |
| title | Alon-Tarsi for hypergraphs |
| topic | Combinatorics Discrete Mathematics 05C65, 05C31, 05D40, 05C15 |
| url | https://arxiv.org/abs/2501.00157 |