8 THE BASIC METHOD for notational convenience.Now let s1.....S.be uniformly and independently chosen n-sets,m to be determined.For each coloringx let Ax be the event that non of the S;are monochromatic.By the independence of the S Pr[Ax≤(1-p)m There are 2 colorings so Pr VAx≤2"(1-p)m When this quantity is less than 1 there exist S1,...,Sm so that no Ax holds;that is. S1,....Sm is not two-colorable and hence m(n)<m. The asymptotics provide a fairly typical example of those encountered when employing the probabilistic method.We first use the is valid for all positive p and the terms are quite close when p is small.When m=[ p then 2(1-p)m<2"e-pm 1 so m(n)<m.Now we need to find v to minimize v/p.We may interpret p as twice the probability of picking n white balls from an urn with v/2 white and v/2 black balls,sampling witho ut replacement.It is tempting to estimate p by 2- the probability for sampling with replacemn This approximation would yield m~v2-1(In 2).As v gets smaller,however,the approximation becomes less accurate and,as we wish to minimize m,the trade-off 4 omes essential.We use a second order approximation v-2i 21-ne-n2/2 () as long asvn3/2,estimating -1-+o() =e-/e+0(2/m3) -i Elementary calculus gives v=n2/2 for the optimal value.The evenness ofv may req ire a cha nge of at most 2,which turns out to be asymptotically negligible.This yields the following result of Erdos(1964). Theorem 13.2 m(n)<(()) 二n22n 4 LetF={(Ai,Bi)be a family of pairs of subsets of an arbitrary set.We call F a(k,()-system if Aal =k andB.=e for all=0 and AnB for all distinct i,j with 1 si,j h.Bollobas (1965)proved the following result,which has many interesting extensions and applications. 8 THE BASIC METHOD for notational convenience. Now let Si,..., Sm be uniformly and independently chosen n-sets, m to be determined. For each coloring \ let Ax be the event that none of the Si are monochromatic. By the independence of the Si Pi[Ax]<(l-p)r There are 2V colorings so Pr \M <2"(l-p) r When this quantity is less than 1 there exist Si,..., Sm so that no Ax holds; that is, Si,... , Sm is not two-colorable and henee m(n) < m. The asymptotics provide a fairly typical example of those encountered when employing the probabilistic method. We first use the inequality 1 — p < e~ p . This is valid for all positive p and the terms are quite cióse when p is small. When üln2 then 2"(1 — p)m < 2v e~ pm < 1 so m(n) < m. Now we need to find v to minimize v/p. We may interpret p as twice the probability of picking n white balls from an urn with v/2 white and v/2 black balls, sampling without replacement. It is tempting to estimate p by 2~n+1 , the probability for sampling with replacement. This approximation would yield m ~ v2n_1 (ln2). As v gets smaller, however, the approximation becomes less accurate and, as we wish to minimize m, the trade-off becomes essential. We use a second order approximation P 2(T) (ñ) -íl—n n i-0 •2i V — l )l—n„—n /2v as long as v S> n3 / 2 , estimating v - 2z _ v 2 -i/v+0(i2 /v2 ) Elementary calculus gives v = n 2 /2 for the optimal valué. The evenness of v may require a change of at most 2, which turns out to be asymptotically negligible. This yields the following result of Erdos (1964). eln2 Theorem 2c\n 1.3.2 m{n) < (1 + o(l))—— n ¿ 2 Let T = {(Ai, Bi)}^=1 be a family of pairs of subsets of an arbitrary set. We cali T a (k,í)-system if |A¿¡ = k and |B¿| = i for all 1 < i < h, Ai n B, = 0 and Í4J n B^ ^¿ 0 for all distinct i, j with 1 < i, j < h. Bollobás (1965) proved the following result, which has many interesting extensions and applications