On the size of the subset partial order

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 - http://www.scopus.com/inward/record.url?scp=84859538289&partnerID=8YFLogxK

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 -