Fractional set systems with few disjoint pairs

Abstract: Ahlswede (1980)  and Frankl (1977)  independently found a result about the structure of set systems with few disjoint pairs. Bollobás and Leader (2003) gave an alternate proof by generalizing to fractional set systems and noting that the optimal fractional set systems are -valued. In this paper we show that this technique does not extend to -intersecting families. We find optimal fractional set systems for some infinite classes of parameters, and we point out that they are strictly better than the corresponding -valued fractional set systems. We prove some results about the structure of an optimal fractional set system, which we use to produce an algorithm for finding such systems. The run time of the algorithm is polynomial in the size of the ground set. [Copyright &y& Elsevier]