Non-trivial $r$-wise agreeing families
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908159009882112 |
|---|---|
| author | Frankl, Peter Kupavskii, Andrey |
| author_facet | Frankl, Peter Kupavskii, Andrey |
| contents | A family of subsets of $[n]$ is $r$-wise agreeing if for any $r$ sets from the family there is an element $x$ that is either contained in all or contained in none of the $r$ sets. The study of such families is motivated by questions in discrete optimization. In this paper, we determine the size of the largest non-trivial $r$-wise agreeing family. This can be seen as a generalization of the classical Brace-Daykin theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_14178 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Non-trivial $r$-wise agreeing families Frankl, Peter Kupavskii, Andrey Combinatorics A family of subsets of $[n]$ is $r$-wise agreeing if for any $r$ sets from the family there is an element $x$ that is either contained in all or contained in none of the $r$ sets. The study of such families is motivated by questions in discrete optimization. In this paper, we determine the size of the largest non-trivial $r$-wise agreeing family. This can be seen as a generalization of the classical Brace-Daykin theorem. |
| title | Non-trivial $r$-wise agreeing families |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2404.14178 |