6 THE BASIC METHOD the number of vertices u that do not lie in the union of the sets c(v)of the vertices chos sen so far is r.By the ass umption,the sum of the cardinalities of the sets C(u over all such uncovered vertices u is at least r(+1),and hence,by averaging.there is a vertex v that belongs to at least r(+1)/n such sets C(u).Adding this v to the set of chosen vertices we observe that the number of uncovered vertices is now at mostr(1-(+1)/n).It follows that in each iteration of the above procedure the number of u ncovered vertices decreases by a factor of 1-(6+1)/n and hence after n In(6+1)/(6+1)steps there will be at most n/(6+1)yet uncovered vertices that can now be added to the set of chosen vertices to form a dominating set of size at most equal to the one in the conclusion of Theorem 1.2.2. Combining this ith some ideas of Podderyugin and Matula,very efficient algorithm to decide if a given undirected graph on n vertices is,say.n/2 edge-connected.A cut in a graph G=(V,E)is a partition of the set of vertices V into two nonempty disjoint sets V=ViUV2.If Vi and we say that the cut separates v and v2. The size of the cut is the number of edges of G having one end in Vi and another end in V2.In fact,we sometimes identify the cut with the set of these edges.The edge connectiviry of G is the minimum size of a cut of G. The following lemma is due to Podderyugin and Matula (independently). Lemma 1.2.3 Let G =(V,E)be a graph with minimum degree 6 and letV =ViUV2 be a cut of size smaller than 6 in G.Then every dominating set U of G has vertices in Vi and in V2 Proof.Suppose this is false and UVi.Choose,arbitrarily,a vertex V2 and let v1,v2,...,vs be 6 of its neighbors.For each i,1 <i6,define an edge e of the given cut as follows;if v Vi then e=fv,vi,otherwise,v;E V2 and since U is dominating there is at least one vertex uU such that u,is an edge;take such a u and put e u,vi).The 6 edges e,...,e are all dist and all lie in the given cut,contradicting the assumption that its size is less than This completes the proof. ■ Let G=(V,E)be a graph on n vertices,and suppose we wish to decide if Gis n/2 edge-connected:that is,if its edg vity is at least n/2.Matula showed,by applying Lemma 1.3.that this can be done in time (n).By the remark following the proof of Theorem 1.2.2,we can slightly improve it and get an O(n8/3 log n)algorithm as follows.We first check if the minimum degree 6 of onnected,and the algorithn ends {ui,...,uk}of G where k=O(log n).and it can in fact be found in time O(n).We now find,for each i,2 <i<k,the minimum size s;of a cut that separates u from u.Each of these problems can be solved by solving a standard network flow problem in time see.Tarjan()By Lemma 1.2.3 the edge conectivity ofis simply the minimum between 6 and min2<s.The total time of the algorithm is O(n8/3 logn),as claimed
6 THE BASIC METHOD the number of vértices u that do not lie in the unión of the sets C(v) of the vértices chosen so far is r. By the assumption, the sum of the cardinalities of the sets C(u) over all such uncovered vértices u is at least r(S + 1), and henee, by averaging, there is a vértex v that belongs to at least r(S + l)/n such sets C{u). Adding this v to the set of chosen vértices we observe that the number of uncovered vértices is now at most r(l — (5 + l)/n). It follows that in each iteration of the above procedure the number of uncovered vértices decreases by a factor of 1 — (5 + l)/n and henee after n ln(í + l)/(¿ + 1) steps there will be at most n/(6 + 1) yet uncovered vértices that can now be added to the set of chosen vértices to form a dominating set of size at most equal to the one in the conclusión of Theorem 1.2.2. Combining this with some ideas of Podderyugin and Matula, we can obtain a very efficient algorithm to decide if a given undirected graph on n vértices is, say, n/2 edge-connected. A cut in a graph G = (V, E) is a partition of the set of vértices V into two nonempty disjoint sets V = V\ U V¿. If v\ e V\ and v-¿ € V2 we say that the cut separates v\ and Vi. The size of the cut is the number of edges of G having one end in Vi and another end in V?. In fact, we sometimes identify the cut with the set of these edges. The edge connectivity of G is the minimum size of a cut of G. The following lemma is due to Podderyugin and Matula (independently). Lemma 1.2.3 Let G = (V,E)bea graph with minimum degree 5 and let V = V\ U V2 be a cut of size smaller than 6 in G Then every dominating set U ofG has vértices in V\ and in V2. Proof. Suppose this is false and í/ C Vi. Choose, arbitrarily, a vértex v £ V2 and let vi, t>2, • • •, vg be S of its neighbors. For each i, 1 < i < S, define an edge e¿ of the given cut as follows; if Vi G Vi then e¿ = {v, Vi}, otherwise, v¿ e V2 and since U is dominating there is at least one vértex u 6 U such that {u, w¿} is an edge; take such a u and put e¿ = {u, v¿}. The S edges ei,... , e¿ are all distinct and all lie in the given cut, contradicting the assumption that its size is less than S. This completes the proof. • Let G = (V,E) be a graph on n vértices, and suppose we wish to decide if G is n/2 edge-connected; that is, if its edge connectivity is at least n/2. Matula showed, by applying Lemma 1.2.3, that this can be done in time 0(n3 ). By the remark following the proof of Theorem 1.2.2, we can slightly improve it and get an 0(n8 / 3 logn) algorithm as follows. We first check if the minimum degree 5 of G is at least n/2. If not, G is not n/2 edge-connected, and the algorithm ends. Otherwise, by Theorem 1.2.2 there is a dominating set U = {ui,... ,Uk} of G, where k = O(logn), and it can in fact be found in time 0(n2 ). We now find, for each i, 2 < i < k, the minimum size s¿ of a cut that separates u\ from u¿. Each of these problems can be solved by solving a standard network flow problem in time 0(n8 / 3 ) [see, e.g., Tarjan (1983)]. By Lemma 1.2.3 the edge connectivity of G is simply the minimum between 5 and min2<¿<fc s¿. The total time of the algorithm is 0(ns / 3 log n), as claimed
COMBINATORICS 1.3 COMBINATORICS A hypergraph is a pair H=(V,E).where V is a finite set whose elements are called vertices and E is a family of subsets of V,called edges.It is n-uniform if each of its edges contains precisely n vertices.We say that H has property B,or that it is two-colorable if there is a two-coloring of V such that no edge is monochromatic Letm()denote the minimum of that does not have property B. Proposition 1.3.1 [Erdos(1963a)]Every n-uniform hypergraph with less than 2n- edges has property B.Therefore m(n) Proof.LetH-(V,E)be an n-unform hypergraph with less than -edges monochomaie P Color V randomly by two colors.For edge e E.let A.be the event that e is Therefore Pr V Ae≤∑Pr[Ac]<I eEe and there is a two-coloring without monochromatic edges. ◆ In Section 3.5 we present a more delicate argument,due to Radhakrishnan and Srinivasan,and based on an idea of Beck,that shows that m≥n()' The best known upper bound to m(n)is found by turing the probabilistic argu- ment"on its head."Basically,the sets become random and each coloring defines an event.Fix V with v points,where we shall later optimize v.Let x be a coloring of V poins inone color,a points in the other.Let SVbean Pr[S is moncchromatic underx) ( Let us assume v is even for convenience.As (is convex,this expression is minimized when a=b.Thus Pr'S is monochromatic under x>p, where we set p=(
COMBINATORIOS 7 1.3 COMBINATORIOS A hypergraph is a pair H = (V,E), where V is a finite set whose elements are called vértices and E is a family of subsets of V, called edges. It is n-uniform if each of its edges contains precisely n vértices. We say that H has property B, or that it is two-colorable if there is a two-coloring of y such that no edge is monochromatic. Let m{n) denote the minimum possible number of edges of an n-uniform hypergraph that does not have property B. Proposition 1.3.1 [Erdos (1963a)] Every n-uniform hypergraph with less than 2n ~ l edges has property B. Therefore m(n) > 2n ~ 1 . Proof. Let H = (V,E) be an n-uniform hypergraph with less than 2 n _ 1 edges. Color V randomly by two colors. For each edge e e E, let Ae be the event that e is monochromatic. Clearly Pr [Ae] = 21_Tl . Therefore Pr \J Ae .eeE <£Pr[Ae ] <l eeE and there is a two-coloring without monochromatic edges. • In Section 3.5 we present a more delicate argument, due to Radhakrishnan and Srinivasan, and based on an idea of Beck, that shows that / / n \ J / 2 The best known upper bound to m(n) is found by turning the probabilistic argument "on its head." Basically, the sets become random and each coloring defines an event. Fix V with v points, where we shall later optimize v. Let x be a coloring of V with a points in one color, b — v — a points in the other. Let S c V be a uniformly selected n-set. Then ( a ) + H Pr [S is monochromatic under x] = /v\ • \n) Let us assume v is even for convenience. As (JQ is convex, this expression is minimized when a = b. Thus Pr [S is monochromatic under x] > P > where we set p o
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
COMBINATORIAL NUMBER THEORY 9 Theorem 1.3.3F=((A,B)is a(ke)-system then h) Proof.Put X =(A:U B:)and consider a random order r of X.For each i, 1ih,let X be the event that all the elements of A precede all those of B:in this order.Clearly Pr=1/().It is also easy to check that the events are pairwise disjoint.Indeed,assume this is false and let be an order in which all the elements of A;precede those of B;and all the elements of A;precede those of B.Without loss of generality we may assume that the last element of A does not appear after the last element of Aj But in this case,all elements of A precede all those of Bj,contradicting the fact that AB0.Therefore all the events Xi are pairwise disjoint,as claimed.It follows that 1≥Px-∑Px1=M(t) completing the proof. ■ Theorem 1.3.3 is sharp,as shown by the familyF=(A,X\A):AC X,A= k,where=(1,2....,k+eh. 1.4 COMBINATORIAL NUMBER THEORY A subset A of an abelian group G is called sum-free if(A+A)A =0;that is.if there are no a1,a2,a3 E A such that a +a2=a3. Theorem 1.4.1 [Erdos (1965a)]Every set B=(b1:...,bn}of n nonzero integers contains a sum-free subset A of size A>n. group Zp and that ICI k+11 p-1=3k+1>3 Let us choose at random an integer,1<<p,according to a uniform distribution on {1,2....,p-11,and define d1,...,dn by di=xbi (mod p),0<di<p. Trivially,for every fixed i,1 <i<n,as ranges over all numbers 1,2,.. p-L,d ranges over all nonzero elements of Zp and hence Prd,C=Cl/(p-1)> Therefore the expected number of elements b;such that di E C is more than n/3. Consequently,there is an x.1 z<p and a subsequence A of B of cardinality lA>n/3,such that za(modp）∈C for all a∈A.This A is clearly sum-free since if a+a2=a3 for some a1,a2,a3 E A then xa ra2 xa3 (mod p contradicting the fact that C is a sum-free subset of Zp.This completes the proof
COMBINATORIA!. NUMBER THEORY 9 h Theorem ;„„iu o\ „„t„m *u„„ h ^ fk+e\ 1.3.3 IfT = {{Ai, £¿)} i = 1 is a (k, l)-system then h < (fc+*). \h Proof. Put X = \Ji=1(Ai U Bi) and consider a random order ir of X. For each i, 1 < i < h, let Xi be the event that all the elements of Ai precede all those of Bi in this order. Clearly Pr [Xi] = l/( £ )• It is also easy to check that the events Xi are pairwise disjoint. Indeed, assume this is false and let n be an order in which all the elements of A¿ precede those of Bi and all the elements of Aj precede those of Bj. Without loss of generality we may assume that the last element of A, does not appear after the last element of Aj. But in this case, all elements of Ai precede all those of Bj, contradicting the fact that Ai n Bj ^ 0. Therefore all the events X¿ are pairwise disjoint, as claimed. It follows that 1 > Pr V * ¿Pr[*] =*/(*£*), completing the proof. Theorem 1.3.3 is sharp, as shown by the family T = {(A, X \ A) : A c X, [A] — k},v/here X = {1,2,... ,k + ¿}. 1.4 COMBINATORIA!. NUMBER THEORY A subset A of an abelian group G is called sum-free if (A + A) n A = 0; that is, if there are no ai, a^, a-¡, € A such that a,\ + ai = a^. Theorem 1.4.1 [Erdós (1965a)] Every set B = {b\,..., bn} ofn nonzero integers contains a sum-free subset A ofsize \A\ > |n . Proof. Let p = 3fc + 2 be a prime, which satisfies p > 2max{¡6¿|}™=1 and put C = {k+ l,k + 2,... ,2k + 1}. Observe that C is a sum-free subset of the cyclic group Zp and that \C\ _ fc + 1 1 p-1 3k + l 3 Let us choose at random an integer x, 1 < x < p, according to a uniform distribution on {1,2,... ,p — 1}, and define di,... ,dn by di = x6¿ (mod p), 0 < d¿ < p. Trivially, for every fixed i, 1 < i < n, as x ranges over all numbers 1,2,... ,p—l,di ranges over all nonzero elements of Zp and henee Pr [d¿ e C] = \C\/{p — 1) > | . Therefore the expected number of elements 6¿ such that di G C is more than n/3. Consequently, there is an x, 1 < x < p and a subsequence A of B of cardinality \A\ > n/3, such that xa (mod p) £ C for all a e A. This A is clearly sum-free, since if ai + Ü2 = a% for some ai, 02,03 £ A then xa\ + xa^ = xa% (mod p), contradicting the fact that C is a sum-free subset of Zp. This completes the proof. •
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}\