Geodesic
Combinatorial nullstellensatz modulo prime powers and the parity argument
László Varga1
1Eötvös Loránd University, Institute of Mathematics, Budapest
The electronic journal of combinatorics, Tome 21 (2014) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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).
DOI : 10.37236/4124
Classification : 11B75
Mots-clés : algebraic combinatorics, combinatorial nullstellensatz, polynomial argument

László Varga  1

1 Eötvös Loránd University, Institute of Mathematics, Budapest 
@article{10_37236_4124,
     author = {L\'aszl\'o Varga},
     title = {Combinatorial nullstellensatz modulo prime powers and the parity argument},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {4},
     doi = {10.37236/4124},
     zbl = {1403.11020},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4124/}
}
TY  - JOUR
AU  - László Varga
TI  - Combinatorial nullstellensatz modulo prime powers and the parity argument
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4124/
DO  - 10.37236/4124
ID  - 10_37236_4124
ER  - 
%0 Journal Article
%A László Varga
%T Combinatorial nullstellensatz modulo prime powers and the parity argument
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4124/
%R 10.37236/4124
%F 10_37236_4124
László Varga. Combinatorial nullstellensatz modulo prime powers and the parity argument. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/4124

Cité par Sources :