The Combinatorial Nullstellensatz applied to the Erdős-Faber-Lovász conjecture and other applications in graph theory

Description of video

Date: 3/3/22
Speaker :Nagy Zoltán Lóránt


    In the first part of the talk I present some applications of the Combinatorial Nullstellensatz (CN) in graph theory, and  a variant of CN, called the Quantitative Nullstellensatz.
    In the second part I discuss the application of CN to the Erdős-Faber-Lovász conjecture, which has been confirmed recently by Kang, Kelly, Kühn, Methuku, and Osthus for large enough values of n. The long-standing Erdős-Faber-Lovász 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 Erdős-Faber-Lovász 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 (but still leave the conjecture open).
    Joint work with Oliver Janzer (ETH Zurich).