Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.08513 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909345354088448 |
|---|---|
| author | Xi, Zoe |
| author_facet | Xi, Zoe |
| contents | A classical theorem of Baranyai states that, given integers $2\leq k < n$ such that $k$ divides $n$, one can find a family of ${n-1\choose k-1}$ partitions of $[n]$ into $k$-element subsets such that every subset appears in exactly one partition. In this paper, we build on recent work by Katona and Katona in studying partial partitions, or parpartitions, of $[n]$ that consist of $k$-element sets not overlapping significantly. More precisely, two parpartitions $P_1$ and $P_2$ are considered $(α,β)$-close for $α,β\in (0,1)$ if there exist subsets $A_1\neq B_1\in P_1$ and $A_2\neq B_2\in P_2$ such that $|A_1\cap A_2| > α{k}$ and $|B_1\cap B_2| > β{k}$.
We establish that, given integers $k$, $\ell$, and $n$ satisfying $k^2\ell\leq n$ and $α, β\in (0, 1)$ satisfying $α+β\geq{(k+2)/k}$, one can find $\lfloor {n\choose
k}/\ell\rfloor$ $(k, \ell)$-parpartitions of $[n]$ such that no two distinct $(k, \ell)$-parpartitions are $(α,β)$-close; this result improves the condition $k=O(1)$ and $\ell=o(\sqrt{n})$ in a corresponding result by Katona and Katona for $α= β= 1/2$. We also prove that, given integers $k$, $\ell$, and $n$ satisfying $k=O(1)$ and $\ell=o(\sqrt{n})$, there is a cyclic ordering of the $k$-element subsets of $[n]$ for any chosen $α+β\geq{1}$ such that any $\ell$ consecutive $k$-element subsets in the ordering form a $(k, \ell)$-parpartition of $[n]$, which we refer to as a consecutive $(k, \ell)$-parpartition (according to the ordering), and any two of these disjoint consecutive $(k, \ell)$-parpartitions are not $(α,β)$-close. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08513 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Variants of Baranyai's Theorem with Additional Conditions Xi, Zoe Combinatorics A classical theorem of Baranyai states that, given integers $2\leq k < n$ such that $k$ divides $n$, one can find a family of ${n-1\choose k-1}$ partitions of $[n]$ into $k$-element subsets such that every subset appears in exactly one partition. In this paper, we build on recent work by Katona and Katona in studying partial partitions, or parpartitions, of $[n]$ that consist of $k$-element sets not overlapping significantly. More precisely, two parpartitions $P_1$ and $P_2$ are considered $(α,β)$-close for $α,β\in (0,1)$ if there exist subsets $A_1\neq B_1\in P_1$ and $A_2\neq B_2\in P_2$ such that $|A_1\cap A_2| > α{k}$ and $|B_1\cap B_2| > β{k}$. We establish that, given integers $k$, $\ell$, and $n$ satisfying $k^2\ell\leq n$ and $α, β\in (0, 1)$ satisfying $α+β\geq{(k+2)/k}$, one can find $\lfloor {n\choose k}/\ell\rfloor$ $(k, \ell)$-parpartitions of $[n]$ such that no two distinct $(k, \ell)$-parpartitions are $(α,β)$-close; this result improves the condition $k=O(1)$ and $\ell=o(\sqrt{n})$ in a corresponding result by Katona and Katona for $α= β= 1/2$. We also prove that, given integers $k$, $\ell$, and $n$ satisfying $k=O(1)$ and $\ell=o(\sqrt{n})$, there is a cyclic ordering of the $k$-element subsets of $[n]$ for any chosen $α+β\geq{1}$ such that any $\ell$ consecutive $k$-element subsets in the ordering form a $(k, \ell)$-parpartition of $[n]$, which we refer to as a consecutive $(k, \ell)$-parpartition (according to the ordering), and any two of these disjoint consecutive $(k, \ell)$-parpartitions are not $(α,β)$-close. |
| title | Variants of Baranyai's Theorem with Additional Conditions |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.08513 |