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

MaRDI QIDQ612968zbMATH OpenFDO

Authors Uwe Schauz

Publication date 16 December 2010

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

Full work available at URL https://arxiv.org/abs/1212.5694, https://eudml.org/doc/233561, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r176.html

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

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)

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.

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

Cited in

(22)

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

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)