Abstract:Given a hypergraph $H=(V,E)$, define for every edge $e\in E$ a linear expression with arguments corresponding to the vertices. Next, let the polynomial $p_H$ be the product of such linear expressions for all edges. Our main goal is 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 \mathrm{ed}(H)\rceil+1$ if all the coefficients in $p_H$ are equal to $1$ and the base field has characteristic zero. Our main result is that, over an arbitrary field, if on every edge the coefficients are not all equal, then they can be permuted within the edges so that for the resulting polynomial $p_H^\prime$, $AT(p_H^\prime)\leq 2\lceil \mathrm{ed}(H)\rceil+1$ holds. We conjecture that this bound holds for every hypergraph polynomial without permuting its coefficients. If this were true, then in particular a significant generalization of the famous 1-2-3 Conjecture would follow.
From: Bartłomiej Bosek [view email]
[v1]
Mon, 30 Dec 2024 22:02:05 UTC (23 KB)
[v2]
Tue, 18 Aug 2026 22:34:28 UTC (24 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。