Saturating Sperner Families

Dániel Gerbner; Balázs Keszegh; Nathan Lemons; Cory Palmer; Dömötör Pálvölgyi; Balázs Patkós

doi:10.1007/s00373-012-1195-6

Saturating Sperner Families

Dániel Gerbner
, Balázs Keszegh
, Nathan Lemons
, Cory Palmer
, Dömötör Pálvölgyi
, Balázs Patkós

Mathematical Sciences

Research output: Contribution to journal › Article › peer-review

29 Scopus citations

Abstract

A family F ⊆ 2^[n] saturates the monotone decreasing property P if F satisfies P and one cannot add any set to F such that property P is still satisfied by the resulting family. We address the problem of finding the minimum size of a family saturating the k-Sperner property and the minimum size of a family that saturates the Sperner property and that consists only of l-sets and (l + 1)-sets.

Original language	English
Pages (from-to)	1355-1364
Number of pages	10
Journal	Graphs and Combinatorics
Volume	29
Issue number	5
DOIs	https://doi.org/10.1007/s00373-012-1195-6
State	Published - Sep 2013

Funding

The research of B. Patkós’s was supported by Hungarian National Scientific Fund, Grant Numbers: OTKA K-69062 and PD-83586. The research of D. Gerbner, B. Keszegh and C. Palmer was supported by Hungarian National Scientific Fund, Grant number: OTKA NK-78439. The European Union and the European Social Fund have provided financial support to the project under the Grant Agreement No. TÁMOP 4.2.1./B-09/1/KMR-2010-0003 to D. Pálvölgyi.

Funders	Funder number
PD-83586, OTKA K-69062
European Commission
NK-78439

Keywords

Extremal set theory
Saturation
Sperner property

Access to Document

10.1007/s00373-012-1195-6

Cite this

@article{f730f02ad7d949bc9626209c1520651c,

title = "Saturating Sperner Families",

abstract = "A family F ⊆ 2[n] saturates the monotone decreasing property P if F satisfies P and one cannot add any set to F such that property P is still satisfied by the resulting family. We address the problem of finding the minimum size of a family saturating the k-Sperner property and the minimum size of a family that saturates the Sperner property and that consists only of l-sets and (l + 1)-sets.",

keywords = "Extremal set theory, Saturation, Sperner property",

author = "D{\'a}niel Gerbner and Bal{\'a}zs Keszegh and Nathan Lemons and Cory Palmer and D{\"o}m{\"o}t{\"o}r P{\'a}lv{\"o}lgyi and Bal{\'a}zs Patk{\'o}s",

note = "Funding Information: The research of B. Patk{\'o}s{\textquoteright}s was supported by Hungarian National Scientific Fund, Grant Numbers: OTKA K-69062 and PD-83586. Funding Information: The research of D. Gerbner, B. Keszegh and C. Palmer was supported by Hungarian National Scientific Fund, Grant number: OTKA NK-78439. Funding Information: The European Union and the European Social Fund have provided financial support to the project under the Grant Agreement No. T{\'A}MOP 4.2.1./B-09/1/KMR-2010-0003 to D. P{\'a}lv{\"o}lgyi. ",

year = "2013",

month = sep,

doi = "10.1007/s00373-012-1195-6",

language = "English",

volume = "29",

pages = "1355--1364",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "5",

}

TY - JOUR

T1 - Saturating Sperner Families

AU - Gerbner, Dániel

AU - Keszegh, Balázs

AU - Lemons, Nathan

AU - Palmer, Cory

AU - Pálvölgyi, Dömötör

AU - Patkós, Balázs

N1 - Funding Information: The research of B. Patkós’s was supported by Hungarian National Scientific Fund, Grant Numbers: OTKA K-69062 and PD-83586. Funding Information: The research of D. Gerbner, B. Keszegh and C. Palmer was supported by Hungarian National Scientific Fund, Grant number: OTKA NK-78439. Funding Information: The European Union and the European Social Fund have provided financial support to the project under the Grant Agreement No. TÁMOP 4.2.1./B-09/1/KMR-2010-0003 to D. Pálvölgyi.

PY - 2013/9

Y1 - 2013/9

N2 - A family F ⊆ 2[n] saturates the monotone decreasing property P if F satisfies P and one cannot add any set to F such that property P is still satisfied by the resulting family. We address the problem of finding the minimum size of a family saturating the k-Sperner property and the minimum size of a family that saturates the Sperner property and that consists only of l-sets and (l + 1)-sets.

AB - A family F ⊆ 2[n] saturates the monotone decreasing property P if F satisfies P and one cannot add any set to F such that property P is still satisfied by the resulting family. We address the problem of finding the minimum size of a family saturating the k-Sperner property and the minimum size of a family that saturates the Sperner property and that consists only of l-sets and (l + 1)-sets.

KW - Extremal set theory

KW - Saturation

KW - Sperner property

UR - https://www.scopus.com/pages/publications/84882773958

U2 - 10.1007/s00373-012-1195-6

DO - 10.1007/s00373-012-1195-6

M3 - Article

AN - SCOPUS:84882773958

SN - 0911-0119

VL - 29

SP - 1355

EP - 1364

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 5

ER -

Saturating Sperner Families

Abstract

Funding

Keywords

Access to Document

Other files and links

Cite this