2024/12/30 by Marcin Anholcer, Bartłomiej Bosek, Anholcer, Marcin +15
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2501.00157
Given a hypergraph H=(V,E), define for every edge e∈ E a linear expression with arguments corresponding with the vertices. Next, let the polynomial pH be the product of such linear expressions for all edges. Our main goal was to find a relationship between the Alon-Tarsi number of pH and the edge density of H. We prove that AT(pH)=\lceil ed(H)\rceil+1 if all the coefficients in pH 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 pH^′, AT(pH^′)≤ 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.