Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.17149 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913669593432064 |
|---|---|
| author | Pohoata, Cosmin Yang, Kevin Zhang, Shengtong |
| author_facet | Pohoata, Cosmin Yang, Kevin Zhang, Shengtong |
| contents | We establish a theorem regarding the maximum size of an {\it{induced}} matching in the bipartite complement of the incidence graph of a set system $(X,\mathcal{F})$. We show that this quantity plus one provides an upper bound on the colorful Helly number of this set system, i.e. the minimum positive integer $N$ for which the following statement holds: if finite subfamilies $\mathcal{F}_1,\ldots, \mathcal{F}_{N} \subset \mathcal{F}$ are such that $\cap_{F \in \mathcal{F}_{i}} F = 0$ for every $i=1,\ldots,N$, then there exists $F_i \in \mathcal{F}_i$ such that $F_1 \cap \ldots \cap F_{N} = \emptyset$. We will also discuss some natural refinements of this result and applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_17149 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Colorful Helly via induced matchings Pohoata, Cosmin Yang, Kevin Zhang, Shengtong Combinatorics We establish a theorem regarding the maximum size of an {\it{induced}} matching in the bipartite complement of the incidence graph of a set system $(X,\mathcal{F})$. We show that this quantity plus one provides an upper bound on the colorful Helly number of this set system, i.e. the minimum positive integer $N$ for which the following statement holds: if finite subfamilies $\mathcal{F}_1,\ldots, \mathcal{F}_{N} \subset \mathcal{F}$ are such that $\cap_{F \in \mathcal{F}_{i}} F = 0$ for every $i=1,\ldots,N$, then there exists $F_i \in \mathcal{F}_i$ such that $F_1 \cap \ldots \cap F_{N} = \emptyset$. We will also discuss some natural refinements of this result and applications. |
| title | Colorful Helly via induced matchings |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.17149 |