Abstract | ||
---|---|---|
A $d$-simplex is a collection of $d+1$ sets such that every $d$ of them have nonempty intersection and the intersection of all of them is empty. A strong $d$-simplex is a collection of $d+2$ sets $A,A_1,\dots,A_{d+1}$ such that $\{A_1,\dots,A_{d+1}\}$ is a $d$-simplex, while $A$ contains an element of $\cap_{j\neq i}A_j$ for each $i$, $1\leq i\leq d+1$. Mubayi and Ramadurai [Combin. Probab. Comput., 18 (2009), pp. 441-454] conjectured that if $k\geq d+1\geq3$, $nk(d+1)/d$, and $\mathcal{F}$ is a family of $k$-element subsets of an $n$-element set that contains no strong $d$-simplex, then $|\mathcal{F}|\leq{n-1\choose k-1}$ with equality only when $\mathcal{F}$ is a star. We prove their conjecture when $k\geq d+2$ and $n$ is large. The case $k=d+1$ was solved in [M. Feng and X. J. Liu, Discrete Math., 310 (2010), pp. 1645-1647] and [Z. Füredi, private communication, St. Paul, MN, 2010]. Our result also yields a new proof of a result of Frankl and Füredi [J. Combin. Theory Ser. A, 45 (1987), pp. 226-262] when $k\geq d+2$ and $n$ is large. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1137/090760775 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
theory ser,m. feng,discrete math,j. liu,j. combin,strong simplex,set systems,st. paul,nonempty intersection,z. f,element set,element subsets,shadows | Discrete mathematics,Combinatorics,Simplex,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
24 | 3 | 0895-4801 |
Citations | PageRank | References |
4 | 0.55 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tao Jiang | 1 | 38 | 4.62 |
Oleg Pikhurko | 2 | 318 | 47.03 |
Zelealem B. Yilma | 3 | 32 | 5.32 |