Mathematics – Combinatorics
Scientific paper
2011-08-16
Mathematics
Combinatorics
15 pages
Scientific paper
A family X of sets is said to be intersecting if any two members of X have non-empty intersection. It is a well-known and simple fact that an intersecting family of subsets of [n]={1,2,...,n} can contain at most 2^(n-1) sets. Katona, Katona and Katona ask the following question. Suppose instead a family X of subsets of [n] satisfies |X|=2^(n-1)+i for some fixed i>0. Create a new family X_p by choosing each member of X independently with some fixed probability p. How do we choose X to maximize the probability that X_p is intersecting? They conjecture that there is a nested sequence of optimal families for i=1, 2, ..., 2^(n-1). In this paper, we show that the families [n]^(\ge r)={A\subset[n]:|A|\ge r} are optimal for the appropriate values of i, thereby proving the conjecture for this sequence of values. Moreover, we show that for intermediate values of i there exist optimal families lying between those we have found. It turns out that the optimal families we find simultaneously maximize the number of intersecting subfamilies of every possible order. Standard compression techniques appear inadequate to solve the problem as they do not preserve intersection properties of subfamilies. Instead, our main tool is a novel compression method, together with a way of `compressing' subfamilies, which may be of independent interest.
No associations
LandOfFree
Compressions and Probably Intersecting Families does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Compressions and Probably Intersecting Families, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressions and Probably Intersecting Families will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-195284