Coloring linear hypergraphs: the Erdős–Faber–Lovász conjecture and the Combinatorial Nullstellensatz
| Autor: | Oliver Janzer, Zoltán Lóránt Nagy |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Graph orientations
Mathematics::Combinatorics Conjecture Computer Science::Information Retrieval Applied Mathematics Coloring Hypergraphs Erdos-Faber-Lovasz Combinatorial Nullstellensatz Computer Science Applications Combinatorics Computer Science::Discrete Mathematics Erdős–Faber–Lovász conjecture ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Mathematics - Combinatorics Algebraic number Mathematics |
| Zdroj: | Designs, Codes and Cryptography, 90 (9) |
| ISSN: | 0925-1022 1573-7586 |
| DOI: | 10.3929/ethz-b-000495133 |
| Popis: | 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. Designs, Codes and Cryptography, 90 (9) ISSN:0925-1022 ISSN:1573-7586 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink