On the Number of P-free Set Systems for Tree Posets P

József Balogh; Ramon I. Garcia; Michael C. Wigal

doi:10.1007/s11083-025-09697-x

On the Number of P-free Set Systems for Tree Posets P

József Balogh, Ramon I. Garcia, Michael C. Wigal

Mathematics

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

Abstract

We say a finite poset P is a tree poset if its Hasse diagram is a tree. Let k be the length of the largest chain contained in P. We show that when P is a fixed tree poset, the number of P-free set systems in 2[n] is 2(1+o(1))(k-1)n⌊n/2⌋. The proof uses a generalization of a theorem by Boris Bukh together with a variation of the multiphase graph container algorithm.

Original language	English (US)
Journal	Order
Early online date	Jan 30 2025
DOIs	https://doi.org/10.1007/s11083-025-09697-x
State	E-pub ahead of print - Jan 30 2025

Keywords

Containers
Forbidden subposet
Set system
Supersaturation
Tree poset

ASJC Scopus subject areas

Algebra and Number Theory
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1007/s11083-025-09697-x

Library availability

Discover UIUC Full Text

Cite this

@article{c3c12a6337134ba7af5f033594d6fe9f,

title = "On the Number of P-free Set Systems for Tree Posets P",

abstract = "We say a finite poset P is a tree poset if its Hasse diagram is a tree. Let k be the length of the largest chain contained in P. We show that when P is a fixed tree poset, the number of P-free set systems in 2[n] is 2(1+o(1))(k-1)n⌊n/2⌋. The proof uses a generalization of a theorem by Boris Bukh together with a variation of the multiphase graph container algorithm.",

keywords = "Containers, Forbidden subposet, Set system, Supersaturation, Tree poset",

author = "J{\'o}zsef Balogh and Garcia, {Ramon I.} and Wigal, {Michael C.}",

note = "J\u00F3zsef Balogh was supported in part by NSF grants DMS-1764123 and RTG DMS-1937241, FRG DMS-2152488, and the Arnold O. Beckman Research Award (UIUC Campus Research Board RB 24012).",

year = "2025",

month = jan,

day = "30",

doi = "10.1007/s11083-025-09697-x",

language = "English (US)",

journal = "Order",

issn = "0167-8094",

publisher = "Springer Netherlands",

}

TY - JOUR

T1 - On the Number of P-free Set Systems for Tree Posets P

AU - Balogh, József

AU - Garcia, Ramon I.

AU - Wigal, Michael C.

N1 - J\u00F3zsef Balogh was supported in part by NSF grants DMS-1764123 and RTG DMS-1937241, FRG DMS-2152488, and the Arnold O. Beckman Research Award (UIUC Campus Research Board RB 24012).

PY - 2025/1/30

Y1 - 2025/1/30

N2 - We say a finite poset P is a tree poset if its Hasse diagram is a tree. Let k be the length of the largest chain contained in P. We show that when P is a fixed tree poset, the number of P-free set systems in 2[n] is 2(1+o(1))(k-1)n⌊n/2⌋. The proof uses a generalization of a theorem by Boris Bukh together with a variation of the multiphase graph container algorithm.

AB - We say a finite poset P is a tree poset if its Hasse diagram is a tree. Let k be the length of the largest chain contained in P. We show that when P is a fixed tree poset, the number of P-free set systems in 2[n] is 2(1+o(1))(k-1)n⌊n/2⌋. The proof uses a generalization of a theorem by Boris Bukh together with a variation of the multiphase graph container algorithm.

KW - Containers

KW - Forbidden subposet

KW - Set system

KW - Supersaturation

KW - Tree poset

UR - http://www.scopus.com/inward/record.url?scp=85217159272&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85217159272&partnerID=8YFLogxK

U2 - 10.1007/s11083-025-09697-x

DO - 10.1007/s11083-025-09697-x

M3 - Article

AN - SCOPUS:85217159272

SN - 0167-8094

JO - Order

JF - Order

ER -

On the Number of P-free Set Systems for Tree Posets P

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this