Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
type: Item
instance of: scholarly article
title: Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
zbMATH Open document ID: 1172.13016
author: Uwe Schauz
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/130684
full work available at URL: v15i1r10.html
review text: Summary: The main result of this paper is a coefficient formula that sharpens and generalizes Alon and Tarsi's Combinatorial Nullstellensatz. On its own, it is a result about polynomials, providing some information about the polynomial map \(P|_{\mathfrak X_1,\times \dots \times \mathfrak X_n}\) when only incomplete information about the polynomial \(P(X_1,\dots,X_n)\) is given. In a very general working frame, the grid points \(x\in\mathfrak X_{1} \times \dots \times \mathfrak X_n\) which do not vanish under an algebraic solution -- a certain describing polynomial \(P(X_1,\dots,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 \({\mathcal S}\), which may be called the set of solutions; and a subset \({\mathcal S}_{\text{triv}}\subseteq{\mathcal S}\), the 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.
Mathematics Subject Classification ID: 13P10
Mathematics Subject Classification ID: 05E99
Mathematics Subject Classification ID: 11D79
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 41A05
zbMATH DE Number: 5540915
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540915