Coloring linear hypergraphs: the Erdos-Faber-Lovasz conjecture and the Combinatorial Nullstellensatz

Janzer, Oliver and Nagy, Zoltán Lóránt (2022) Coloring linear hypergraphs: the Erdos-Faber-Lovasz conjecture and the Combinatorial Nullstellensatz. DESIGNS CODES AND CRYPTOGRAPHY, 90. pp. 1991-2001. ISSN 0925-1022

Preview

Text 2007.00685.pdf Download (962kB) | Preview

Abstract

The long-standing Erdos-Faber-Lovasz conjecture states that every n-uniform linear hypergaph with n edges has a proper vertex-coloring using n colors. In this paper we propose an algebraic framework to the problem and formulate a corresponding stronger conjecture. Using the Combinatorial Nullstellensatz, we reduce the Erdos-Faber-Lovasz conjecture to the existence of non-zero coefficients in certain polynomials. These coefficients are in turn related to the number of orientations with prescribed in-degree sequences of some auxiliary graphs. We prove the existence of certain orientations, which verifies a necessary condition for our algebraic approach to work.

Actions (login required)

Edit Item