On families of subsets with a forbidden subposet
| dc.creator | Griggs, Jerrold R. | |
| dc.creator | Lu, Linyuan | |
| dc.date | 2008-07-23 | |
| dc.date.accessioned | 2026-07-07T09:52:23Z | |
| dc.date.available | 2026-07-07T09:52:23Z | |
| dc.description | Let $\F\subset 2^{[n]}$ be a family of subsets of $\{1,2,..., n\}$. For any poset $H$, we say $\F$ is $H$-free if $\F$ does not contain any subposet isomorphic to $H$. Katona and others have investigated the behavior of $\La(n,H)$, which denotes the maximum size of $H$-free families $\F\subset 2^{[n]}$. Here we use a new approach, which is to apply methods from extremal graph theory and probability theory to identify new classes of posets $H$, for which $\La(n,H)$ can be determined asymptotically as $n\to\infty$ for various posets $H$, including two-end-forks, up-down trees, and cycles $C_{4k}$ on two levels. | |
| dc.description | 19 pages, submitted to CPC | |
| dc.identifier | https://arxiv.org/abs/0807.3702 | |
| dc.identifier | http://arxiv.org/abs/0807.3702 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/165576 | |
| dc.subject | Combinatorics | |
| dc.subject | 05D05 | |
| dc.title | On families of subsets with a forbidden subposet | |
| dc.type | text |