Combinatorial nullstellensatz modulo prime powers and the parity argument

zbMATH Open1403.11020arXiv1402.4422MaRDI QIDQ490257FDOQ490257

Authors: Yong-Cai Geng, Sumit K. Garg 

Publication date: 22 January 2015

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

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).

Full work available at URL: https://arxiv.org/abs/1402.4422

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

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

zbMATH Keywords

combinatorial nullstellensatzalgebraic combinatoricspolynomial argument

Mathematics Subject Classification ID

Other combinatorial number theory (11B75)

Cites Work

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

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)