Combinatorial nullstellensatz modulo prime powers and the parity argument

MaRDI QIDQ490257zbMATH OpenFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 22 January 2015

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

Full work available at URL https://arxiv.org/abs/1402.4422, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p44

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 nullstellensatzalgebraic combinatoricspolynomial argument

Mathematics Subject Classification ID

Other combinatorial number theory (11B75)

Abstract: We present new generalizations of Olson's theorem and of a consequence of Alon's Combinatorial Nullstellensatz. These enable us to extend some of their combinatorial applications with conditions modulo primes to conditions modulo prime powers. We analyze computational search problems corresponding to these kinds of combinatorial questions and we prove that the problem of finding degree-constrained subgraphs modulo $2^d$ such as $2^d$-divisible subgraphs and the search problem corresponding to the Combinatorial Nullstellensatz over $mathbb{F}_2$ belong to the complexity class Polynomial Parity Argument (PPA).

Recommendations

• Combinatorial congruences modulo prime powers
• A generalization of combinatorial Nullstellensatz
• The Combinatorial Nullstellensätze revisited
• On the polynomial parity argument complexity of the combinatorial Nullstellensatz
• A combinatorial proof of the effective Nullstellensatz
• Combinational properties of sets of residues modulo a prime and the Erdős-Graham problem
• A short proof of combinatorial Nullstellensatz
• A duality based proof of the combinatorial nullstellensatz
• Combinatorial Nullstellensatz
• A generalization of Alon's combinatorial nullstellensatz

Cites work

• scientific article; zbMATH DE number 1962903 (Why is no real title available?)
• A combinatorial problem on finite Abelian groups. I
• A note on degree-constrained subgraphs
• A note on polynomials and \(f\)-factors of graphs
• Chevalley's theorem with restricted variables
• Combinatorial Nullstellensatz
• Integer-valued polynomials
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Regular subgraphs of almost regular graphs

Cited in

(4)

• On the polynomial parity argument complexity of the combinatorial Nullstellensatz
• Varga's theorem in number fields
• The complexity of the parity argument with potential
• TFNP: an update

This page was built for publication: Combinatorial nullstellensatz modulo prime powers and the parity argument

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