Description
Absztrakt.
The long-standing Erdos--Faber--Lov\'asz conjecture states that every $n$-uniform linear hypergraph with $n$ edges has a proper vertex-coloring using $n$ colors such that each edge has one vertex of each color. 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--Lov\'asz 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.
Joint work with Oliver Janzer (ETH Zurich)
Zoom link: https://zoom.us/j/94732664165