Gyula O.H. Katona - Excluded subposets in the Boolean lattice

dmtcs:3409 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3409
Excluded subposets in the Boolean latticeArticle

Authors: Gyula O.H. Katona 1

  • 1 Alfréd Rényi Institute of Mathematics

We are looking for the maximum number of subsets of an n-element set not containing 4 distinct subsets satisfying $A ⊂B, C ⊂B, C ⊂D$. It is proved that this number is at least the number of the $\lfloor \frac{n }{ 2}\rfloor$ -element sets times $1+\frac{2}{ n}$, on the other hand an upper bound is given with 4 replaced by the value 2.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: extremal problems,families of subsets,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Consultation statistics

This page has been seen 221 times.
This article's PDF has been downloaded 352 times.