Finite combinatorics and computability theory
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918456983552000 |
|---|---|
| author | Dzhafarov, Damir D. Goh, Jun le |
| author_facet | Dzhafarov, Damir D. Goh, Jun le |
| contents | We prove that the existence of finite combinatorial objects such as affine planes, mutually orthogonal Latin squares, and resolvable balanced incomplete block designs can be reformulated as the existence of certain algorithmic reductions between problems related to the pigeonhole principle. We then study the latter using counting arguments and computability theory. In particular, we demonstrate that computability theoretic techniques can be used to refine and prove new results in finite combinatorics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_18290 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Finite combinatorics and computability theory Dzhafarov, Damir D. Goh, Jun le Combinatorics Logic We prove that the existence of finite combinatorial objects such as affine planes, mutually orthogonal Latin squares, and resolvable balanced incomplete block designs can be reformulated as the existence of certain algorithmic reductions between problems related to the pigeonhole principle. We then study the latter using counting arguments and computability theory. In particular, we demonstrate that computability theoretic techniques can be used to refine and prove new results in finite combinatorics. |
| title | Finite combinatorics and computability theory |
| topic | Combinatorics Logic |
| url | https://arxiv.org/abs/2604.18290 |