TY - JOUR
T1 - On the size of the subset partial order
AU - Elmasry, Amr Ahmed Abd Elmoneim
PY - 2012
Y1 - 2012
N2 - Given a family of k sets with cardinalities S 1,S 2,⋯, S k and N=Σ k i=1S i, we show that the size of the partial order graph induced by the subset relation (called the subset graph) is O(Σ si≤B 2si+N/lgN·Σ si>Blg(s i/B)), 2 where B=lg(N/lg 2N). This implies a simpler proof to the O(N 2/lg 2N) bound concluded in Pritchard (1999) [4].
AB - Given a family of k sets with cardinalities S 1,S 2,⋯, S k and N=Σ k i=1S i, we show that the size of the partial order graph induced by the subset relation (called the subset graph) is O(Σ si≤B 2si+N/lgN·Σ si>Blg(s i/B)), 2 where B=lg(N/lg 2N). This implies a simpler proof to the O(N 2/lg 2N) bound concluded in Pritchard (1999) [4].
KW - Combinatorial problems
KW - Counting arguments
KW - Extremal combinatorics
KW - Partial order
KW - Subset graph
UR - https://www.scopus.com/pages/publications/84859538289
U2 - 10.1016/j.ipl.2012.03.005
DO - 10.1016/j.ipl.2012.03.005
M3 - Journal article
AN - SCOPUS:84859538289
SN - 0020-0190
VL - 112
SP - 487
EP - 489
JO - Information Processing Letters
JF - Information Processing Letters
IS - 12
ER -