Jiang, Tao, Pikhurko, Oleg and Yilma, Zelealem (2010) Set systems without a strong simplex. SIAM Journal on Discrete Mathematics, Vol.24 (No.3). pp. 1038-1045. doi:10.1137/090760775

Research output not available from this repository, contact author.

Request Changes to record.

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$, $n>k(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.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Journal or Publication Title:	SIAM Journal on Discrete Mathematics
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	0895-4801
Official Date:	2010
Dates:	Date Event 2010 Published
Volume:	Vol.24
Number:	No.3
Page Range:	pp. 1038-1045
DOI:	10.1137/090760775
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access

Request changes or add full text files to a record

Repository staff actions (login required)

View Item