Alterations

3 3.1 Alterations Ramsey numbers Recall from Section 1.1: R(s, t) = smallest n such that every red/blue edge coloring of Kn contains a red Ks or a blue Kt Using the basic method (union bounds), we deduce Theorem 3.1.1. If there exists p ∈ [0, 1] with     t n n (2s) (1 − p)(2) < 1 p + t s then R(s, t) > n. Proof sketch. Color edge red with prob p and blue with prob 1 − p. LHS upper bounds the probability of a red Ks or a blue Kt . Using the alteration method, we deduce Theorem 3.1.2. For all p ∈ [0, 1] and n,     t n (2s) n R(s, t) > n − p − (1 − p)(2) s t Proof sketch. Color edge red with prob p and blue with prob 1−p remove one vertex from each red Ks or blue Kt . RHS lower bounds the expected number remaining vertices. 3.2 Dominating set in graphs In a graph G = (V, E), we say that U ⊂ V is dominating if every vertex in V \ U has a neighbor in U . Theorem 3.2.1. Every graphon n vertices with minimum degree δ > 1 has a dominating  log(δ+1)+1 set of size at most n. δ+1 Naive attempt: take out vertices greedily. The first vertex eliminates 1 + δ vertices, but subsequent vertices eliminate possibly fewer vertices. Proof. Two-step process (alteration method): 1. Choose a random subset 2. Add enough vertices to make it dominating Let p ∈ [0, 1] to be decided later. Let X be a random subset of V where every vertex is included with probability p independently. Let Y = V \ (X ∪ N (X)). Each v ∈ V lies in Y with probability ≤ (1 − p)1+δ . Then X ∪ Y is dominating, and E[|X ∪ Y |] = E[|X|] + E[|Y |] ≤ pn + (1 − p)1+δ n ≤ (p + e−p(1+δ) )n using 1 + x ≤ ex for all x ∈ R. Finally, setting p = log(δ+1) to minimize p + e−p(1+δ) , we δ+1 bound the above expression by   1 + log(δ + 1) ≤ . δ+1 3.3 Heilbronn triangle problem Question 3.3.1. How can one place n points in the unit square so that no three points forms a triangle with small area? Let ∆(n) = sup min area(pqr) S⊂[0,1]2 p,q,r∈S distinct |S|=n Naive constructions fair poorly. E.g., n points around a circle has a triangle of area Θ(1/n3 ) (the triangle formed by three consectutive points has side lengths  1/n and angle θ = (1 − 1/n)2π). Even worse is arranging points on a grid, as you would get triangles of zero area. Heilbronn conjectured that ∆(n) = O(n−2 ). Komlós, Pintz, and Szemerédi (1982) disproved the conjecture, showing ∆(n) & n−2 log n. They used an elaborate probabilistic construction. Here we show a much simpler version probabilistic construction that gives a weaker bound ∆(n) & n−2 . Remark 3.3.2. The currently best upper bound known is ∆(n) ≤ n−8/7+o(1) (Komlós, Pintz, and Szemerédi 1981) Theorem 3.3.3. For every positive integer n, there exists a set of n points in [0, 1]2 such that every triple spans a triangle of area ≥ cn−2 , for some absolute constant c > 0. Proof. Choose 2n points at random. For every three random points p, q, r, let us estimate Pp,q,r (area(p, q, r) ≤ ). By considering the area of a circular annulus around p, with inner and outer radii x and x + ∆x, we find Pp,q (|pq| ∈ [x, x + ∆x]) ≤ π((x + ∆x)2 − x2 ) So the probability density function satisfies Pp,q (|pq| ∈ [x, x + dx]) ≤ 2πxdx For fixed p, q    2 . Pr (area(pqr) ≤ ) = Pr dist(pq, r) ≤ |pq| |pq| Thus, with p, q, r at random √ Z Pp,q,r (area(pqr) ≤ ) . 0 2  2πx dx  . x Given these 2n random points, let X be the number of triangles with area ≤ . Then EX = O(n3 ). Choose  = c/n2 with c > 0 small enough so that EX ≤ n. Delete a point from each triangle with area ≤ . The expected number of remaining points is E[2n − X] ≥ n, and no triangles with area ≤  = c/n2 . Thus with positive probability, we end up with ≥ n points and no triangle with area ≤ c/n2 . Algebraic construction. Here is another construction due to Erdős (in appendix of Roth (1951)) also giving ∆(n) & n−2 : Let p be a prime. The set {(x, x2 ) ∈ F2p : x ∈ Fp } has no 3 points collinear (a parabola meets every line in ≤ 2 points). Take the corresponding set of p points in [p]2 ⊂ Z2 . Then every triangle has area ≥ 1/2 due to Pick’s theorem. Scale back down to a unit square. (If n is not a prime, then use that there is a prime between n and 2n.) 3.4 Markov’s inequality We note an important tool that will be used next. Markov’s inequality. Let X ≥ 0 be random variable. Then for every a > 0, P(X ≥ a) ≤ E[X] . a Proof. E[X] ≥ E[X1X≥a ] ≥ E[a1X≥a ] = aP(X ≥ a) Take-home message: for r.v. X ≥ 0, if EX is very small, then typically X is small. 3.5 High girth and high chromatic number If a graph has a k-clique, then you know that its chromatic number is at least k. Conversely, if a graph has high chromatic number, is it always possible to certify this fact from some “local information”? Surprisingly, the answer is no. The following ingenious construction shows that a graph can be “locally tree-like” while still having high chromatic number. The girth of a graph is the length of its shortest cycle. Theorem 3.5.1 (Erdős 1959). For all k, `, there exists a graph with girth > ` and chromatic number > k. Proof. Let G ∼ G(n, p) with p = (log n)2 /n (the proof works whenever log n/n  p  n−1+1/` ). Here G(n, p) is Erdős–Rényi random graph (n vertices, every edge appearing with probability p independently). Let X be the number of cycles of length at most ` in G. By linearity of expectations, as
there are exactly ni (i − 1)!/2 cycles of length i in Kn for each 3 ≤ i ≤ n, we have (recall that ` is a constant) EX = `   X n (i − 1)! i=3 i 2 i p ≤ ` X ni pi = o(n). i=3 By Markov’s inequality P(X ≥ n/2) ≤ EX = o(1). n/2 (This allows us to get rid of all short cycles.) How can we lower bound the chromatic number χ(·)? Note that χ(G) ≥ |V (G)|/α(G), where α(G) is the independence number (the size of the largest independent set). With x = (3/p) log n,   x n P(α(G) ≥ x) ≤ (1 − p)(2) < nx e−px(x−1)/2 = (ne−p(x−1)/2 )x = o(1). x Let n be large enough so that P(X ≥ n/2) < 1/2 and P(α(G) ≥ x) < 1/2. Then there is some G with fewer than n/2 cycles of length ≤ ` and with α(G) ≤ (3/p) log n. Remove a vertex from each cycle to get G0 . Then |V (G0 )| ≥ n/2, girth > `, and α(G0 ) ≤ α(G) ≤ (3/p) log n, so χ(G0 ) ≥ |V (G0 )| np log n ≥ = >k 0 α(G ) 6 log n 6 if n is sufficiently large. Remark 3.5.2. Erdős (1962) also showed that in fact one needs to see at least a linear number of vertices to deduce high chromatic number: for all k, there exists  = k such that for all sufficiently large n there exists an n-vertex graph with chromatic number > k but every subgraph on bnc vertices is 3-colorable. (In fact, one can take G ∼ G(n, C/n); see "Probabilistic Lens: Local coloring" in Alon–Spencer) 3.6 Greedy random coloring Recall m(k) is the minimum number of edges in a k-uniform hypergraph that is not 2-colorable. Earlier we proved that m(k) ≥ 2k−1 . Indeed, given a k-graph with < 2k−1 edges, by randomly coloring the vertices, the expected number of monochromatic numbers is < 1. We also proved an upper bound m(k) = O(k 2 2k ) by taking a random k-uniform hypergraph on k 2 vertices. Here is the currently best known lower bound. Theorem 3.6.1 (Radhakrishnan and Srinivasan (2000)). m(k) & q k 2k log k Here we present a simpler proof, based on a random greedy coloring, due to Cherkashin and Kozik (2015), following an approach of Pluhaár (2009). Proof. Suppose H is a k-graph with m edges. Map V (H) → [0, 1] uniformly at random. Color vertices greedily from left to right: color a vertex blue unless it would create a monochromatic edge, in which case color it red (i.e., every red vertex is the final vertex in an edge with all earlier k − 1 vertices have been colored blue). The resulting coloring has no all-blue edges. What is the probability of seeing a red edge? If there is a red edge, then there must be two edges e, f so that the last vertex of e is the first vertex of f . Call such pair (e, f ) conflicting. Want to bound probability of seeing a conflicting pair in a random V (H) → [0, 1]. Here is an attempt (an earlier weaker result due to Pluhaár (2009)). Each pair of edges
(k−1)!2 2k−2 −1 1 with exactly one vertex in common conflicts with probability (2k−1)! = 2k−1  k−1 −1/2 −2k 2 k 2 ; union bounding over < m pairs of edges, the probability of of getting a conflicting edge is . m2 k −1/2 2−2k , which is < 1 for some m  k 1/4 2k . We’d like to do better by more carefully analyzing conflicting edges. Continuing . . . Write [0, 1] = L ∪ M ∪ R where (p to be decided)     1−p 1+p 1−p M := , L := 0, 2 2 2  R :=  1+p ,1 . 2 The probability that a given edge lands entirely in L is ( 1−p )k , and likewise with R 2 So probability that some edge of H is entirely contained in L or contained in R is ≤ )k . 2m( 1−p 2 Suppose that no edge of H lies entirely in L or entirely in R. If (e, f ) conflicts, then their unique common vertex xv ∈ e ∩ f must lie in M . So the probability that (e, f ) conflicts is (here we use x(1 − x) ≤ 1/4) Z (1+p)/2 xk−1 (1 − x)k−1 dx ≤ p4−k+1 . (1−p)/2 Thus the probability of seeing any conflicting pair is  ≤ 2m 1−p 2 k + m2 p4−k+1 < 2−k+1 me−pk + (2−k+1 m)2 p. Set p = log(2−k+2 k/m)/k, we find that the above probability is < 1 for m = c2k with c > 0 being a sufficiently small constant. p k/ log k,