Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.15362 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913997218906112 |
|---|---|
| author | Quintero, Guillermo Gamboa Kantor, Ida |
| author_facet | Quintero, Guillermo Gamboa Kantor, Ida |
| contents | A $3$-partition of an $n$-element set $V$ is a triple of pairwise disjoint nonempty subsets $X,Y,Z$ such that $V=X\cup Y\cup Z$. We determine the minimum size $φ_3(n)$ of a set $\mathcal{E}$ of triples such that for every 3-partition $X,Y,Z$ of the set $\{1,\dots,n\}$, there is some $\{x,y,z\}\in \mathcal{E}$ with $x\in X$, $y\in Y$, and $z\in Z$. In particular, $$φ_3(n)=\left\lceil{\frac{n(n-2)}{3}}\right\rceil.$$ For $d>3$, one may define an analogous number $φ_d(n)$. We determine the order of magnitude of $φ_d(n)$, and prove the following upper and lower bounds, for $d>3$: $$\frac{2 n^{d-1}}{d!} -o(n^{d-1}) \leq φ_d(n) \leq \frac{0.86}{(d-1)!}n^{d-1}+o(n^{d-1}).$$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_15362 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimum blocking sets for families of partitions Quintero, Guillermo Gamboa Kantor, Ida Combinatorics Discrete Mathematics 05D15 A $3$-partition of an $n$-element set $V$ is a triple of pairwise disjoint nonempty subsets $X,Y,Z$ such that $V=X\cup Y\cup Z$. We determine the minimum size $φ_3(n)$ of a set $\mathcal{E}$ of triples such that for every 3-partition $X,Y,Z$ of the set $\{1,\dots,n\}$, there is some $\{x,y,z\}\in \mathcal{E}$ with $x\in X$, $y\in Y$, and $z\in Z$. In particular, $$φ_3(n)=\left\lceil{\frac{n(n-2)}{3}}\right\rceil.$$ For $d>3$, one may define an analogous number $φ_d(n)$. We determine the order of magnitude of $φ_d(n)$, and prove the following upper and lower bounds, for $d>3$: $$\frac{2 n^{d-1}}{d!} -o(n^{d-1}) \leq φ_d(n) \leq \frac{0.86}{(d-1)!}n^{d-1}+o(n^{d-1}).$$ |
| title | Minimum blocking sets for families of partitions |
| topic | Combinatorics Discrete Mathematics 05D15 |
| url | https://arxiv.org/abs/2505.15362 |