Saturated chains of subsets and a random walk

DOI10.1016/0097-3165(88)90021-0MaRDI QIDQ1114686zbMATH OpenOpenAlexFDO

Authors J. Griggs

Publication date 1988

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(88)90021-0

zbMATH Keywords

chain partition random walk subsets

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Sums of independent random variables; random walks (60G50)

Review text

This paper concerns the problem: How many of the subsets of an n element set can be partitioned into blocks each block of which has cardinality c and consists of subsets of consecutive cardinalities that nest inside one another? It is shown here that one can answer this and the similar covering problem by using the standard inductive construction of a chain partition (due to de Bruijn, et al.), until chains are of size c, and allowing those at that size to remain so as n increases. (In standard construction, as n increases by 1, each chain gives rise to two chains, and one takes the head from one and attaches it to the other; when the chain has length c here one instead leaves the two chains alone.) Asymptotic results are derived for the resulting proportion of subsets in length c chains, and for a related random walk.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Saturated chains of subsets and a random walk

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114686)