10 THE BASIC METHOD Remark.The above proof works whenever p is a prime that does not divide any of the numbers b.This can be used to design n an efficient deterministic algorithm for finding a sum-free subset A of size bigger than B/3 in a given set B as above.In Alon and Kleitman (1990)it is shown that every set of n nonzero elements of an arbitrary abelian group contains a sum-free subset of more than 2n/7 elements,and that the constant 2/7 is best possible.The best possible constant in Theorem 1.4.1 is not known. 1.5 DISJOINT PAIRS The probabilistic method is most striking when it is applied to prove theorems whose statement does not seem to suggest at all the need for probability.Most of the examples given in the previo sections are simple instances of such statements.In this section we describe a(slightly)more complicated result,due to Alon and Frankl (1985),which solves a conjecture of Daykin and Erdos. Let F be a family of m distinct subsets of X={1,2,...,n}.Let d(F)denote the number of disjoint pairs in F:that is, d(=F,F'):F,FEF,FOF=0) Daykin and Erdos conjectured that if m =2(1/2+6)m,then,for every fixed>0. dF)=o(m2),as n tends to infinity.This result follows from the following theorem, which is a special case of a more general result. Theorem 1.5.1 Let F be a family of m=2(1/2+6m subsets of ={1,2.....nh. where 6>0.Then d(F)<m2-6212 (1.1) Proof.Suppose(1.1)is false and pick independently t members A1,A2,....A ofF with repetitions at random,where t is a large positive integer,to be chosen later.We will show that with positive probability still this establish(1.1). In fact, PrlA1UA2U…UAtl≤n/2) Pr [Ai c S,i=1,...] (1.2) ≤2”(2n/2/21/2+6)n)t=2n(1-6) Define v(B)=I{A∈F:BnA=0I. 10 THE BASIC METHOD Remark. The above proof works whenever p is a prime that does not divide any of the numbers 6¿. This can be used to design an efficient deterministic algorithm for finding a sum-free subset A of size bigger than \B\/3 in a given set B as above. In Alón and Kleitman (1990) it is shown that every set of n nonzero elements of an arbitrary abelian group contains a sum-free subset of more than 2n/7 elements, and that the constant 2/7 is best possible. The best possible constant in Theorem 1.4.1 is not known. 1.5 DISJOINT PAIRS The probabilistic method is most striking when it is applied to prove theorems whose statement does not seem to suggest at all the need for probability. Most of the examples given in the previous sections are simple instances of such statements. In this section we describe a (slightly) more complicated result, due to Alón and Frankl (1985), which solves a conjecture of Daykin and Erdós. Let T be a family of m distinct subsets of X = {1,2,..., n}. Let d(T) denote the number of disjoint pairs in F; that is, d(f) = |{{F,F'}:F,F'ef,fnF ' = f)}| . Daykin and Erdos conjectured that if m = 2(1 / 2+<5) ra , then, for every fixed 6 > 0, dí¿F) = o(?n2 ),asntendstoinfinity. This result follows from the following theorem, which is a special case of a more general result. Theorem 1.5.1 Let F be a family ofm = 2^'2+^ n subsets of X = {1,2,..., n}, where 5 > 0. Then d{T) < m 2 - s2/2 . (1.1) Proof. Suppose (1.1) is false and pick independently t members A\, Ai,..., At of T with repetitions at random, where t is a large positive integer, to be chosen later. We will show that with positive probability \AX U A2 U • • • U At \ > n/2 and still this unión is disjoint to more than 2"/2 distinct subsets of X. This contradiction will establish(l.l). In fact, Prp ! UA 2 U---U^Í | <n/2 ] < J2 Pr[Ai<zS,i = l,...,t] (1.2) scx |S|=n/ 2 <- nnínn/2 ln(l/2+5)n\t r>n(l— St) Define v(B) = \{AeF:BnA = Q}\