PUMaC 2019 · 加试 · 第 11 题

PUMaC 2019 Power Round Solutions November 9, 2019 1 1.4.1 [5 points] c c

1. Note that A ∪ A = Ω, so P ( A ) + P ( A ) = P (Ω) = 1.
2. Note that B = A ∪ ( B \ A ), so P ( B ) = P ( A ) + P ( B \ A ) ≥ P ( A ). 1.1 Grading 2 points for the first part, 3 points for the second. 2 1.4.2 [5 points] 2
3. Since f ( t ) ≥ 0 and ( X − E ( X )) ≥ 0, we know Var( X ) ≥ 0.
4. If Var( X ) = 0, it follows for every term in the variance sum, f ( t ) = 0 or P ( X = t ) = 0. This means t = E ( X ) or P ( X = t ) = 0. If X is nonrandom, then t = E ( X ) for all t , so Var( X ) = 0.
5. We find 2 2 2 Var( X ) = E (( X − E ( X )) ) = E ( X − 2 X E ( X ) + E ( X ) ) 2 2 = E ( X − 2 X E ( X ) + E ( X ) ) 2 2 = E ( X ) − E (2 X E ( X )) + E ( X ) 2 2 2 = E ( X ) − 2 E ( X ) + E ( X ) 2 2 = E ( X ) − E ( X ) .
6. We know E ( XY ) = E ( X ) E ( Y ) if and only if X and Y are independent random variables. Then 2 Var( X + Y ) = E (( X + Y − E ( X + Y ))) 2 2 = E (( X + Y ) ) − E ( X + Y ) (Part 3) 2 2 2 = E ( X ) + E ( XY ) + E ( Y X ) + E ( Y ) − ( E ( X ) + E ( Y )) = 0 (If and only if E ( XY ) = E ( X ) E ( Y ))

2 2 5. Using part 3 and linearity of expectation, note that Var( aX ) = E (( aX ) ) − E ( aX ) = 2 2 2 2 2 2 2 2 a E ( X ) − a E ( X ) = a ( E ( X ) − E ( X ) ) = a Var( X ). 2.1 Grading 1 points for each part. 3 1.4.3 [5 points] We induct on the number of sets. Note that P ( A ∪ A ) = P ( A ∪ ( A \ A )) = P ( A ) + P ( A \ A ) ≤ P ( A ) + P ( A ) . 1 2 1 2 1 1 2 1 1 2 By induction we can find that P ( A ∪ · · · ∪ A ) ≤ P ( A ∪ · · · ∪ A ) + P ( A ) , 1 n 1 n − 1 n hence the desired result. 3.1 Grading 2 for having the idea to use induction, 5 for complete proof. 4 1.4.4 [10 points] We find that ∑ E ( X ) = x P ( X = x ) x ∑ ≥ x P ( X = x ) ( t is nonnegative) x ≥ t ∑ ≥ t P ( X = x ) x ≥ t = t P ( X ≥ t ) . This proves the desired statement. 4.1 Grading 4 points for writing out the formula for expected value, 10 for finishing the proof. 5 1.5.1 1 7 [5 points] If X is the value of the roll of a die, then E ( X ) = (1 + 2 + 3 + 4 + 5 + 6) = . 6 2 2 1 7 35 2 2 2 2 2 2 2 2 The variance is Var( X ) = E ( X ) − E ( X ) = (1 + 2 + 3 + 4 + 5 + 6 ) − = . 2 6 12 2 For one hundred rolls, let the values be X , . . . , X . Since the rolls are independent 1 100 E ( X + · · · + X ) = 100 E ( X ) = 350. For the variance, we find Var( X + · · · + X ) = 1 100 1 1 100 875 100 Var( X ) = . 1 3 2

5.1 Grading 2 points for expected value, 3 for variance. 6 1.5.2 [5 points] We have three cases: if we roll RR we are done; if we roll RB we have to start over with two extra rolls; if we roll B we start over with one extra roll. Therefore, 1 1 1 E ( R ) = (2) + (2 + E ( R )) + (1 + E ( R )), so E ( R ) = 6. 4 4 2 1 1 25 25 Similarly, E ( K ) = (2) + · ( E ( K ) + 2) + ( E ( K ) + 1). Solving for E ( K ) gives 2 26 26 26 26 E ( K ) = 702. For the random variable M , we claim that this is the random variable representing the minimal number of draws needed to draw one red card plus 1. To observe this, note that P ( M = t ) implies that the last two cards drawn are either RR or RB, and that for every pair of adjacent cards before, they are either BB or BR. But this requires that the first t − 2 cards are B and the t − 1st card is red. Hence, it suffices to compute the minimal number of draws it takes to draw a red card, and then add 1. To do this, we repeat the 1 1 E same argument as before: E = + ( E + 1), which means that = 1 and so E = 2, which 2 2 2 means that E ( M ) = 3. 6.1 Grading 1 point for each of R, B, K and 2 points for each M . Subtract at most 1 point if there is a calculation error but the reasoning is correct. 7 1.5.3 11 21 231 [10 points] First, E ( X X ) = · = . 10 20 2 2 4 For the variance, ( ) 2 Var( X X ) = E ( X X ) 10 20 10 20 2 2 2 2 = E ( X X ) + E ( − 2 X X ) + E ( X X ) 10 20 10 20 10 20 ( ) ( ) 2 2 2 2 1 + · · · + 10 1 + · · · + 20 2 = − E ( X X ) 10 20 10 20 ( ) 2 11 · 21 21 · 41 11 · 21 = − 6 6 4 35035 = . 16 2 21 · 11 11 · 10 2 3 4 By manual computation, we observe E ( X ) = , E ( X ) = , and E ( X ) = 10 10 10 6 4 25333 . This means 10 2 2 3 4 2 Var( X ( X − X )) = E ( X X ) − 2 E ( X X ) + E ( X ) − E ( X X ) 10 20 10 20 10 20 10 20 10 10 106799 2 2 2 +2 E ( X X ) E ( X ) − E ( X ) = 10 20 10 10 80 3

7.1 Grading 3 for expectation of X 0 X 0, 3 for variance 4 for variance of X 0( X 0 − X 0). Subtract up 1 2 1 2 1 to 2 points for an error in calculation with correct reasoning. 8 1.5.4 [5 points] A is the event that the second coin lands heads. B is the event that the first coin lands head. We want to compute P [ A | B ] = P [ A ∩ B ] / P [ B ] . We have that 1 1 1 1 P [ A ] = + · = 3 3 2 2 1 1 1 1 1 1 1 P [ A ∩ B ] = · · + · · = 3 2 2 3 2 2 6 So, the answer is (1 / 6) / (1 / 2) = 1 / 3 . If you return the first coin, the second coin is independent of the first coin. From symmetry, answer is 1 / 2. 8.1 Grading 3 points for first part a d 2 points for the second part. 9 1.5.5 [20 points] Let p = 3 k + 1 be a prime sufficiently large (so that S have distinct modulos in p). Consider T = { k + 1 , . . . , 2 k + 1 } . Modulo p , T is sum-free. We will pick a random ∗ a ∈ Z and compute the number of elements in S which land in T (modulo p ). This subset p will be sum-free. The probability that s ∈ S will land in T is ( k + 1) / ( p − 1) > = 1 / 3 there is a unique a which makes s equal to k+1, k+2, . . . , 2k+1. From Linearity of Expectation, the expected number of elements that land in T is (1 / 3) | S | , which suffices for the proof. 9.1 Grading 5 points for trying to use expectation, another 5 for looking at the probability that s ∈ S land in T . 10 1.5.6 [10 points] ( ) n 3 There are triangles. Each triangle has a probability of p of being in the graph. So, 3 ( ) n 3 there are p expected triangles. 3 4

10.1 Grading 5 points for looking at each triangle separately. 10 for complete solution. Subtract up to 2 points for error in computation with correct reasoning. 11 1.5.7 [30 points] Take 32 n edges, randomly, uniformly, independently with repetitions from A to n B , then fix X ⊆ A, Y ⊆ B , | X | = | Y | = . Now we have that P (no edge is from X to Y ) = 4 2 n ( ) 2 n 1 32 n 32 n − 2 n 2 n 16 (1 − ) = (1 − ) < e . There exists only pairs of X, Y which is < 2 . n 2 16 n 4 2 n − 2 n Thus since 2 e << 1 there is such graph. 11.1 Grading 5 points for looking at 32 n edges randomly uniformly independently and 10 looking at the probability at P (no edge is from X to Y ). The rest for finishing the proof. 12 2.1.1 [20 points] Second part implies the first part. The second part is equivalent to proving that as m goes to infinity the probability of P being not ε -regular goes to 0, and this follows from the ∑ union bound, namely P ( U, W not ε -regular) ≤ P ( X, Y is not ε regular) ≤ any pair X, Y , | X | ≥ ε | U , | Y | ≥ ε | W | 1. 12.1 Grading 5 points for proving that second part implies the first part. Another 5 for doing manipulation with probabilities. The rest for finishing the proof. 13 2.1.2 ( ) ∑ n 2 [10 points] Since d ( U, W ) ≤ 1 for all U, W and | U || W | ≤ , where n is the U,W, unordered 2 1 number of vertices of the graph it follows that q ( P ) ≥ 0 , q ( P ) ≤ . 2 13.1 Grading 4 for looking at d ( U, W ) ≤ 1 and 4 for looking at unordered pairs. The rest for finishing the proof. 14 2.1.3 [10 points] Follows immediately from lemma 2 . 1 . 1. 5

14.1 Grading At most 5 points if a solutin mentions lemma 2 . 1 . 1 but is not completed. 15 2.1.4 [30 points] Since ( U, W ) is not ε -regular there exists U , W ⊆ U, W , | U | ≥ ε | U | , | W | ≥ 1 1 1 1 2 n ε | W | , | d ( U , W ) − d ( U, W ) | ≥ ε . Let Z be as before. We have that var ( z ) = ( q ( U , W ) − 1 1 | U || W | q ( U, W )). On the other hand since Z differs from E ( z ) = d ( U, W ) by ≥ ε with probability | U || W | | U || W | 1 1 1 1 2 ≥ thus var ( z ) ≥ ε . The result follows from this. | U || W | | U || W | 15.1 Grading 2 n 10 points for showing that var ( z ) = ( q ( U , W ) − q ( U, W )). Another 10 for looking at | U || W | E ( z ) and difference with d ( U, W ). At most 20 for looking at these but not finishing the proof. 16 2.1.5 n (1 − ε ) n [50 points] Put ≥ c = | V | = ... = | V | ≥ . For all 1 ≤ i < j ≤ k define a 1 k k k partition V of V into ≤ 2 parts and a partition of V int ≤ 2 parts as follows: if ( V , V ) ij i j i j is ε -regular V , V are trivial(only one part) otherwise we partition as in previous proof. ij ji Take a paritition V of each V defined by the Venn diagram of all k − 1 partitions of V . i i i,j | V | c i k − 1 V has at most 2 parts. To make their sizes equal let b = [ ] = and split each part i k k 4 4 of V into disjoint sets of sizes b each, and if there is something remaining add it to the i c n ′ ′ k − 1 k − 1 exceptional sets V . Now | V | ≤ | V | + bk 2 ≤ | V | + k 2 ≤ | V | + ( n is the number 0 0 0 k k 0 0 4 2 c k of vertices of the graph), since ck ≤ n . Also note that l ≤ k ≤ k 4 . Since P is not ε -regular b 2 c 1 ′ 2 4 5 by problem 2 . 1 . 4 and by lemma 2 . 1 . 1 we have that q ( P ) ≥ q ( P ) + εk ε ≥ q ( P ) + ε , 2 n 2 3 where the last inequality follows from kc ≥ (1 − ε ) n ≥ n . 4 16.1 Grading ′ 35 for showing that there exists a new partition of V such that it’s equitable and | V | ≤ i 0 n | V | + . 10 for mentioning problem 2 . 1 . 4 and lemma 2 . 1 . 1 0 k 2 17 2.1.6 εn [15 points] Start with any partition into t equal parts such taht | V | ≤ t ( ≤ for large 0 2 1 5 n ). As long as it is not ε -regular apply 2 . 1 . 5 and note that index increases by at least ε 2 1 and is never bigger than so it stops in at most s steps and the size of the exceptional set 2 6 6 n 1 nε nε nε nε 1 t − 2 incerases by at most s ≤ (1 + ) = + ≤ . (because 2 ≥ ). t 5 6 2 4 4 4 2 e ε 17.1 Grading 10 points for applying 2 . 1 . 5 by starting from a partition. 6

18 2.2.1 ε 10 [50 points] Take, say, regular partition of G with t = , which exists by Collegiate 10 ε Splitting theorem. V = v ∪ V ...V , t ≤ k ≤ T = T ( t, ε ). Remove now the following edges: 0 1 k 2 εn

1. All edges incident with V ( ≥ edges) 0 10 2 εn
2. all edges inside sets V , ≤ edges, as graph of edges removed here is of max degree i 20 n εn | V | ≤ = 1 t 10 2 ε n εn 2 2
3. all edges between irregular pairs which are not ε -regular, ≤ k ( ) = edges 10 k 10 ( ) k 3 ε 3 ε n 3 2 2
4. all edges between pairs of density ≤ , at most ( ) ≤ εn . 10 2 10 k 20 2 Altogether number of edges removed is ¡ εn . Thus at least one triangle is left. This ε triangle has vertices in 3 distinct parts V , V , V so that all pairs of parts are -regular p q r 10 ε | V | 3 ε 1 and of density ≥ . Wlog let pairs V , V , V . Note that all vertices v ∈ V but ≤ 1 2 3 1 10 10 ε have ≥ ( d ( V , V ) − ) | V | neighbors in V , since otherwise those that do not, and V 1 2 2 2 2 10 ε 2 ε violate ε/ 10-regularity of ( V , V ). Similarly all v ∈ V have ≥ ( d ( V , V ) − ) | V | ≥ | V | 1 2 1 1 3 3 3 10 10 2 ε 2 ε neighbors in V . Fix v ∈ V with | N ( v ) ∩ V | ≥ | V | | N ( v ) ∩ V | ≥ | V | ( N ( v ) is 3 1 2 2 3 3 10 10 2 ε 2 ε 2 ε neighbors of v ). Then by regularity of V , V there exists ≥ ( | V || V | edges between 2 3 2 3 10 10 10 3 3 8 ε 8 ε n 2 N ( v ) ∩ V and N ( v ) ∩ V , so v belongs to ≥ | V | ≥ ( ) . Number of such v is 2 3 3 1 3 2 T 10 10 3 2 ε n 8 ε n 3 ≥ (1 − ) | V | > which implies that the number of triangles is ≥ ( ) proving the 1 3 10 2 T 2 T 10 3 8 ε 1 theorem with δ = . 3 1000 8 T 18.1 Grading 5 points for looking at cε regular partition. 10 removing the edges as in the proof such that 2 there’s at most εn of them. 35 for finishing the proof. 19 2.2.2 [60 points] Bob wins. We will prove that for any ε > 0 there exists n such that for any 0 | A | ⊆ εn A contains a three term arithmetic progression. Let G be a three-partite graph with classes of vertices of sizes h , h , h , H , H , H each beign a copy of [ n ]. For any 1 2 3 1 2 3 k ∈ [ n ] , a ∈ A add to the graph the three edges of a triangle on vts h ∈ H , h + a ∈ 1 2 H , h + 2 a ∈ H note that all the make ≥ εn triangles which are pairwise edge disjoint. 2 3 Since knowing two vertices among h, h + a, h + 2 a we can reconstruct h, a uniquely, we 2 ε 2 have to delete ≥ εn = (3 n ) edges to destroy all triangles. By Coupon theorem there is 9 3 ≥ δ ( ε ) n triangles, and in particular there is at least one triangle besides the initial ones, this gives a, b, c distinct and h ∈ [ n ] with h + a + b = h + 2 c which implies a + b = 2 c . 19.1 Grading 5 for reducing to arithmetic progression. Another 10 for wiritng that with an equivalent graph. 45 for finishing the proof. 7

20 2.2.3 ∑ s i [60 points] Let | A | ⊂ [ n ] Fix d which we will choose later, | A | = { x d ≤ n, 0 ≤ i i =0 ∑ d 2 x < , x = K } , where K is choosen to maximize | A | . Note now that by pigeonhole i i 2 √ d s +1 ( ) n log n 2 √ | A | ≥ , choose d = 2 and then | A | ≥ for any ε , | A | has no three d 2 O ( log n ) 1 − ε ( s +1)( ) 2 >n 2 term arithmetic progression so | A | does not have two numbers such that one is the mean of the other two. 20.1 Grading 40 for choosing the right A , 20 for finishing the proof. 21 2.2.4 and 2.2.5 [30+30 points] For any a , a ∈ A there exists a unique ( x, y ) ∈ { 2 , 3 , .., 2 n } × { 2 , 3 , .., 2 n } 1 2 | A | such that a = ( x, y ) − a . This means that for any a ∈ A P ( a ∈ A ) = ≥ 1 2 1 1 x,y 2 (2 n − 1) 2 2 εn ε 3 ε 2 ≥ . By linearity of expectation expected size of | A ∩ A | is ≥ | A | ≥ = δn . Put 2 x,y 4 4 4 4 n ′ B = A ∩ A . Suffices to show that contains the triple for either d > 0 or d < 0. Define a three partite graph on classes of vertices V = vertical lines, V = horizontal lines, V = 1 2 3 line swith slope − 1(through lattice points). Two vertices are adjacent if and only if the corresponding intersection of the corresponding lines lies in B . For any b in B we get a triangle corresponding to the three lines in V , V , V that pass through b . The triangles are 1 2 3 2 δ 2 2 2 edge disjoint which implies that we have to remove | B | ≥ δn ≥ ( | V | + | V | + | V | ) to 1 2 3 16 remove all triangles which implies that by Coupon theorem there exists another triangle. Similarly, other two cases hold as well. 21.1 Grading 2.2.4. 10 points for looking at the probability that a ∈ A . 20 for the rest of the solution. 1 2.2.5 15 for looking at the graph. 15 for finishing the proof. 22 2.2.6 [40 points] We work in Z / ( M n + 1) Z for M = lcm (2019 , 2020 , 2039). Take the first n elements of this set and take a subset of this that has | X | ≥ εn elements. Take sets H , H , H 1 2 3 subsets of { 1 , . . . , 4040 n } in the integers mod ( M n + 1). Join vertices in the following way: if a ∈ H and a ∈ H join them iff a − a ∈ 2019 X . Similarly join two elements in H , H 1 1 2 2 2 1 2 3 iff their difference a − a is in 2020 X and elements in H and H iff difference in 4039 X . If 3 2 1 3 we remove all the triangles of the form h, h + 2019 x, h + 4039 x for x ∈ X , we have removed 2 at least n | X | ≥ εn triangles (pairwise disjoint). By triangle removal lemma, there are at 3 least δ ( ε ) n of them, so for n big enough there is at least another triangle besides the ones we have removed. ∃ distinct a, b, c , s.t. h + 2019 a + 2020 b = h + 4039 c , which is what we want. 8

22.1 Grading 20 for looking at thee right graph and using Triangle removal lemma. 20 for finishing the proof. 23 2.3.1 2 [50 points] We prove the statement that it holds if we need to remove at least εn triangles. This is stronger since H contains a triangle. Refer to the proof of triangle removal lemma ε ε h and choose an ( ) regular partition and remove parts which are not regular and of 10 10 density at least 3 ε . Then count the number of copies of K in three pairs which are h ,h ,h 1 2 3 regular and of big enough size, so that there is enough copies of K , hence of H . h ,h ,h 1 2 3 23.1 Grading 24 2.3.2 [50 points] The theorem is called Erd´ os-Stone-Simonovits. Solutions are available online. Google just in case. Proof: The lower bound is witnessed by the bipartite graph with almost 1 2 equal number of vertices ≤ 1. Suppose G has ≥ ( + ε ) n . By Turan’s theorem this is ε 4 far from triangle-free. By the previous problem, G contains K ( h, h, h ) and hence H , where | H | = h . 24.1 Grading 25 2.3.3 ε [75 points] Take an -regular partition. Overcount the number of such G , N ( G ) by counting 10 the number of ways to construct G from G , M ( G : G ). N ( G ) ≤ N ( G ) M ( G : G ). Now 1 1 1 1 ε we specifically select the graph G to be graph that we get from G when we do the 1 10 partition and then take out all the edges incident to V , between pairs which are not regular 0 2 ε k and between pairs with density less than . We want to find A ( G ). Choose pairs 1 10 4 k ( ) ( ) ( ) k 2 out of in ways.Furthermore we look at how to reconstruct G from G to get that 2 1 k 2 4 2 n 2 k εn k (1+4 ε ) 4 B ( G : G ) ≤ 2 2 , and choosing the sets V , V , . . . , V adds in total A ( G ) ≤ 2 n !2 . 1 0 1 k 2 n (1+ o (1)) 4 log A ( G ) = 2 . 25.1 Grading 26 2.3.4 3 3 c 1 c [60 points] We use the bound T of the regularity lemma and let ε = and = . 1 100 100 T ( ε, ) ε ε | V | 1 We do the triangle removal proof and use the following fact: Note that all but ≤ 10 ε vertices in V have degree ≥ ( d ( V , V ) − ) | V | (otherwise the ε/ 10 regularity would be 1 1 2 2 10 violated). 9

Now we find H as a subgraph of the induced subgraph on V and V . We algorithmically 1 2 find vertices u , . . . , u , where h = | H | , such that in step i we choose u , and that they 1 i h alterante between V and V . In particular we use ε regularity to prove that we can always 1 2 choose such a vertex. We maintain sets C vertices that u can be chosen from after step i,j j i , at the start they are V or V . In each step we choose u from C and update the 1 2 i i − 1 ,i 1 n rest. If k = b we prove that | C ≥ 4 ε by induction. Updating the ones from the i − 1 ,i ε k same set V is just deducting the currently chosen vertex. Updating the others uses the fact 1 that the degree is at most 3, and that so far at most δn have been removed to prove that n | C | ≥ . . . ≥ 4 ε . i,j k 26.1 Grading 27 2.3.5 [75 points] We are basically looking for a k -regular graph. We apply Collegiate partition theorem with the argument for equitable partition (secretly Szemeredi’s regularity lemma). There ∃ a ε/ 10-regular partition. It is enough to prove the claim for a small ε . Start imitating the proof of the triangle removal lemma and take a ε/ 10 regular pair V , V . Important: 1 2 ε | V | 1 ε Note that all but ≤ vertices in V have degree ≥ ( d ( V , V ) − ) | V | (otherwise the 1 1 2 2 10 10 ε/ 10 regularity would be violated). Let the set of those that have a high degree in V be U . 1 1 2 ε Similarly define U . For v ∈ U , N ( v ) ∩ U ≥ ( d ( V , V ) − ) | V | . A symmetric statement 2 1 2 1 2 2 10 ε holds for 2 , 1. WLOG | U | = | U | . Then when restricted to U , U , the pair is regular by 1 2 1 2 9 a short calculation. Then the idea is to periodically find a perfect matching between vertices in U , U , and 1 2 remove those edges and show that the perfect matching conditions still hold, performing 2 2 this in total ε | U | times. The removed edges will make a ε | U | regular subgraph. 1 1 ′ 2 The minimal degree after removing these edges in U will be d = d − ε | U | ≥ ε | U | . 1 min 1 1 min Using regularity prove Hall’s condition. (There are three cases that depend on the size of the subset of U that we pick. The first one is | X | ≤ ε | U | , the second one is | X | between 1 1 ε this and (1 − ) | U | , and the third one is bigger than this.) Refer to Igor for clarification. 2 9 27.1 Grading 28 3.1.1 [10 points] When we remove or add an edge in graph G , the new graph is isomorphic to the graph H with the corresponding edge removed so this part holds. The second part is not true. 28.1 Grading 29 3.1.2 [15 points] 10

This part requires some sort of explanation, i.e. description of the tester and reasoning why is it true. • This is testable. • This is also testable. • Trivially testable, since for large n no graphs are ε -far from having k -clique. • Trivially testable, no graph is ε -far from this property since you always only add a 2 linear number of vertices, so it’s less than for large enough n . • This is testable. They are only supposed to fill in the details here in the theorem after this problem, i.e. the following text and the theorem that follows it: 100 Take the ε -tester to be the following: choose randomly uniformly vertices and 2 ε accept if and only if the induced subgraph on them is 3-colorable. Here, the tester is also one-sided (if G is 3-colorable it will always accept). In order to prove correctness we have to show the following. If G = ( V, E ) with | V | = n is ε -far from 3-colorable then the induced subgraph on a 100 random set of vertices is with high probability not 3-colorable. 2 ε 29.1 Grading 30 3.1.3 [30 points] By triangle removal if G is ε -far from triangle free and has n vertices then has ≥ 3 δn ( δ = δ ( ε )) triangles. If we take randomly 3 vertices, probability that they form a triangle 3 δn 1 is ≥ ≥ 6 δ . Doing it times we have that P (no triangle found | G is ε -far from triangle free) ≤ n δ ( ) 3 1 1 − 6 6 (1 − 6 δ ) ≤ e . Thus deciding according to such samplings is a good 1-sided ε -tester. δ 3 Taking randomly vertices and deciding according to the induced subgraph on them is a δ 1-sided ε -tester. 30.1 Grading 31 3.1.4 [40 points] Let K be the star with t edges. Let d ≥ d ≥ .. ≥ d be the degrees of 1 ,t 1 2 n ∑ d i ¯ vertices in G let d = ≥ 2 εn be the average degree. Number of homomorphisms from n ∑ n t t t ¯ K to G is d ≥ n d ≥ n (2 ε ) by Jensen. Now we can classify these homomorhpisms 1 ,t i i =1 t according to ordered set of t vertices to which the leaves are mapped. There exists N = n ¯ such classes. Let D , D , .., D be numnbers of homomorphisms in the classes, let D be 1 2 N t n (2 εn ) t ¯ their average, D ≥ = n (2 ε ) . The number of homomorphisms from K to G is s,t N ∑ N s s t s st s + t ¯ D ≥ N D ≥ N ( n (2 ε ) ) = (2 ε ) n . Number of homomorphisms which are not i =1 i s + t st s + t 1 − 1 is ≤ o ( n ) and thus the number of ordered copies is at least (1 − o (1))(2 ε ) n ≥ 2 h / 4 h c ( s, t ) ε n . 11

31.1 Grading 32 3.1.5 [15 points] Let m, X be as in the previous lemma. Let G be a 5 partite graph on vertices classes V , .., V , and | V | = im . Denote V = { 1 , ..., im } , V are pairwise disjoint. For any 1 5 i i i j ∈ [ m ] and x ∈ X take a copy of C on V vertices j ∈ V , j + x ∈ V , .., j + 4 x ∈ V . There 5 i 1 2 5 2 m √ exists m | X | ≥ copies of C which are pairwise disjoint. Every edge is in exactly 5 10( log m ) 2 n one copy of C in G or equivalently G contains exactly m | X | copies of C . Let r = . Let 5 5 15 m 1 1 1 1 1 log 2 100 ε 1 (log ( )) =( ) ′ √ 100 ε ε G be the r -blow up of G . Let ε = which implies m = 2 . Note 10 log m 2 ′ 5 5 that now G contains m | X | r copies of C ( r for each C of G ). Thus to destroy all copies of 5 5 5 3 2 2 C in G we have to delete at least m | X | r /r ≥ m | X | r ≥ Ω( εn ) edges so G is Ω( ε ) C -free. 5 5 1 Θ(log ) 5 2 5 5 3 5 ε The total number of copies in G is m | X | r ≤ m ( n/ 15 m ) ≤ n /m = ε n which proves the claim. 32.1 Grading 33 3.1.6 [50 points] Note that if we may assume that any tester pick(perhaps adaptevely) some set of ( ) y y vertices and queries the pairs on them. Also adaptiveness does not help since the input 2 can be given after randomly permuting the vertices. Thus, we can WLOG assume that any tester simply looks at an induced subgraph and decides based on this since. By 3 . 1 . 4 we have proved the direction H is bipartite = ⇒ P is easily testable. To prove the other H implication we use the theorem 3 . 1 .IV . If we choose y random vertices G is ε -far from P H y 1 1 ( ) θ log( ) h θ (log ) h h ε ε and no of H in G is ≤ ε n , probability of seeing a copy of H is ≤ ε n = o (1) n ( ) h 1 1 o (log( )) 1 1 Ω(log ) ε ε for y = , which implies that we need at least ( ) queries, i.e. it’s not easily ε ε testable if H is not bipartite. 33.1 Grading 34 3.2.1 [25 points] The first way to solve this is just to prove theorem 3 . 1 .II , by showing that there √ exists n such that with less than c n queries we can’t distinguish between two random n n graphs on { 1 , 2 , . . . , } and { + 1 , . . . , n } and two copies of the same random graph. 2 2 Alternatively, take a similar construction as in theorem 3.1.II, but with 2 parts instead of 2. Then the proof is similar, i.e. prove that we cannot distinguish between two random √ graphs on n vertices with three parts with less than o ( n ) queries(or any other function of n ). 12

34.1 Grading 35 3.2.2 [15 points] 13