Combinatorial Nullstellensatz

DOI10.1017/S0963548398003411zbMath0920.05026WikidataQ64117603 ScholiaQ64117603MaRDI QIDQ4243069

Noga Alon

Publication date: 10 September 1999

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

polynomial ringgraph colouringregular graphgraph bandwidthHilbert's Nullstellensatzideal of polynomialsresidue class

Mathematics Subject Classification ID

Polynomial rings and ideals; rings of integer-valued polynomials (13F20) Other combinatorial number theory (11B75) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Polynomials over commutative rings (13B25) Coloring of graphs and hypergraphs (05C15)

Related Items

Pair dominating graphs, Graphs are \((1, \varDelta + 1)\)-choosable, Neighbor sum distinguishing total choosability of planar graphs without 4-cycles, Neighbor distinguishing total choice number of sparse graphs via the combinatorial nullstellensatz, Graph polynomials and paintability of plane graphs, Neighbor sum distinguishing total chromatic number of 2-degenerate graphs, Total weight choosability of cone graphs, Warning's second theorem with relaxed outputs, Polynomial approach to explicit formulae for generalized binomial coefficients, A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles, Coloring, sparseness and girth, Lower bounds for monotone counting circuits, Weighted antimagic labeling: an algorithmic approach, Neighbor sum distinguishing total choosability of planar graphs, Finite phylogenetic complexity of \(\mathbb{Z}_p\) and invariants for \(\mathbb{Z}_3\), Book review of: L. Guth, Polynomial methods in combinatorics, Zero-sum problems in finite Abelian groups: a survey, On the strong chromatic index of sparse graphs, Graphs with maximum average degree less than \(\frac{11}{4}\) are \((1, 3)\)-choosable, A non-commutative cryptosystem based on quaternion algebras, Zero-sum flows in regular graphs, Alon's nullstellensatz for multisets, Essential positive covers of the cube, Neighbor sum distinguishing total coloring of planar graphs without 4-cycles, Neighbor-sum-distinguishing edge choosability of subcubic graphs, Enumeration of non-crossing pairings on bit strings, List neighbor sum distinguishing edge coloring of subcubic graphs, On restricted sumsets over a field, Algebraic methods for parameterized codes and invariants of vanishing ideals over finite fields, Zero-sum problems and coverings by proper cosets, Punctured combinatorial Nullstellensätze, On the modular sumset partition problem, On weighted zero-sum sequences, On the neighbor sum distinguishing total coloring of planar graphs, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, Partial matrices all of whose completions have the same spectrum, On the neighbour sum distinguishing index of graphs with bounded maximum average degree, On the existence of zero-sum subsequences of distinct lengths, The adjacent vertex distinguishing total choosability of planar graphs with maximum degree at least eleven, On Snevily's conjecture and restricted sumsets., Representation theorems for partially exchangeable random variables, Zero sum partition of abelian groups into sets of the same order and its applications, Neighbor sum distinguishing total coloring and list neighbor sum distinguishing total coloring, The minimum distance of parameterized codes on projective tori, Approximation by multivariate higher degree \(F\)-transform based on B-splines, Weighted-1-antimagic graphs of prime power order, Warning's second theorem with restricted variables, Neighbor sum distinguishing total coloring of sparse IC-planar graphs, Value sets of polynomials and the Cauchy-Davenport theorem., Total weight choosability of Cartesian product of graphs, Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz, On two generalizations of the Alon-Tarsi polynomial method, The Combinatorial Nullstellensätze revisited, Chevalley's theorem with restricted variables, Linear extension of the Erdős-Heilbronn conjecture, The \(1,2,3\)-conjecture and \(1,2\)-conjecture for sparse graphs, Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz, Combinatorial nullstellensatz modulo prime powers and the parity argument, On the cylinder conjecture, Read-once polynomial identity testing, A Bertini-type theorem for free arithmetic linear series, Adjacent vertex distinguishing colorings by sum of sparse graphs, Neighbor sum distinguishing total choosability of planar graphs without adjacent triangles, On a permutation problem for finite abelian groups, Permanent index of matrices associated with graphs, The adjacent vertex distinguishing total coloring of planar graphs without adjacent 4-cycles, Total weight choosability of Mycielski graphs, Neighbor sum distinguishing colorings of graphs with maximum average degree less than \(\frac{37} {12}\), On-line list coloring of matroids, On weight choosabilities of graphs with bounded maximum average degree, Every graph is \((2,3)\)-choosable, Neighbor sum distinguishing edge coloring of subcubic graphs, On the subset sum problem over finite fields, Approximate results for rainbow labelings, Exterior algebras and two conjectures on finite Abelian groups., Every tree is a large subtree of a tree that decomposes \(K_n\) or \(K_{n,n}\), Addition of sets via symmetric polynomials - a polynomial method, Algebraic points of small height missing a union of varieties, Permutations, hyperplanes and polynomials over finite fields, Brooks' theorem via the Alon-Tarsi theorem, Lucky labelings of graphs, Neighbor sum distinguishing total coloring of graphs with bounded treewidth, Building above read-once polynomials: identity testing and hardness of representation, A new class of antimagic Cartesian product graphs, A variant of Tao's method with application to restricted sumsets, The primes contain arbitrarily long polynomial progressions, Remarks on some zero-sum theorems, Permutations over cyclic groups, Additive coloring of planar graphs, The complexity of approximating conservative counting CSPs, Proof of the list edge coloring conjecture for complete graphs of prime degree, Restricted set addition: the exceptional case of the Erdős-Heilbronn conjecture, Additive Latin transversals., The permanent rank of a matrix, On a conjecture of Graham and Häggkvist with the polynomial method, The hat guessing number of graphs, A new extension of the Erdős-Heilbronn conjecture, Spectral aspects of symmetric matrix signings, Optimal strong parity edge-coloring of complete graphs, Adjacent vertex distinguishing total coloring of planar graphs with maximum degree 8, Nearly holomorphic automorphic forms on \(\mathrm{SP}_{2n}\) with sufficiently regular infinitesimal characters and applications, Graph polynomials and group coloring of graphs, Additive Latin transversals and group rings., The Erdős-Heilbronn problem in Abelian groups., On a list variant of the multiplicative 1-2-3 conjecture, Covering symmetric sets of the Boolean cube by affine hyperplanes, Affine representability and decision procedures for commutativity theorems for rings and algebras, Going wide with the 1-2-3 conjecture, Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the combinatorial nullstellensatz, On sequences in cyclic groups with distinct partial sums, Every nice graph is (1,5)-choosable, List strong edge-coloring of graphs with maximum degree 4, Local antimagic orientation of graphs, Additive list coloring of planar graphs with given girth, Neighbor sum distinguishing total choosability of planar graphs without adjacent special 5-cycles, Neighbor sum distinguishing total coloring of IC-planar graphs with short cycle restrictions, Improved bounds for neighbor sum (set) distinguishing choosability of planar graphs, Parity and strong parity edge-colorings of graphs, Some criteria for a signed graph to have full rank, Neighbor sum distinguishing total coloring of IC-planar graphs, Partitions of nonzero elements of a finite field into pairs, The list edge coloring and list total coloring of planar graphs with maximum degree at least 7, Neighbor sum distinguishing index of sparse graphs, Weight choosability of graphs with maximum degree 4, Tropical combinatorial Nullstellensatz and sparse polynomials, Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing, The Alon-Tarsi number of a planar graph minus a matching, System of unbiased representatives for a collection of bicolorings, Some new results about a conjecture by Brian Alspach, On the lucky choice number of graphs, Understanding PPA-completeness, Neighbor sum distinguishing chromatic index of sparse graphs via the combinatorial Nullstellensatz, On total weight choosability of graphs, Computing the list chromatic index of graphs, Chevalley-Warning type results on abelian groups, Neighbor sum distinguishing total choosability of 1-planar graphs with maximum degree at least 24, On almost \(k\)-covers of hypercubes, The unit theorem for finite-dimensional algebras, Caterpillars are antimagic, From the 1-2-3 conjecture to the Riemann hypothesis, 2-connected chordal graphs and line graphs are \((1,5)\)-choosable, Local antimagic orientations of \(d\)-degenerate graphs, Solving a fixed number of equations over finite groups, Neighbor sum distinguishing total choosability of cubic graphs, Counting and enumerating feasible rotating schedules by means of Gröbner bases, Matrix choosability, Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10, Neighbor sum distinguishing list total coloring of subcubic graphs, New bounds on the field size for maximally recoverable codes instantiating grid-like topologies, Neighbor sum distinguishing total coloring of triangle free IC-planar graphs, Squarefree polynomials with prescribed coefficients, Constant terms of near-Dyson polynomials, Weighted antimagic labeling, Neighbor sum distinguishing total choice number of planar graphs without 6-cycles, Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory, On the complexity of Hilbert refutations for partition, An addition theorem and maximal zero-sum free sets in \(\mathbb{Z}/p\mathbb{Z}\), Combinatorial Nullstellensatz and DP-coloring of graphs, An algebraic perspective on integer sparse recovery, Antimagic labelings of caterpillars, A generalized combinatorial nullstellensatz for multisets, Neighbor sum distinguishing index of subcubic graphs, On a Lovász-type lemma, applied to Brooks' theorem for list-colouring, List edge coloring of outer-1-planar graphs, A characterization for the neighbor-distinguishing total chromatic number of planar graphs with \(\varDelta = 13\), On proper edge 3-colorings of a cubic graph, On irreduceability of Boolean functions with respect to commutative associative operation, Neighbor sum distinguishing total choosability of IC-planar graphs, Total weight choosability of graphs: towards the 1-2-3-conjecture, The multidimensional truncated moment problem: Carathéodory numbers from Hilbert functions, Edge-face list coloring of Halin graphs, The list \(L(2,1)\)-labeling of planar graphs with large girth, Neighbor product distinguishing total colorings of 2-degenerate graphs, Neighbor-distinguishing total coloring of planar graphs with maximum degree twelve, Neighbor sum distinguishing total colorings of IC-planar graphs with maximum degree 13, On the total neighbour sum distinguishing index of graphs with bounded maximum average degree, Strong list-chromatic index of subcubic graphs, Neighbor product distinguishing total colorings of planar graphs with maximum degree at least ten, List injective edge-coloring of subcubic graphs, A Snevily-type inequality for multisets, A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density, On permutations of \(\{1,\ldots ,n\}\) and related topics, Planar graphs with girth 20 are additively 3-choosable, Asymptotics of traces of paths in the Young and Schur graphs, Operator scaling: theory and applications, On a theorem of Morlaye and Joly and its generalization, Univariate ideal membership parameterized by rank, degree, and number of generators, The Alon-Tarsi number of \(K_5\)-minor-free graphs, Alon-Tarsi numbers of direct products, Optimal frequency assignment and planar list \(L(2, 1)\)-labeling, The complexity of finding fair independent sets in cycles, On the generalized restricted sumsets in abelian groups, Uniform bounds for the number of rational points on varieties over global fields, Variations on the Erdős distinct-sums problem, A lower bound for \(|\{a+b: a\in A,\;b\in B,\;P(a,b)\neq 0\}|\), On 2-coloring certain \(k\)-uniform hypergraphs, Note on a zero net-regular signed graph, On zeros of multilinear polynomials, A refinement of Christol's theorem for algebraic power series, Sums of subsets with polynomial restrictions., An algorithm for identifying cycle-plus-triangles graphs, Neighbor sum distinguishing total choice number of NIC-planar graphs with restricted conditions, Maximal rank in matrix spaces via graph matchings, The Weighted Davenport Constant of a group and a related extremal problem, Between Proper and Strong Edge-Colorings of Subcubic Graphs, Constructing integer-magic graphs via the Combinatorial Nullstellensatz, Antimagic labelling of vertex weighted graphs, A note on the neighbor sum distinguishing total coloring of planar graphs, Adjacent vertex distinguishing total coloring of graphs with maximum degree 4, Neighbor sum (set) distinguishing total choosability of \(d\)-degenerate graphs, On an effective variation of Kronecker’s approximation theorem avoiding algebraic sets, k-Sums in Abelian Groups, Three Combinatorial Perspectives on Minimal Codes, Asymptotically optimal neighbour sum distinguishing colourings of graphs, An inverse theorem for the restricted set addition in Abelian groups., Restricted set addition in abelian groups: results and conjectures, Neighbor Distinguishing Edge Colorings Via the Combinatorial Nullstellensatz Revisited, A simple proof of the Zeilberger–Bressoud 𝑞-Dyson theorem, Combinatorial Nullstellensatz approach to polynomial expansion, The Multivariate Schwartz--Zippel Lemma, Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles, Derandomization from Algebraic Hardness, Total weight choosability of graphs with bounded maximum average degree, Minimal Symmetric Differences of Lines in Projective Planes, Neighbor sum distinguishing total coloring of planar graphs without 5-cycles, On generalized neighbor sum distinguishing index of planar graphs, Neighbor sum distinguishing total chromatic number of \(K_4\)-minor free graph, A New Proof of Warning's Second Theorem, On the limits of depth reduction at depth 3 over small finite fields, Neighbor sum (set) distinguishing total choosability via the combinatorial Nullstellensatz, Neighbor sum distinguishing total coloring of 2-degenerate graphs, Chevalley-Warning at the boundary, The adjacent vertex distinguishing total chromatic numbers of planar graphs with \(\Delta=10\), The polynomial method in the study of zero-sum theorems, The neighbour sum distinguishing relaxed edge colouring, Constant term identities and Poincaré polynomials, Graphs admitting antimagic labeling for arbitrary sets of positive integers, Zero-sum subsets in vector spaces over finite fields, Vanishing ideals of parameterized subgroups in a toric variety, Lifted projective Reed-Solomon codes, On a Häggkvist's Conjecture with the Polynomial Method, List-distinguishing Cartesian products of cliques, Affine Cartesian codes with complementary duals, On product decomposition, Local antimagic labeling of graphs, Planar graphs with \(\Delta =9\) are neighbor-distinguishing totally 12-colorable, Adjacent vertex distinguishing total choosability of planar graphs with maximum degree at least 10, 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz, On value sets of polynomials over a field, A note on degree-constrained subgraphs, 3-facial edge-coloring of plane graphs, \(\rho\)-valuations for some stunted trees, The list-chromatic index of \(K_6\), On two questions about circular choosability, On some batch code properties of the simplex code, Affine Cartesian codes, 2-Synchronizing Words, Equal entries in totally positive matrices, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, A polynomial method approach to zero-sum subsets in $\mathbb {F}_{p}^{2}$, Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz, Algebraic Properties of ModuloqComplete ℓ-Wide Families, Sumsets as unions of sumsets of subsets, Schwartz-Zippel bounds for two-dimensional products, On multivariate polynomials with many roots over a finite grid, Some Combinatorial Applications of Gröbner Bases, Restricted sumsets and a conjecture of Lev, Parity, Eulerian subgraphs and the Tutte polynomial, Unification of zero-sum problems, subset sums and covers of ℤ, Unnamed Item, Unnamed Item, On the exterior algebra method applied to restricted set addition, Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs, Total weight choosability for Halin graphs, Combinatorial anti-concentration inequalities, with applications, Weakening the conditions in some classical theorems on linear preserver problems, Restricted sumsets in ℤn, On systems of diagonal forms II, On the Neighbor Sum Distinguishing Index of Planar Graphs, The 1-2-3-Conjecture for Hypergraphs, General Parity Result and Cycle‐Plus‐Triangles Graphs, Characterizing Arithmetic Read-Once Formulae, Vanishing ideals over finite fields, A Partial Solution to Cordial Tree Conjecture, 2-colorability of \(r\)-uniform hypergraphs, THE NUMBER OF ROOTS OF A POLYNOMIAL SYSTEM, Unnamed Item, The Degree and Regularity of Vanishing Ideals of Algebraic Toric Sets Over Finite Fields, On various restricted sumsets, On the Sumset Partition Problem, Neighbor sum distinguishing total chromatic number of planar graphs, Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs, A compactness argument in the additive theory and the polynomial method., A nullstellensatz for sequences over \(\mathbb{F}_p\), A new approach to constant term identities and Selberg-type integrals, Enumeration and classification of self-orthogonal partial Latin rectangles by using the polynomial method, The polynomial method for list-colouring extendability of outerplanar graphs, Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry, List-antimagic labeling of vertex-weighted graphs, Neighbor sum distinguishing total colorings of triangle free planar graphs, Polynomials over structured grids, Improper Choosability and Property B, Total Weight Choosability of Trees, List-Coloring Claw-Free Graphs with $\Delta-1$ Colors, Covering almost all the layers of the hypercube with multiplicities, Between proper and strong edge‐colorings of subcubic graphs, Proof-carrying data from arithmetized random oracles, Maximal generalized rank in graphical matrix spaces, Distance matrices of a tree: two more invariants, and in a unified framework, Combinatorial Nullstellensatz over division rings, The structure of symmetric tensor powers of composition algebras, Transformation invariance in the combinatorial Nullstellensatz and nowhere-zero points of non-singular matrices, Neighbour sum distinguishing edge-weightings with local constraints, An algebraic formulation of hypergraph colorings, Multilinear algebra for minimum storage regenerating codes: a generalization of the product-matrix construction, Neighbor Sum Distinguishing Total Chromatic Number of Graphs with Lower Average Degree, On finding constrained independent sets in cycles, 5-list coloring toroidal 6-regular triangulations in linear time, Polynomials that vanish to high order on most of the hypercube, Exploring implications of trace (inversion) formula and Artin algebras in extremal combinatorics, Adjacent vertex distinguishing edge choosability of 1-planar graphs with maximum degree at least 23, The Alon-Tarsi number of two kinds of planar graphs, Espaces adéliques quadratiques, The Alon-Tarsi number of a toroidal grid, Neighbor sum distinguishing total choosability of planar graphs with maximum degree at least 10, On strong edge-coloring of graphs with maximum degree 5, On the Alon-Tarsi number of semi-strong product of graphs, Weak sequenceability in cyclic groups, Zero testing and equation solving for sparse polynomials on rectangular domains, A solution to the 1-2-3 conjecture, Covering grids with multiplicity, Unnamed Item, Decomposing almost complete graphs by random trees, Total weight choosability of graphs, Decomposing almost complete graphs by random trees, A NOTE ON EDGE WEIGHT CHOOSABILITY OF GRAPHS, Almost Every Tree With m Edges Decomposes K_2m,2m, Depth-4 Identity Testing and Noether’s Normalization Lemma, A Polyhedral Characterization of Border Bases, Transversals of additive Latin squares, Neighbour sum distinguishing total colourings via the combinatorial nullstellensatz, Weight choosability of oriented hypergraphs, Unnamed Item, A Large Gap in a Dilate of a Set, Codes for Distributed Storage, 3-Regular subgraphs and (3,1)-colorings of 4-regular pseudographs, Membership in Moment Polytopes is in NP and coNP