12 THE BASIC METHOD Remark.The above proof works wheneverp is a prime that does not divide any of the numbers b.This can be used to design an efficient deterministic algorithm for finding a sum-free subset A of size bigger than |Bl/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 the best possible.For quite some time it was not clear whether or not m1.4.1ca eplaced by a la rge Eberhard.G reen an lem of deciding whether or not every set of n nonzero integers contains a sum-free subset of cardinality at least n/3 +w(n).where w(n)tends to infinity with n,remains open.It will be very surprising if there is no such w(n). 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 Alon and Frankl (1985).which solve es a onject re of Daykin mily of m subsets of=(1.2......Let d(F)denote the d(F)=FF')F.F'EF,FnF'=0) Daykin and [Erdos]conjectured that,if mthen for every fixed0 d()=o(m).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 afamily ofm=+6m subsets of=(1.2.....n.where 6>0.Then d(T)<m2-22 (1.10 A.of P with Proof.Suppose (1.D)is false:pick independently r members A.. s a l to be A1 UA2 nt to more than2 UAl n/2 and st stinct subsets of X.This contradiction will establish(1.1). In fact, P[lAUA2UUA,l≤n/2] Pr[A cS.i=1...... ≤2(2/2/21/2+my=2n1-6 (1.2)
12 THE BASIC METHOD Remark. The above proof works whenever p is a prime that does not divide any of the numbers bi . 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 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 the best possible. For quite some time it was not clear whether or not the constant 1∕3 in Theorem 1.4.1 can be replaced by a larger constant, until Eberhard, Green and Manners (2013) proved that the constant 1∕3 is tight. The problem of deciding whether or not every set of n nonzero integers contains a sum-free subset of cardinality at least n∕3 + 𝑤(n), where 𝑤(n) tends to infinity with n, remains open. It will be very surprising if there is no such 𝑤(n). 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 Alon and Frankl (1985), which solves a conjecture of Daykin and Erdos. ˝ Let be a family of m distinct subsets of X = {1, 2, … , n}. Let d() denote the number of disjoint pairs in , that is d() = |{{F, F′ } ∶ F, F′ ∈ , F ∩ F′ = ∅}|. Daykin and [Erdos] conjectured that, if ˝ m = 2(1∕2+𝛿)n, then for every fixed 𝛿 > 0, d() = 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 be a family of m = 2(1∕2+𝛿)n subsets of X = {1, 2, … , n}, where 𝛿 > 0. Then d() < m2−𝛿2∕2. (1.1) Proof. Suppose (1.1) is false; pick independently t members A1, A2, … , At of with repetitions at random, where t is a large positive integer, to be chosen later. We will show that with positive probability |A1 ∪ A2 ∪···∪ At | > n∕2 and still this union is disjoint to more than 2n∕2 distinct subsets of X. This contradiction will establish (1.1). In fact, Pr[|A1 ∪ A2 ∪···∪ At | ≤ n∕2] ≤ ∑ S⊂X,|S|=n∕2 Pr[Ai ⊂ S, i = 1, … , t] ≤ 2n(2n∕2∕2(1∕2+𝛿)n) t = 2n(1−𝛿t) . (1.2)
INDEPENDENT SETS AND LIST COLORING Define (B)=I(A∈F:BnA=l. Clearly, 昌国=24≥2m Let Y be a random variable whose value is the number of members B E F that are disjoint to all theA,(I sist).By the convexity ofz.the expected value of y satisfies m=(2)-京m(②） BEP ≥左(2)≥2mn Since Ym,we conclude that PmY≥m-6A乃]≥m6p. (1.3) One cancheck that,fort=[1+1/],m>22and the right-hand side of (1.3) is greater than the right-hand side of(1.2).Thus,with positive probability.A UA,U ...A >n/2 and still this union is disjoint to more than 2n/2 members of F.This 1.6 INDEPENDENT SETS AND LIST COLORING Containers A recent powe erful method has been devel loped inde ntly by Saxton and Thomason(2012)and by Balogh,M orris and Samotij (2014).This method sup- plies a structural characterization of the independent sets in uniform hypergraphs satisfying certain natural conditions,by showing that in such hypergraphs every independent set is almost fully contained in one of a small number of sparse sets (called containers).This general result leads to many interesting consequences including sparse random analogs of several classical results like Szemeredi's theorem and Tura em.The hod is h technical:here the approa ch dea ng w vith i ndepen regula e one interesting application to a seen ngly unrelate problem.Many additional applications can be found in Saxton and Thomason (2012) and in Balogh et al.(2014). The basic approach for regular graphs has been discovered earlier by several researchers,most notably by Sapozhenko (2001).We proceed with the statement and its short proof
INDEPENDENT SETS AND LIST COLORING 13 Define 𝑣(B) = |{A ∈ ∶ B ∩ A = ∅}|. Clearly, ∑ B∈ 𝑣(B) = 2d() ≥ 2m2−𝛿2∕2. Let Y be a random variable whose value is the number of members B ∈ that are disjoint to all the Ai (1 ≤ i ≤ t). By the convexity ofzt , the expected value of Y satisfies E[Y] = ∑ B∈ (𝑣(B) m )t = 1 mt ⋅ m (∑ 𝑣(B) t m ) ≥ 1 mt ⋅ m (2d() m )t ≥ 2m1−t𝛿2∕2 . Since Y ≤ m, we conclude that Pr[Y ≥ m1−t𝛿2∕2] ≥ m−t𝛿2∕2. (1.3) One can check that, fort = ⌈1 + 1∕𝛿⌉, m1−t𝛿2∕2 > 2n∕2 and the right-hand side of (1.3) is greater than the right-hand side of (1.2). Thus, with positive probability, |A1 ∪ A2 ∪ ···∪ At| > n∕2 and still this union is disjoint to more than 2n∕2 members of F. This contradiction implies inequality (1.1). ◾ 1.6 INDEPENDENT SETS AND LIST COLORING Containers A recent powerful method has been developed independently by Saxton and Thomason (2012) and by Balogh, Morris and Samotij (2014). This method supplies a structural characterization of the independent sets in uniform hypergraphs satisfying certain natural conditions, by showing that in such hypergraphs every independent set is almost fully contained in one of a small number of sparse sets (called containers). This general result leads to many interesting consequences including sparse random analogs of several classical results like Szemerédi’s theorem and Turán’s theorem. The method is elementary but somewhat technical; here we only present the basic approach dealing with independent sets in regular graphs, and describe one interesting application to a seemingly unrelated graph coloring problem. Many additional applications can be found in Saxton and Thomason (2012) and in Balogh et al. (2014). The basic approach for regular graphs has been discovered earlier by several researchers, most notably by Sapozhenko (2001). We proceed with the statement and its short proof
14 THE BASIC METHOD Theorem 1.6.1 Let G=(V,E)be a d-regular graph on n vertices,and lete>be a positive real.Then there is a collection C of subsets of V.so that 1qs∑() isn/(ed) each CEC is of size at most+ and every independent set in G is fully con- tained in a member CEC.Moreover.for each C C.the degree ofeach vertexv E C in the induced subgraph of G on C is at most ed. Proof.Let S be an independent set in G.Define a set C containing S as follows Starting with T=d as lor gas there is a vertex so that N( 二N(I add it to T.Her N(o the set of all neighbors of an nd N(T)is s the set of al neighbors of vertices in T.Note that T may depend on the order in which the vertices of S are inspected,but for our purpose here any order will do.This process clearly ends with a subset T C S,where ITI s"as each addition of a vertex to T increases IN(T)I by at least ed.Moreover,each vertex vE S-T has at least(1-e)d neighbors in N(T).Let B(T)denote the set of all vertices vV-(TUN(T))that have at least (1-e)d neighbors in N(T).Note that,crucially,B(T)is determined by T.Define C=TUB(T).By the discussion aboveScC.every vertex ofT has no neighbors in C.ad x in C-T has at most ed nei in C.Since C-T=B(T)is ntain V(T n-IN(T)I. at least(1-e)d neighbors in N(T),it follows that |B(T)s w出of Taking a convex combination of the above two bounds,we conclude that IBD1≤2是a-1wD+=eN 2-e1-e ,二2-e List Coloring chromatic number (or choice number)(G)of a graph Ga um in er k such th for of G.there is aproper tex c o ich th e col ofea This noti n wa introduced independently by V (and by and Taylor(1980).In both papers,the authors realized that this is a variant of usua coloring that exhibits several new interesting properties,and that in general (G). which is always at least as large as the chromatic number of G.may be arbitrarily large even for graphs G of chromatic number 2. An intriguing property of list coloring of graphs.which is not shared by ordinary vertex coloring,is the fact that the list chromatic number of anyg ge deg is lar e Indeed it is shov ( roma mumber of any graph with average degreed is at least Here we present a
14 THE BASIC METHOD Theorem 1.6.1 Let G = (V, E) be a d-regular graph on n vertices, and let 𝜖 > 0 be a positive real. Then there is a collection of subsets of V, so that || ≤ ∑ i≤n∕(𝜖d) (n i ) each C ∈ is of size at most n 𝜖d + n 2−𝜖 , and every independent set in G is fully contained in a member C ∈ . Moreover, for each C ∈ , the degree of each vertex 𝑣 ∈ C in the induced subgraph of G on C is at most 𝜖d. Proof. Let S be an independent set in G. Define a set C containing S as follows: Starting with T = ∅, as long as there is a vertex 𝑣 ∈ S so that |N(𝑣) − N(T)| ≥ 𝜖d, add it to T. Here, N(𝑣) is the set of all neighbors of 𝑣, and N(T) is the set of all neighbors of vertices in T. Note that T may depend on the order in which the vertices of S are inspected, but for our purpose here any order will do. This process clearly ends with a subset T ⊂ S, where |T| ≤ n 𝜖d as each addition of a vertex to T increases |N(T)| by at least 𝜖d. Moreover, each vertex 𝑣 ∈ S − T has at least (1 − 𝜖)d neighbors in N(T). Let B(T) denote the set of all vertices 𝑣 ∈ V − (T ∪ N(T)) that have at least (1 − 𝜖)d neighbors in N(T). Note that, crucially, B(T) is determined by T. Define C = T ∪ B(T). By the discussion above S ⊂ C, every vertex of T has no neighbors in C, and every vertex in C − T has at most 𝜖d neighbors in C. Since C − T = B(T) is contained in V − N(T), its size is at most n − |N(T)|, and as each of its vertices has at least (1 − 𝜖)d neighbors in N(T), it follows that |B(T)| ≤ |N(T)d| (1−𝜖)d = |N(T)| 1−𝜖 . Taking a convex combination of the above two bounds, we conclude that |B(T)| ≤ 1 2 − 𝜖 (n − |N(T)|) + 1 − 𝜖 2 − 𝜖 |N(T)| 1 − 𝜖 = n 2 − 𝜖 . The set of containers can thus be defined as the collection of all sets T ∪ B(T), where T is an independent set of size at most n 𝜖d in G. ◾ List Coloring The list chromatic number (or choice number) 𝜒𝓁(G) of a graph G = (V, E) is the minimum integer k such that, for every assignment of a list of k colors to each vertex 𝑣 of G, there is a proper vertex coloring of G in which the color of each vertex is in its list. This notion was introduced independently by Vizing (1976) and by Erdos, Rubin ˝ and Taylor (1980). In both papers, the authors realized that this is a variant of usual coloring that exhibits several new interesting properties, and that in general 𝜒𝓁(G), which is always at least as large as the chromatic number of G, may be arbitrarily large even for graphs G of chromatic number 2. An intriguing property of list coloring of graphs, which is not shared by ordinary vertex coloring, is the fact that the list chromatic number of any graph with a large average degree is large. Indeed, it is shown in Alon (2000) that the list chromatic number of any graph with average degree d is at least Ω(log d). Here we present a
INDEPENDENT SETS AND LIST COLORING 15 short proof of this result for regular g bound for th er in terms of the de with some additional work.to nonregular graphs as well,but for simplicity we restrict the description to regular graphs. Theorem 1.6.2 Let d>k>2 be integers satisfying H(g)<-(+a)(点ee (1.4) where H(x)=-xlogx-(1-x)log(1-x)is the binary entropy fiunction and all log arithms are in base2.Then the choice mumber of any d-regula grap exceeds k Therefore,there exists an absolute positive constant c so that,ifdzckk then the choice number of any d-regular graph exceeds k. Proof.Let G=(V,E)be a d-regular graph on n vertices,and let k be an integer so that (1.4)holds.Fix a set K=(1.2.....2)of k2 colors and assign to each vertex V,randomly and independently.a subset L of cardinalityk chosen uniformly ets of K.We clai that.w th there is n ch vertex KD a c from ns To prove thi ound,it suffices to show that the probability that there are k2inde pendent sets S.S2.....Sg2 in G so that for each vertex e there is an independent set S;satisfying v S;and iL is smaller than 1.Indeed,in any proper coloring,the set S;of all vertices colored i forms an independent set,and if the color i of a vertex vbelongs to its list L,then we must have vS;and iL.However,the number of independent sets in G may well be too large for using the union bound,hence we replace the independent sets by the containers described above.by Theorem 16.1 e=1/logd.there is a family Cof at most subsets C of V,each of size at most n 4 )<n(+ 个pdlly contained in at least one五ume iog)so that anv vthat,with ity,for any ch ice of containers ere is a verte v so that v is not contained in C;for any i e L,..As the number of conta iners is much smaller than the total number of independent sets,this can be proved by the union bound.The details follow.There are IC ways to choose the containers C.....C Fix such a choice and note that,since each container is small,so is their average size. implving that the average.over the vertices v.number of containers C.that contain v is at most2+).Let k denote the number of containers Csuch that C and let=kbe its average over the vertices v.The probability that the listL of v does not contain any index so that ue C.i exactly
INDEPENDENT SETS AND LIST COLORING 15 short proof of this result for regular graphs, using the notion of containers. This proof appears in Saxton and Thomason (2012) and provides an asymptotically sharp lower bound for the choice number in terms of the degree of regularity. It can be extended, with some additional work, to nonregular graphs as well, but for simplicity we restrict the description to regular graphs. Theorem 1.6.2 Let d > k > 2 be integers satisfying k2 ⋅ H (log d d ) < [ 1 − (1 2 + 1 log d ) ( k k − 1 )]k log e, (1.4) where H(x)=−x log x − (1 − x) log(1 − x) is the binary entropy function and all logarithms are in base 2. Then the choice number of any d-regular graph exceeds k. Therefore, there exists an absolute positive constant c so that, if d ≥ ck42k, then the choice number of any d-regular graph exceeds k. Proof. Let G = (V, E) be a d-regular graph on n vertices, and let k be an integer so that (1.4) holds. Fix a set K = {1, 2, … , k2} of k2 colors and assign to each vertex 𝑣 ∈ V, randomly and independently, a subset L𝑣 of cardinality k chosen uniformly among all k-subsets of K. We claim that, with positive probability, there is no proper coloring of G assigning to each vertex 𝑣 a color from its list L𝑣. To prove this claim using the union bound, it suffices to show that the probability that there are k2 independent sets S1, S2, … , Sk2 in G so that for each vertex 𝑣 there is an independent set Si satisfying 𝑣 ∈ Si and i ∈ L𝑣 is smaller than 1. Indeed, in any proper coloring, the set Si of all vertices colored i forms an independent set, and if the color i of a vertex 𝑣 belongs to its list L𝑣, then we must have 𝑣 ∈ Si and i ∈ L𝑣. However, the number of independent sets in G may well be too large for using the union bound, hence we replace the independent sets by the containers described above. By Theorem 1.6.1 with 𝜖 = 1∕ log d, there is a family of at most ∑ i≤n log d∕d (n i ) ≤ 2H(log d∕d)n subsets C of V, each of size at most n (log d d + 1 2−1∕ log d ) < n ( 1 2 + 1 log d ) so that any independent set is fully contained in at least one of them. It suffices to show that, with positive probability, for any choice of k2 containers C1, C2, … , Ck2 , there is a vertex 𝑣 so that 𝑣 is not contained in Ci for any i ∈ L𝑣. As the number of containers is much smaller than the total number of independent sets, this can be proved by the union bound. The details follow. There are || k2 ways to choose the containers C1, … , Ck2 . Fix such a choice and note that, since each container is small, so is their average size, implying that the average, over the vertices 𝑣, number of containers Ci that contain 𝑣 is at most k2 ( 1 2 + 1 log d ) . Let k𝑣 denote the number of containers Ci such that 𝑣 ∈ Ci , and let k = 1 n ∑ 𝑣k𝑣 be its average over the vertices 𝑣. The probability that the list L𝑣 of 𝑣 does not contain any index i so that 𝑣 ∈ Ci is exactly
16 THE BASIC METHOD ≥gk where the function g(z)is defined by g(a)= =-立)》 and by g(2)=0 fork.It follows that the bove ixed choice of cotainer for ac vereter for the vE C,is at most Π1-gk,】≤e2.s Since the function g()is convex for all 0.it follows by Jensen's inequality tha >g(k)>ng(k),and thus the probability that the random lists do yield a proper coloring by color classes contained in the fixed set of containers above is at most eg而.Since()is non--increasing and灭≤k2g+it follows that 2-k-2(传+) g≥ k2-k -(传*)点 and the above probability is at most e-(+) coprobability multiplied by the number of choices of a sequence of By(1.4),this 22(g） is smaller than 1,and the union bound completes the proof. ■ L7 EXERCISES 1.Prove that,if there is a real p,sp1 such that ()n+()a-m)< then the Ramsey number R(k,t)satisfies R(k,t)>n.Using this,show that R4,0≥2rP/m032
16 THE BASIC METHOD ( k2−k𝑣 k ) ( k2 k ) ≥ g(k𝑣), where the function g(z) is defined by g(z) = [ k2 − k − z k2 − k ]k = ( 1 − z k2 − k )k for 0 ≤ z < k2 − k and by g(z) = 0 for z ≥ k2 − k. It follows that the probability that, for the above fixed choice of containers, for each vertex 𝑣 there is an i ∈ L𝑣 with 𝑣 ∈ Ci, is at most ∏ 𝑣 [1 − g(k𝑣)] ≤ e− ∑ 𝑣g(k𝑣) . Since the function g(z) is convex for all z ≥ 0, it follows by Jensen’s inequality that ∑ 𝑣g(k𝑣) ≥ ng(k), and thus the probability that the random lists do yield a proper coloring by color classes contained in the fixed set of containers above is at most e−ng(k) . Since g(z) is non-increasing and k ≤ k2( 1 2 + 1 log d ), it follows that g(k) ≥ ⎡ ⎢ ⎢ ⎢ ⎣ k2 − k − k2 (1 2 + 1 log d ) k2 − k ⎤ ⎥ ⎥ ⎥ ⎦ k = [ 1 − (1 2 + 1 log d ) k k − 1 ]k and the above probability is at most e −n [ 1− ( 1 2+ 1 log d ) k k−1 ]k . By (1.4), this probability multiplied by the number of choices of a sequence of k2 containers, which is at most 2 k2H ( log d d ) , is smaller than 1, and the union bound completes the proof. ◾ 1.7 EXERCISES 1. Prove that, if there is a real p, 0 ≤ p ≤ 1 such that (n k ) p ( k 2 ) + (n t ) (1 − p) ( t 2 ) < 1, then the Ramsey number R(k, t) satisfies R(k, t) > n. Using this, show that R(4, t) ≥ Ω(t 3∕2∕(ln t) 3∕2)