Definable $(ω, 2)$-theorem for families with VC-codensity less than $2$
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910920785002496 |
|---|---|
| author | Guerrero, Pablo Andújar |
| author_facet | Guerrero, Pablo Andújar |
| contents | Let $\mathcal{S}$ be a family of sets with VC-codensity less than $2$. We prove that, if $\mathcal{S}$ has the $(ω, 2)$-property (for any infinitely many sets in $\mathcal{S}$, at least $2$ among them intersect), then $\mathcal{S}$ can be partitioned into finitely many subfamilies, each with the finite intersection property. If $\mathcal{S}$ is definable in some first-order structure, then these subfamilies can be chosen definable too. This is a strengthening of the case $q=2$ of the definable $(p,q)$- conjecture in model theory and of the Alon-Kleitman-Matoušek $(p,q)$-theorem in combinatorics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_13665 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Definable $(ω, 2)$-theorem for families with VC-codensity less than $2$ Guerrero, Pablo Andújar Logic Combinatorics 03C45, 52A35 Let $\mathcal{S}$ be a family of sets with VC-codensity less than $2$. We prove that, if $\mathcal{S}$ has the $(ω, 2)$-property (for any infinitely many sets in $\mathcal{S}$, at least $2$ among them intersect), then $\mathcal{S}$ can be partitioned into finitely many subfamilies, each with the finite intersection property. If $\mathcal{S}$ is definable in some first-order structure, then these subfamilies can be chosen definable too. This is a strengthening of the case $q=2$ of the definable $(p,q)$- conjecture in model theory and of the Alon-Kleitman-Matoušek $(p,q)$-theorem in combinatorics. |
| title | Definable $(ω, 2)$-theorem for families with VC-codensity less than $2$ |
| topic | Logic Combinatorics 03C45, 52A35 |
| url | https://arxiv.org/abs/2205.13665 |