pith. sign in

arxiv: 2501.00157 · v1 · pith:LTF4AWJTnew · submitted 2024-12-30 · 🧮 math.CO · cs.DM

Alon-Tarsi for hypergraphs

classification 🧮 math.CO cs.DM
keywords coefficientsalon-tarsiconjectureedgeedgeslceillinearmain
0
0 comments X
read the original abstract

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.

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.