On crown-free families of subsets
Author:
Preprint
Abstract
The crown $\Oh_{2t}$ is a height-2 poset whose Hasse diagram is a cycle of length $2t$. A family $\F$ of subsets of $[n]:=\{1,2..., n\}$ is {\em $\Oh_{2t}$-free} if $\Oh_{2t}$ is not a weak subposet of $(\F,\subseteq)$. Let $\La(n,\Oh_{2t})$ be the largest size of $\Oh_{2t}$-free families of subsets of $[n]$. De Bonis-Katona-Swanepoel proved $\La(n,\Oh_{4})= {n\choose \lfloor \frac{n}{2} \rfloor} + {n\choose \lceil \frac{n}{2} \rceil}$. Griggs and Lu proved that $\La(n,\Oh_{2t})=(1+o(1))\nchn$ for all even $t\ge 4$. In this paper, we prove $\La(n,\Oh_{2t})=(1+o(1))\nchn$ for all odd $t\geq 7$.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- On diamond-free subposets of the Boolean latticeJournal of Combinatorial Theory, Series A, 2013
- Diamond-free familiesJournal of Combinatorial Theory, Series A, 2012
- Q 2-free Families in the Boolean LatticeOrder, 2011
- On 14-Cycle-Free Subgraphs of the HypercubeCombinatorics, Probability and Computing, 2009
- On Families of Subsets With a Forbidden SubposetCombinatorics, Probability and Computing, 2009
- Largest Families Without an r-ForkOrder, 2007
- A Ramsey-type result for the hypercubeJournal of Graph Theory, 2006
- Subgraphs of a hypercube containing no small even cyclesJournal of Graph Theory, 1992
- On extremal problems of graphs and generalized graphsIsrael Journal of Mathematics, 1964
- Ein Satz ber Untermengen einer endlichen MengeMathematische Zeitschrift, 1928