Most Probably Intersecting Families of Subsets

Katona, Gyula and Katona, Gyula (Ifj.) and Katona, Z. (2012) Most Probably Intersecting Families of Subsets. COMBINATORICS PROBABILITY AND COMPUTING, 21 (1-2). pp. 219-227. ISSN 0963-5483

Preview

Text Most Probably Intersecting Families of Subsets.pdf Download (266kB) | Preview

Abstract

Let F be a family of subsets of an n-element set. It is called intersecting if every pair of its members has a non-disjoint intersection. It is well known that an intersecting family satisfies the inequality vertical bar F vertical bar <= 2(n-1). Suppose that vertical bar F vertical bar = 2(n-1) + i. Choose the members of F independently with probability p (delete them with probability 1 - p). The new family is intersecting with a certain probability. We try to maximize this probability by choosing F appropriately. The exact maximum is determined in this paper for some small i. The analogous problem is considered for families consisting of k-element subsets, but the exact solution is obtained only when the size of the family exceeds the maximum size of the intersecting family only by one. A family is said to be inclusion-free if no member is a proper subset of another one. It is well known that the largest inclusion-free family is the one consisting of all [n/2]-element subsets. We determine the most probably inclusion-free family too, when the number of members is (n([n/2])) + 1.

Actions (login required)

Edit Item