Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2604.20529 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916044318179328 |
|---|---|
| author | Ago, Kristina Katona, Gyula O. H. |
| author_facet | Ago, Kristina Katona, Gyula O. H. |
| contents | Let $\mathcal F\subset 2^{[n]}$ be an $s$-uniform family such that every two distinct sets have a nonempty intersection but intersect in at most $k$ elements. By the well-known Ray-Chaudhuri--Wilson theorem, since the intersections can take at most $k$ different values, we have $|\mathcal F|\leq \binom{n}{k}$. We give a stronger upper bound under our assumptions above, when $n$ is large enough compared to $s$ (and $k+1<s$): $|\mathcal F|\leq \frac{\binom{n-1}{k}}{\binom{s-1}{k}}$. This is a special case of an old theorem of Deza, Erd\H os and Frankl, but our proof is simpler and gives a better threshold for $n$. Furthermore, we prove a generalization of the Erd\H os--Ko--Rado theorem for non-uniform families. Let $\mathcal F\subset \binom{[n]}{k}\cup\binom{[n]}{k+1}\cup\dots\cup\binom{[n]}{s}$, $3\leq k\leq s$, be a family such that for every two distinct sets
the size of the intersection is between 1 and $k-1$ and $n$ is large enough then $|\mathcal F|\leq {n-1 \choose k-1}$.
\emph{Mathematics Subject Classification (2020):} 05D05
\emph{Keywords: intersecting families, uniform families, Ray-Chaudhuri--Wilson theorem, Erd\H os--Ko--Rado theorem} |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_20529 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Intersecting families with bounded intersections Ago, Kristina Katona, Gyula O. H. Combinatorics 05D05 Let $\mathcal F\subset 2^{[n]}$ be an $s$-uniform family such that every two distinct sets have a nonempty intersection but intersect in at most $k$ elements. By the well-known Ray-Chaudhuri--Wilson theorem, since the intersections can take at most $k$ different values, we have $|\mathcal F|\leq \binom{n}{k}$. We give a stronger upper bound under our assumptions above, when $n$ is large enough compared to $s$ (and $k+1<s$): $|\mathcal F|\leq \frac{\binom{n-1}{k}}{\binom{s-1}{k}}$. This is a special case of an old theorem of Deza, Erd\H os and Frankl, but our proof is simpler and gives a better threshold for $n$. Furthermore, we prove a generalization of the Erd\H os--Ko--Rado theorem for non-uniform families. Let $\mathcal F\subset \binom{[n]}{k}\cup\binom{[n]}{k+1}\cup\dots\cup\binom{[n]}{s}$, $3\leq k\leq s$, be a family such that for every two distinct sets the size of the intersection is between 1 and $k-1$ and $n$ is large enough then $|\mathcal F|\leq {n-1 \choose k-1}$. \emph{Mathematics Subject Classification (2020):} 05D05 \emph{Keywords: intersecting families, uniform families, Ray-Chaudhuri--Wilson theorem, Erd\H os--Ko--Rado theorem} |
| title | Intersecting families with bounded intersections |
| topic | Combinatorics 05D05 |
| url | https://arxiv.org/abs/2604.20529 |