GRAPH THEORY > Prv]=Pr(v and its neighbors are not in X](1-p)+.Since the expected value of a sum of random variables is the sum of their expectations (even if they are not independent)and since the random variable IyI can be written as a sum of n indicator random variables vV),where =l if vE Y and=0otherwise. we conclude that the expected value of+Y]is at most np+n(1-p)5+1.Conse- quently,there is at least one choice of X C V such that+Yyl np+n(1-p)5+1 The set U=XUYx is clearly a dominating set of G whos cardinality is at most this size The above elementary calculus hent works for any p o opmize the resu (th nonnegative p and is a fairly close bound when p is small)to give the simpler bound IU≤np+ne6+) Take the derivative of the right-hand side with respect to p and set it equal to zero. The right-hand side is minimized at p=血+) δ+1 Formally,we set p equal to this value in the first line of the proof.We now have as claimed 0+1 Three simple but important ideas are incorporated in the last proof.The first is the linearity of expectation:many applications of this simple.yet powerful principle perhaps more subtle and is an example of the ciple that is discussed in Ch pter3.The ra ndom choice did n the set U im nediatel a little(b ng to j it only supp olied the set which has it the se ed domi ang se The third involves the optim n choic but is not certain what probability p should be used.The idea is to carry out the proo with p as a parameter giving a result that is a function of p.At the end,that p is selected which gives the optimal result.Here,there is yet a fourth idea that might be called asymptotic calculus.We want the asymptotics of min np+n(1-p)5+1,where p ranges over [0.1].The actual minimump=1-(+1)-1/6 is difficult to deal with. and in many similar case s precise minima are impossible to find in a closed form Rathe give away a little bit,bo .1 e-p ieldins a clean bound.A rt of th of the pro d ng su d we give away too much in this case?The answer de pen for the original question.For 6= 3.our rough bound gives s0.5 more precise calculation gives 0.496n,perhaps a substantial difference.For large,both methods give asymptotically n In 6/8. It can easily be deduced from the results in Alon (1990b)that the bound in Theorem 1.2.2 is nearly optimal.A non-probabilistic,algorithmic proof of this theorem can be obtained by choosing the vertices for the dominating set one by
GRAPH THEORY 7 Pr[𝑣 ∈ Y] = Pr[𝑣 and its neighbors are not in X] ≤ (1 − p) 𝛿+1. Since the expected value of a sum of random variables is the sum of their expectations (even if they are not independent) and since the random variable |Y| can be written as a sum of n indicator random variables 𝜒𝑣 (𝑣 ∈ V), where 𝜒𝑣 = 1 if 𝑣 ∈ Y and 𝜒𝑣 = 0 otherwise, we conclude that the expected value of |X| + |Y| is at most np + n(1 − p) 𝛿+1. Consequently, there is at least one choice of X ⊆ V such that |X| + |YX| ≤ np + n(1 − p) 𝛿+1. The set U = X ∪ YX is clearly a dominating set of G whose cardinality is at most this size. The above argument works for any p ∈ [0, 1]. To optimize the result we use elementary calculus. For convenience, we bound 1 − p ≤ e−p (this holds for all nonnegative p and is a fairly close bound when p is small) to give the simpler bound |U| ≤ np + ne−p(𝛿+1) . Take the derivative of the right-hand side with respect to p and set it equal to zero. The right-hand side is minimized at p = ln (𝛿 + 1) 𝛿 + 1 . Formally, we set p equal to this value in the first line of the proof. We now have |U| ≤ n 1 + ln (𝛿 + 1) 𝛿 + 1 , as claimed. ◾ Three simple but important ideas are incorporated in the last proof. The first is the linearity of expectation; many applications of this simple, yet powerful principle appear in Chapter 2. The second is perhaps more subtle and is an example of the “alteration” principle that is discussed in Chapter 3. The random choice did not supply the required dominating set U immediately; it only supplied the set X, which has to be altered a little (by adding to it the set YX) to provide the required dominating set. The third involves the optimal choice of p. One often wants to make a random choice but is not certain what probability p should be used. The idea is to carry out the proof with p as a parameter giving a result that is a function of p. At the end, that p is selected which gives the optimal result. Here, there is yet a fourth idea that might be called asymptotic calculus. We want the asymptotics of min np + n(1 − p) 𝛿+1, where p ranges over [0, 1]. The actual minimum p = 1 − (𝛿 + 1) −1∕𝛿 is difficult to deal with, and in many similar cases precise minima are impossible to find in a closed form. Rather, we give away a little bit, bounding 1 − p ≤ e−p, yielding a clean bound. A good part of the art of the probabilistic method lies in finding suboptimal but clean bounds. Did we give away too much in this case? The answer depends on the emphasis for the original question. For 𝛿 = 3, our rough bound gives |U| ≤ 0.596n, while the more precise calculation gives |U| ≤ 0.496n, perhaps a substantial difference. For 𝛿 large, both methods give asymptotically n ln 𝛿∕𝛿. It can easily be deduced from the results in Alon (1990b) that the bound in Theorem 1.2.2 is nearly optimal. A non-probabilistic, algorithmic proof of this theorem can be obtained by choosing the vertices for the dominating set one by
8 THE BASIC METHOD one,when in each step a vertex that covers the maximum number of yet-uncovered vertices is picked.Indeed,for each vertex v.denote by C(v)the set consisting of v together with all its neighbors.Suppose that during the process of picking vertices the number of vertices u that do not lie in the union of the sets C(v)of the vertices chosen so far is r.By the assumption,the sum of the cardinalities of the sets C() 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 vert tices we ohse ve that the ni nber of unc red vertice is n mo -(+1)/n).It follows that in each ite ation of the vertices dec ses by a factor -(6+1)/man h nln(+1)/6 1)steps,there will be at m ostn/(ò +1)yet uncovered vertic nce aft 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 with some ideas of Poddervugin and Matula.we can obtain a verv efficient algorithm to decide whether a given undirected graph on n vertices is,say. n/3 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=.If vE V and v,V.we say that he cut sepo and v2.The size of the cut is the number of edges of G having e ed Th im: ect of a cut The owing lemma is due to Podderyugin ar nd Mat pe) Lemma 1.2.3 Let G=(V.E)be d a graph with minimum degree 6.and let V=V ut of siz e smaller G The every dominating set Uo ofG has vertices in V and in V2 Proof.Suppose this is false and UV.Choose,arbitrarily,a vertex vV2.and let be 6 of its neighbors.For each,il≤i≤，define an edge of the given cur as foll ,∈Vi,then g.there is tex∈U y∈V,amd such th such aand pute The 6edges el, 6 are all d an edge;take tinct and all lie in the given cut,contradicting the assumption that its size is less than 6.This completes the proof. ■ Let G=(V,E)be a raph on suppose we wish to decide whether Gis n/3e e-com that Is.v r its edge co nectivity is at lea ula show by applying Lemma 1.2.3.that this can be done in time O(n).By the remark following the proof of Theorem 1.2.2,we can slightly improve it and get an O(n/3 log n)algorithm as follows.We first check if the minimum degree of G is at least n/3.If not,G is not n/3 edge-connected,and the algorithm ends.Otherwise,by Theorem 1.2.2,there is a dominating set U =(u. uof G.where k=O(og n) and it can in fact be found in time O(n2).We now find,for eachi,2sisk,the min- imum 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 O(n/)(see,e.g..Tarjan(1983)). m a 1 2 3 the edoe ity of Gis s ly the minir tween 6 and
8 THE BASIC METHOD one, when in each step a vertex that covers the maximum number of yet-uncovered vertices is picked. Indeed, for each vertex 𝑣, denote by C(𝑣) the set consisting of 𝑣 together with all its neighbors. Suppose that during the process of picking vertices the number of vertices u that do not lie in the union of the sets C(𝑣) of the vertices chosen so far is r. By the assumption, 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 𝑣 that belongs to at least r(𝛿 + 1)∕n such sets C(u). Adding this 𝑣 to the set of chosen vertices, we observe that the number of uncovered vertices is now at most r(1 − (𝛿 + 1)∕n). It follows that in each iteration of the above procedure the number of uncovered vertices decreases by a factor of 1 − (𝛿 + 1)∕n and, hence after n ln (𝛿 + 1)∕(𝛿 + 1) steps, there will be at most n∕(𝛿 + 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 with some ideas of Podderyugin and Matula, we can obtain a very efficient algorithm to decide whether a given undirected graph on n vertices is, say, n∕3 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 = V1 ∪ V2. If 𝑣1 ∈ V1 and 𝑣2 ∈ V2, we say that the cut separates 𝑣1 and 𝑣2. The size of the cut is the number of edges of G having one end in V1 and the other end in V2. 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) be a graph with minimum degree 𝛿, and let V = V1 ∪ V2 be a cut of size smaller than 𝛿 in G. Then every dominating set U of G has vertices in V1 and in V2. Proof. Suppose this is false and U ⊆ V1. Choose, arbitrarily, a vertex 𝑣 ∈ V2, and let 𝑣1, 𝑣2, … , 𝑣𝛿 be 𝛿 of its neighbors. For each i, 1 ≤ i ≤ 𝛿, define an edge ei of the given cut as follows: if 𝑣i ∈ V1, then ei = {𝑣, 𝑣i}, otherwise 𝑣i ∈ V2, and since U is dominating, there is at least one vertex u ∈ U such that {u, 𝑣i } is an edge; take such a u and put ei = {u, 𝑣i }. The 𝛿 edges e1, … , e𝛿 are all distinct 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 whether G is n∕3 edge-connected; that is, whether its edge connectivity is at least n∕3. Matula showed, by applying Lemma 1.2.3, that this can be done in time O(n3). 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 𝛿 of G is at least n∕3. If not, G is not n∕3 edge-connected, and the algorithm ends. Otherwise, by Theorem 1.2.2, there is a dominating set U = {u1, … , uk} of G, where k = O(log n), and it can in fact be found in time O(n2). We now find, for each i, 2 ≤ i ≤ k, the minimum size si of a cut that separates u1 from ui . Each of these problems can be solved by solving a standard network flow problem in time O(n8∕3) (see, e.g., Tarjan (1983)). By Lemma 1.2.3, the edge connectivity of G is simply the minimum between 𝛿 and min2≤i≤k si . The total time of the algorithm is O(n8∕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. Let m(n)denote the minimum possible number of edges of an n-uniform hypergraph that does not have property B. Proof.LetH=(V,E)be ann-uniformhypergraph with less than 2edges.Color rando omly by tw co edge ee let A.be the event such that e is monochromatic.Clearly,Pr[A ]=21-".Therefore, Pm&As∑PmA,I<I and there is a two-coloring without monochromatic edges ◆ In Section 3.6 we present a more delicate argument.due to Cherkashin and Kozik (2015).which shows that m≥(（品）x) Thebest known upper boundto)is foundby ting the probabilistic argument the sets be here we shall later opi ning of points in one in the other n-set.Then ()+() Pr[S is monochromatic under]= () Let usassumeiseven for convenience.Asis convexthis expression is mini- mized when a=b.Thus Pr[S is monochromatic under>p. where we set 2(2） p=
COMBINATORICS 9 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. 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−1 edges has property B. Therefore m(n) ≥ 2n−1. Proof. Let H = (V, E) be an n-uniform hypergraph with less than 2n−1 edges. Color V randomly by two colors. For each edge e ∈ E, let Ae be the event such that e is monochromatic. Clearly, Pr[Ae] = 21−n. Therefore, Pr [ ∨ e∈E Ae ] ≤ ∑ e∈E Pr[Ae] < 1 and there is a two-coloring without monochromatic edges. ◾ In Section 3.6 we present a more delicate argument, due to Cherkashin and Kozik (2015), which shows that m(n) ≥ Ω (( n ln n )1∕2 2n ) . 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 𝑣 points, where we shall later optimize 𝑣. Let 𝜒 be a coloring of V with a points in one color, b = 𝑣 − a points in the other. Let S ⊂ V be a uniformly selected n-set. Then Pr[S is monochromatic under 𝜒] = (a n ) + (b n ) (𝑣 n ) . Let us assume 𝑣 is even for convenience. As (y n ) is convex, this expression is minimized when a = b. Thus Pr[S is monochromatic under𝜒] ≥ p, where we set p = 2 (𝑣∕2 n ) (𝑣 n )
10 THE BASIC METHOD for notational convenience.Now let S1.....S be uniformly and independently chosen n-sets,with m to be determined.For each coloring z.let A,be the event in which none of the S is monochromatic.By the independence of the S Pr[A,J≤(1-p)m There are 2colorings,so P,s2u-p. When this quantity is less than 1,there exist S ...S so that no A holds:that is. 兴 S1. colorable and her vide a fairly ole of those encou red wher .This is 快 then 2(1-pym<2e-pmsI so m(n)sm.Now we need to find e 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 esti- mate p by 2-+,the probability for sampling with replacement.This approximation would yield m~v2"-1(In 2).As vgets smaller,however,the approximation becomes less accurate and,as we wish to minimize m.the tradeoff becomes essential.We use a second-order approximation p= () as long as,estimating =1-+() -i =e-/e+o Elementary calculus gives =n2/2 for the optimal value.The evenness of may require a change of at most 2,which turns out to be asymptotically negligible.This yields the following result of Erdos(1964): Theorem 1.3.2 m(n)<(1+(1))In 2n2 4 Let =((A:.B )be a family of pairs of set Wecall fa k,f)-system if A,l=kand |B,l=for al1≤i≤h,A,nB=,nB,≠gfo
10 THE BASIC METHOD for notational convenience. Now let S1, … , Sm be uniformly and independently chosen n-sets, with m to be determined. For each coloring 𝜒, let A𝜒 be the event in which none of the Si is monochromatic. By the independence of the Si Pr[A𝜒 ] ≤ (1 − p) m. There are 2𝑣 colorings, so Pr [ ∨ 𝜒 A𝜒 ] ≤ 2𝑣(1 − p) m. When this quantity is less than 1, there exist S1, … , Sm so that no A𝜒 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 inequality 1 − p ≤ e−p. This is valid for all positive p, and the terms are quite close when p is small. When m = ⌈ 𝑣 ln 2 p ⌉ , then 2𝑣(1 − p) m < 2𝑣e−pm ≤ 1 so m(n) ≤ m. Now we need to find 𝑣 to minimize 𝑣∕p. We may interpret p as twice the probability of picking n white balls from an urn with 𝑣∕2 white and 𝑣∕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 ∼ 𝑣2n−1(ln 2). As 𝑣 gets smaller, however,the approximation becomes less accurate and, as we wish to minimize m, the tradeoff becomes essential. We use a second-order approximation p = 2 (𝑣∕2 n ) (𝑣 n ) = 21−n∏n−1 i=0 𝑣 − 2i 𝑣 − i ∼ 21−ne−n2∕2𝑣 as long as 𝑣 ≫ n3∕2, estimating 𝑣 − 2i 𝑣 − i = 1 − i 𝑣 + O ( i 2 𝑣2 ) = e−i∕𝑣+O(i 2∕𝑣2) . Elementary calculus gives 𝑣 = n2∕2 for the optimal value. The evenness of 𝑣 may require a change of at most 2, which turns out to be asymptotically negligible. This yields the following result of Erdos (1964): ˝ Theorem 1.3.2 m(n) < (1 + o(1)) e ln 2 4 n22n. Let = {(Ai, Bi)}h i=1 be a family of pairs of subsets of an arbitrary set. We call a (k, 𝓁)-system if |Ai | = k and |Bi | = 𝓁 for all 1 ≤ i ≤ h, Ai ∩ Bi = ∅ and Ai ∩ Bj ≠ ∅ for
COMBINATORIAL NUMBER THEORY 11 all distinct i.j.with 1i.(1965)proved the following result,which has many interesting extensions and applications: Theorem 13.3fF=fa,B,A1sak,)system thenh≤(） Proof.PutX=(A;UB:)and consider arandomorder of X.Foreachi,1 sis h,let X;be the event that all the elements of A;precede all those of B,in this order. Clearly,Pr1/).It is also easy to check that the eventsare 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 ofA:.But in this case,all elements of A;precede all those of B:.contradicting the fact thatAB.Therefore,all the events are pairwise disjoint.as claimed. It follows that 12-2m1=M() completing the proof. ◆ Theorem 1.3.3 is sharp.as shown by the family =((A.X\A)A C X.IAl k),where=(1,2....). 1.4 COMBINATORIAL NUMBER THEORY A subset Aof an abelian group Gis called sum-free if (A+A)is,if there are no a,a.a3 E A such that a +a a3. Theorem 1.4.1 [Erdos (1965a)]Every set B=(b.....b)ofn nonzero integers contains a sum-free subset A of size Al>in. Proof.Letp =3k+2 be a prime that satisfies p>2maxisisnlbl,and put C=(k+ 1,k+2.....k+1).Observe that C is a sum-free subset of the cyclic group Z and that Let us choose at random an integerx,1x<p,according to a uniform distribu tion on(1,2. -1)and defin everyed.ss di..dn by p,0≤d,<p.Ti ially,for 1 P d;ranges over all nonzeroelemer ts of Zp.and hence Prld;E C]=ICl/(p-1)> the expected number of elements b;such that d,E Cis more than n/3.Consequently, there is anx,1 sx<p,and a subsequence A of B of cardinality Al >n/3,such that xa(mod p)E C for all a EA.This A is clearly sum-free,since,if a+a2=as for some a.a,a EA,then xa+xa2=xaa(mod p).contradicting the fact that C is a sum-free subset ofZ.This completes the proof. ■
COMBINATORIAL NUMBER THEORY 11 all distinct i, j, with 1 ≤ i, j ≤ h. Bollobás (1965) proved the following result, which has many interesting extensions and applications: Theorem 1.3.3 If = {(Ai , Bi )}h i=1 is a (k, 𝓁)-system then h ≤ (k+𝓁 k ) . Proof. Put X = ⋃h i=1(Ai ∪ Bi) and consider a random order 𝜋 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 ] = 1∕ (k+𝓁 k ) . It is also easy to check that the events Xi are pairwise disjoint. Indeed, assume this is false, and let 𝜋 be an order in which all the elements of Ai 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 Ai 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 ∩ Bj ≠ ∅. Therefore, all the events Xi are pairwise disjoint, as claimed. It follows that 1 ≥ Pr [ h ∨ i=1 Xi ] = ∑ h i=1 Pr[Xi ] = h / (k + 𝓁 k ) , completing the proof. ◾ Theorem 1.3.3 is sharp, as shown by the family = {(A, X ⧵ A) ∶ A ⊂ X, |A| = k}, where X = {1, 2, … , k + 𝓁}. 1.4 COMBINATORIAL NUMBER THEORY A subset A of an abelian group G is called sum-free if (A + A) ∩ A = ∅, that is, if there are no a1, a2, a3 ∈ A such that a1 + 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| > 1 3 n. Proof. Let p = 3k + 2 be a prime that satisfies p > 2max1≤i≤n|bi |, and put C = {k + 1, k + 2, … , 2k + 1}. Observe that C is a sum-free subset of the cyclic group Zp and that |C| p − 1 = k + 1 3k + 1 > 1 3 . Let us choose at random an integer x, 1 ≤ x < p, according to a uniform distribution on {1, 2, … , p − 1}, and define d1, … , dn by di ≡ xbi(mod p), 0 ≤ di < p. Trivially, for every fixed i, 1 ≤ i ≤ n, as x ranges over all numbers 1, 2, … , p − 1, di ranges over all nonzero elements of Zp, and hence Pr[di ∈ C] = |C|∕(p − 1) > 1 3 . Therefore, the expected number of elements bi such that di ∈ 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 ∈ A. This A is clearly sum-free, since, if a1 + a2 = a3 for some a1, a2, a3 ∈ A, then xa1 + xa2 ≡ xa3(mod p), contradicting the fact that C is a sum-free subset of Zp. This completes the proof. ◾