Premium
On Kruskal's cascades and counting containments in a set of subsets
Author(s) -
Daykin David E.,
Frankl Peter
Publication year - 1983
Publication title -
mathematika
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.955
H-Index - 29
eISSN - 2041-7942
pISSN - 0025-5793
DOI - 10.1112/s0025579300010470
Subject(s) - mathematics , combinatorics , cardinality (data modeling) , product (mathematics) , integer (computer science) , set (abstract data type) , cascade , discrete mathematics , geometry , computer science , data mining , programming language , chemistry , chromatography
Let ℱ be a set of m subsets of X = {1,2,…, n }. We study the maximum number λ of containments Y ⊂ Z with Y, Z ∊ ℱ. Theorem 9. λ = ( 1 + o ( 1 ) ) (2 m ) , if, and only if , m l/n → 1. When n is large and members of ℱ have cardinality k or k–1 we determine λ. For this we bound (Δ N )/ N where Δ N is the shadow of Kruskal's k ‐cascade for the integer N . Roughly, if m ∼ N + Δ N , then λ ∼ kN with infinitely many cases of equality. A by‐product is Theorem 7 of LYM posets.