Intersecting families with bounded intersections
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.20529
curl -X POST /api/v1/records/arxiv/2604.20529/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.20529/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'