Hilton-Milner theorem for $k$-multisets
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910515374063616 |
|---|---|
| author | Liao, Jiaqi Lv, Zequn Cao, Mengyu Lu, Mei |
| author_facet | Liao, Jiaqi Lv, Zequn Cao, Mengyu Lu, Mei |
| contents | Let $ k, n \in \mathbb{N}^+ $ and $ m \in \mathbb{N}^+ \cup \{\infty \} $. A $ k $-multiset in $ [n]_m $ is a $ k $-set whose elements are integers from $ \{1, 2, \ldots, n\} $, and each element is allowed to have at most $ m $ repetitions. A family of $ k $-multisets in $ [n]_m $ is said to be intersecting if every pair of $ k $-multisets from the family have non-empty intersection. In this paper, we give the size and structure of the largest non-trivial intersecting family of $ k $-multisets in $ [n]_m $ for $ n \geq k + \lceil k/m \rceil $. In the special case when $m=\infty$, our result gives rise to an unbounded multiset version for Hilton-Milner Theorem given by Meagher and Purdy. Furthermore, our main theorem unites the statements of the Hilton-Milner Theorem for finite sets and unbounded multisets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_03585 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hilton-Milner theorem for $k$-multisets Liao, Jiaqi Lv, Zequn Cao, Mengyu Lu, Mei Combinatorics 05D05, 05C35, 05A15 Let $ k, n \in \mathbb{N}^+ $ and $ m \in \mathbb{N}^+ \cup \{\infty \} $. A $ k $-multiset in $ [n]_m $ is a $ k $-set whose elements are integers from $ \{1, 2, \ldots, n\} $, and each element is allowed to have at most $ m $ repetitions. A family of $ k $-multisets in $ [n]_m $ is said to be intersecting if every pair of $ k $-multisets from the family have non-empty intersection. In this paper, we give the size and structure of the largest non-trivial intersecting family of $ k $-multisets in $ [n]_m $ for $ n \geq k + \lceil k/m \rceil $. In the special case when $m=\infty$, our result gives rise to an unbounded multiset version for Hilton-Milner Theorem given by Meagher and Purdy. Furthermore, our main theorem unites the statements of the Hilton-Milner Theorem for finite sets and unbounded multisets. |
| title | Hilton-Milner theorem for $k$-multisets |
| topic | Combinatorics 05D05, 05C35, 05A15 |
| url | https://arxiv.org/abs/2308.03585 |