Count(q) versus the Pigeon-Hole Principle

Søren Riis

August 1994


For each tex2html_wrap_inline31 there exist a model tex2html_wrap_inline33 of tex2html_wrap_inline35 which satisfies the Count(p) principle. Furthermore if p contain all prime factors of q there exist tex2html_wrap_inline43 and a bijective map tex2html_wrap_inline45 mapping tex2html_wrap_inline47 onto tex2html_wrap_inline49.

A corollary is a complete classification of the Count(q) versus Count(p) problem. Another corollary solves an open question by M. Ajtai.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.