Forbidding intersection patterns between layers of the cube

Research output: Contribution to journalArticlepeer-review

Standard

Forbidding intersection patterns between layers of the cube. / Long, Eoin.

In: Journal of Combinatorial Theory, Series A, Vol. 134, 01.08.2015, p. 103-120.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Bibtex

@article{13b09e5db7dc4548949fa58332095371,
title = "Forbidding intersection patterns between layers of the cube",
abstract = "A family ${\cal A}$ is said to be an antichain if $A \not \subset B$ for all distinct $A, B \in {\cal A}$. A classic result of Sperner shows that such families satisfy $|{\cal A}| \leq \binom {n}{\lfloor n/2\rfloor }$, which is easily seen to be best possible. One can view the antichain condition as a restriction on the intersection sizes between sets in different layers of ${\cal P}[n]$. More generally one can ask, given a collection of intersection restrictions between the layers, how large can families respecting these restrictions be? Answering a question of Kalai [8], we show that for most collections of such restrictions, layered families are asymptotically largest. This extends results of Leader and the author from [11].",
author = "Eoin Long",
year = "2015",
month = aug,
day = "1",
doi = "10.1016/j.jcta.2014.08.008",
language = "English",
volume = "134",
pages = "103--120",
journal = "Journal of Combinatorial Theory, Series A",
issn = "0097-3165",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Forbidding intersection patterns between layers of the cube

AU - Long, Eoin

PY - 2015/8/1

Y1 - 2015/8/1

N2 - A family ${\cal A}$ is said to be an antichain if $A \not \subset B$ for all distinct $A, B \in {\cal A}$. A classic result of Sperner shows that such families satisfy $|{\cal A}| \leq \binom {n}{\lfloor n/2\rfloor }$, which is easily seen to be best possible. One can view the antichain condition as a restriction on the intersection sizes between sets in different layers of ${\cal P}[n]$. More generally one can ask, given a collection of intersection restrictions between the layers, how large can families respecting these restrictions be? Answering a question of Kalai [8], we show that for most collections of such restrictions, layered families are asymptotically largest. This extends results of Leader and the author from [11].

AB - A family ${\cal A}$ is said to be an antichain if $A \not \subset B$ for all distinct $A, B \in {\cal A}$. A classic result of Sperner shows that such families satisfy $|{\cal A}| \leq \binom {n}{\lfloor n/2\rfloor }$, which is easily seen to be best possible. One can view the antichain condition as a restriction on the intersection sizes between sets in different layers of ${\cal P}[n]$. More generally one can ask, given a collection of intersection restrictions between the layers, how large can families respecting these restrictions be? Answering a question of Kalai [8], we show that for most collections of such restrictions, layered families are asymptotically largest. This extends results of Leader and the author from [11].

U2 - 10.1016/j.jcta.2014.08.008

DO - 10.1016/j.jcta.2014.08.008

M3 - Article

VL - 134

SP - 103

EP - 120

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

SN - 0097-3165

ER -