The Library
Set systems without a strong simplex
Tools
Tools
Tools
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 ISSN 0895-4801.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1137/090760775
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, Engineering and Medicine > 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: |
|
||||
| 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 |
