pith. sign in

arxiv: 1812.11153 · v2 · pith:3PJ4HVVXnew · submitted 2018-12-28 · 🧮 math.CO

On the d-cluster generalization of ErdH{o}s-Ko-Rado

classification 🧮 math.CO
keywords chooseclustergeneralizationmubayis-ko-radosizecluster-freecollection
0
0 comments X
read the original abstract

If $2 \le d \le k$ and $n \ge dk/(d-1)$, a $d$-cluster is defined to be a collection of $d$ elements of ${[n] \choose k}$ with empty intersection and union of size no more than $2k$. Mubayi conjectured that the largest size of a $d$-cluster-free family $\mathcal{F} \subset {[n] \choose k}$ is ${n-1 \choose k-1}$, with equality holding only for a maximum-sized star. Here, we resolve Mubayi's conjecture and prove a slightly stronger result, thus completing a new generalization of the Erd\H{o}s-Ko-Rado Theorem.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.