Katona, Gyula and Katona, Gyula (Ifj.) and Katona, Z. (2012) Most Probably Intersecting Families of Subsets. COMBINATORICS PROBABILITY AND COMPUTING, 21 (12). pp. 219227. ISSN 09635483

Text
Most Probably Intersecting Families of Subsets.pdf Download (266kB)  Preview 
Abstract
Let F be a family of subsets of an nelement set. It is called intersecting if every pair of its members has a nondisjoint intersection. It is well known that an intersecting family satisfies the inequality vertical bar F vertical bar <= 2(n1). Suppose that vertical bar F vertical bar = 2(n1) + 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 kelement 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 inclusionfree if no member is a proper subset of another one. It is well known that the largest inclusionfree family is the one consisting of all [n/2]element subsets. We determine the most probably inclusionfree family too, when the number of members is (n([n/2])) + 1.
Item Type:  Article 

Uncontrolled Keywords:  SYSTEMS; THEOREMS; FINITE SETS; fluorine; Set theory; Probability; Intersecting families; Exact solution 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  11 Dec 2013 09:36 
Last Modified:  11 Dec 2013 10:13 
URI:  http://real.mtak.hu/id/eprint/7992 
Actions (login required)
Edit Item 