A paintability version of the combinatorial Nullstellensatz, and list colorings of k-partite k-uniform hypergraphs

zbMATH Open1201.05039arXiv1212.5694MaRDI QIDQ612968FDOQ612968

Authors: Uwe Schauz 

Publication date: 16 December 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: The main result of this paper is a coefficient formula that sharpens and generalizes Alon and Tarsi's Combinatorial Nullstellensatz, which provides some information about the polynomial map $P{|}_{X_{1}imes\mathrm{...}imes{X}_n}$ when only incomplete information about the polynomial $P(X_1,\mathrm{...}c,X_n)$ is given. In a very general working frame, the grid points $xin{X}_{1}imes\mathrm{...}bimes{X}_n$ which do not vanish under an algebraic solution -- a certain describing polynomial $P(X_1,\mathrm{...}c,X_n)$ -- correspond to the explicit solutions of a problem. As a consequence of the coefficient formula, we prove that the existence of an algebraic solution is equivalent to the existence of a nontrivial solution to a problem. By a problem, we mean everything that "owns" both, a set $S$, which may be called the emph{set of solutions}; and a subset $StsubseteqS$, the emph{set of trivial solutions}. We give several examples of how to find algebraic solutions, and how to apply our coefficient formula. These examples are mainly from graph theory and combinatorial number theory, but we also prove several versions of Chevalley and Warning's Theorem, including a generalization of Olson's Theorem, as examples and useful corollaries. We obtain a permanent formula by applying our coefficient formula to the matrix polynomial, which is a generalization of the graph polynomial. This formula is an integrative generalization and sharpening of: 1. Ryser's permanent formula. 2. Alon's Permanent Lemma. 3. Alon and Tarsi's Theorem about orientations and colorings of graphs. Furthermore, in combination with the Vigneron-Ellingham-Goddyn property of planar (n)regular graphs, the formula contains as very special cases: 4. Scheim's formula for the number of edge (n)-colorings of such graphs. 5. Ellingham and Goddyn's partial answer to the list coloring conjecture.

Full work available at URL: https://arxiv.org/abs/1212.5694

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The list-chromatic number of complete multipartite hypergraphs and multiple covers by independent sets
• Combinatorial Nullstellensatz and DP-coloring of graphs
• Colorings versus list colorings of uniform hypergraphs
• Near-optimal list colorings
• scientific article; zbMATH DE number 2204176

zbMATH Keywords

combinatorial nullstellensatzlist coloring number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Polynomials in number theory (11C08) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Games involving graphs (91A43)

Cited In (22)

• Locally planar graphs are 2-defective 4-paintable
• Application of polynomial method to on-line list colouring of graphs
• The Alon-Tarsi number of planar graphs
• Network Capacity Bound for Personalized PageRank in Multimodal Networks
• On-line list coloring of matroids
• Combinatorial Nullstellensatz and DP-coloring of graphs
• Painting squares in \(\Delta^2-1\) shades
• Towards an on-line version of Ohba's conjecture
• The Alon-Tarsi number of two kinds of planar graphs
• Critically paintable, choosable or colorable graphs
• Constructing integer-magic graphs via the combinatorial Nullstellensatz
• Chip games and paintability
• Locally planar graphs are 5-paintable
• On two generalizations of the Alon-Tarsi polynomial method
• The tournament scheduling problem with absences
• Schnyder woods and Alon-Tarsi number of planar graphs
• Proof of the list edge coloring conjecture for complete graphs of prime degree
• Partial online list coloring of graphs
• Computing the list chromatic index of graphs
• The list-chromatic index of \(K_6\)
• Transformation invariance in the combinatorial Nullstellensatz and nowhere-zero points of non-singular matrices
• Brooks' Theorem and Beyond

This page was built for publication: A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q612968)