Friday, April 17, 2015 (3:00 p.m. in Yost 306)

Title: Most Probably Intersecting Families of Subsets

Speaker: Gyula Katona (Renyi Institute, Budapest, and Member, Hungarian Academy of Sciences)

Abstract: Let F be a family of an n-element set. It is called intersecting if every pair of its members have a non-disjoint intersection. It is well- known that an intersecting family satisfies the inequality |F| ≤ 2^(n-1). Suppose that |F | = 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 for some small i’s. 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 probable inclusion-free family too, when the number of members is (n Choose [n/2])+1.