Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
Coloring of graphs and hypergraphs (05C15) Algebraic combinatorics (05E99) Congruences in many variables (11D79) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Determinants, permanents, traces, other special matrix functions (15A15) Interpolation in approximation theory (41A05)
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.
- Warning's second theorem with relaxed outputs
- Warning's second theorem with restricted variables
- Computing the list chromatic index of graphs
- Constant terms of near-Dyson polynomials
- Combinatorial Nullstellensatz and DP-coloring of graphs
- A generalized combinatorial nullstellensatz for multisets
- Classification of polynomial mappings between commutative groups.
- Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the combinatorial nullstellensatz
- Chevalley-Warning type results on abelian groups
- Asymptotics of traces of paths in the Young and Schur graphs
- On a theorem of Morlaye and Joly and its generalization
- An improvement to Chevalley's theorem with restricted variables
- Some new characterizations of graph colorability and of blocking sets of projective spaces
- The Combinatorial Nullstellensätze revisited
- On zeros of a polynomial in a finite grid
- Total weight choosability for Halin graphs
- Constructing integer-magic graphs via the combinatorial Nullstellensatz
- scientific article; zbMATH DE number 7633017 (Why is no real title available?)
- On the Alon-Füredi bound
- List-coloring claw-free graphs with -1 colors
- A generalization of Schauz and Brink's restricted-variable version of Chevalley's theorem
- Two Chromatic Conjectures: One for Vertices and One for Edges
- Polynomials over structured grids
- Covering almost all the layers of the hypercube with multiplicities
- Transformation invariance in the combinatorial Nullstellensatz and nowhere-zero points of non-singular matrices
- The Alon-Tarsi number of two kinds of planar graphs
- The Alon-Tarsi number of a toroidal grid
- scientific article; zbMATH DE number 7790331 (Why is no real title available?)
- On the Alon-Tarsi number of semi-strong product of graphs
- Zero testing and equation solving for sparse polynomials on rectangular domains
- Additive combinatorics using equivariant cohomology
- Brooks' theorem via the Alon-Tarsi theorem
- Structured and punctured Nullstellensätze
- Proof of the list edge coloring conjecture for complete graphs of prime degree
This page was built for publication: Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010715)
