Approximate Euler characteristic, dimension, and weak pigeonhole principles

DOI10.2178/jsl/1080938837zbMath1068.03024OpenAlexW2038773716MaRDI QIDQ5311719

Jan Krajíček

Publication date: 29 August 2005

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1080938837

zbMATH Keywords

dimension functionweak pigeonhole principledefinable setsfirst-order structureapproximate Euler characteristic

Mathematics Subject Classification ID

Complexity of proofs (03F20) Basic properties of first-order languages and structures (03C07)

Related Items (2)

Approximate counting by hashing in bounded arithmetic ⋮ MULTIDIMENSIONAL EXACT CLASSES, SMOOTH APPROXIMATION AND BOUNDED 4-TYPES

Cites Work

• Exponential lower bounds for the pigeonhole principle
• The elementary theory of finite fields
• Uniform Families of Polynomial Equations Over a Finite Field and Structures Admitting an Euler Characteristic of Definable Sets
• Provability of the pigeonhole principle and the existence of infinitely many primes
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle

This page was built for publication: Approximate Euler characteristic, dimension, and weak pigeonhole principles