On the number of $P$-free set systems for tree posets $P$
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909437235560448 |
|---|---|
| author | Balogh, József Garcia, Ramon I. Wigal, Michael C. |
| author_facet | Balogh, József Garcia, Ramon I. Wigal, Michael C. |
| contents | 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 \choose \lfloor n/2\rfloor}}$. The proof uses a generalization of a theorem by Boris Bukh together with a variation of the multiphase graph container algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09635 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the number of $P$-free set systems for tree posets $P$ Balogh, József Garcia, Ramon I. Wigal, Michael C. Combinatorics 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 \choose \lfloor n/2\rfloor}}$. The proof uses a generalization of a theorem by Boris Bukh together with a variation of the multiphase graph container algorithm. |
| title | On the number of $P$-free set systems for tree posets $P$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.09635 |