On the Average Sizes of Ideals and Antichains in Some Infinite Families of Posets
Abstract
We study the average sizes of ideals and antichains in several families of posets arising from rooted unlabeled trees. For ideals, we encode order ideals by coloring vertices red, with the condition that every descendant of a red vertex is also red. Using generating functions and singularity analysis, we show that for every family governed by a quadratic root decomposition, the average number of red vertices in a tree of size n is asymptotic to n/3. This includes binary plane trees, plane 1-2 trees, plane 2-trees, and 0-1-trees, while unrestricted rooted plane trees instead have average ideal size asymptotic to 2n/5. For antichains, represented by pairwise incomparable blue vertices, the corresponding asymptotic constants depend on the particular branching function; for example, binary plane trees have average antichain size asymptotic to n/6. We also consider plane trees in which every vertex has at most k children and prove that the asymptotic proportion of red vertices increases strictly with k, from 1/3 when k=2 to the limiting value 2/5 for unrestricted rooted plane trees. The asymptotic proportion of blue vertices also increases strictly with k, tending to 3/10. The proofs are based on bivariate generating functions together with the analytic implicit-function and smooth implicit-function methods of analytic combinatorics.
Related
- Simplicial Complexes of Antichains in Root Posets and Related Combinatorics of Dyck Paths
- Optimal and minimal p-ary linear codes from generalized order ideals of hierarchical posets
- Alternating Divisoriality of Prime Ideals along Infinite Chains of Bézout Domains
- Closed maximal eventually different families for Σ03 and weakly Farah ideals
- Reduced and coreduced modules with respect to inverse families of ideals
BibTeX
@misc{bona2026average,
title = {{On the Average Sizes of Ideals and Antichains in Some Infinite Families of Posets}},
author = {Miklos Bona and Ricardo Gomez Aiza},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03579},
eprint = {2610.03579},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03579},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Average Sizes of Ideals and Antichains in Some Infinite Families of Posets
AU - Miklos Bona
AU - Ricardo Gomez Aiza
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.03579
UR - https://arxiv.org/abs/2610.03579
AB - We study the average sizes of ideals and antichains in several families of posets arising from rooted unlabeled trees. For ideals, we encode order ideals by coloring vertices red, with the condition that every descendant of a red vertex is also red. Using generating functions and singularity analysis, we show that for every family governed by a quadratic root decomposition, the average number of red vertices in a tree of size n is asymptotic to n/3. This includes binary plane trees, plane 1-2 trees, plane 2-trees, and 0-1-trees, while unrestricted rooted plane trees instead have average ideal size asymptotic to 2n/5. For antichains, represented by pairwise incomparable blue vertices, the corresponding asymptotic constants depend on the particular branching function; for example, binary plane trees have average antichain size asymptotic to n/6. We also consider plane trees in which every vertex has at most k children and prove that the asymptotic proportion of red vertices increases strictly with k, from 1/3 when k=2 to the limiting value 2/5 for unrestricted rooted plane trees. The asymptotic proportion of blue vertices also increases strictly with k, tending to 3/10. The proofs are based on bivariate generating functions together with the analytic implicit-function and smooth implicit-function methods of analytic combinatorics.
ER -