Name
Abstract | ||
|---|---|---|
Let 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 || â聣陇 2n-1. Suppose that ||=2n-1 + i. Choose the members of 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 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 $\lfloor \frac{n}{ 2}\rfloor$-element subsets. We determine the most probably inclusion-free family too, when the number of members is $\binom{n}{ \lfloor \frac{n}{ 2}\rfloor} +1$. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1017/S0963548311000587 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
largest inclusion-free family,new family,certain probability,inclusion-free family,probability 1-p,intersecting family,element subsets,exact maximum,probability p,k-element subsets | Exact solutions in general relativity,Discrete mathematics,Family of sets,Combinatorics,Family only,Mathematics | Journal |
Volume | Issue | ISSN |
21 | 1-2 | 0963-5483 |
Citations | PageRank | References |
5 | 0.61 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gyula O. H. Katona | 1 | 264 | 66.44 |
| Gyula Y. Katona | 2 | 118 | 25.96 |
| Zsolt Katona | 3 | 169 | 14.64 |