PUMaC 2019 · 加试 · 第 4 题
PUMaC 2019 — Power Round — Problem 4
题目详情
- Please collate the solutions in order in your solution packet. Each problem should start on a new page, and solutions should be written on one side of the paper only (there is a point deduction for not following this formatting).
解析
- 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