[Solved] additive combinatorics

Assignment Prompt & Instructions

need only no 4 – ## attachment_16.pdf **## attachment_16.pdf** Problem Set 1 1. (Just checking you can use Cauchy-Schwarz) Suppose that S and T are nonempty finite sets and ρ a map from S to T show that ∑ t |ρ−1(t)|2 ≥ |S| 2 |T | . (This was the final step in my proof of the combinatorial Cauchy-Schwarz inequality that I left to you.) 2. (Applying Balog-Szemeredi-Gowers 1) Suppose that A is a nonempty finite subset of an abelian group Z. Suppose that E(A) = 1 K . Show that there is a constant C independent of K so that there exist sets A1, A2 ⊂ A with |A1| > |A| CK , |A2| > |A| CK , and |A1 +A2| ≤ CK8|A|. (I basically indicated how you can do this in lecture.) 3. (Applying Balog-Szemeredi-Gowers 2) With the same hypotheses as problem 2, show there is a constant C independent of K (but maybe dependent on the base of log that appears in this problem) and A1, A2 ⊂ A with |A1| > |A| CK(1 + logK) , |A2| > |A| CK(1 + logK) , and |A1 +A2| < CK3(1 + logK)5|A|. Hint: When choosing G, sort together those pairs whose sums have approximately the same number of representations. If you get a different upper bound than I did, it could mean that I screwed up this problem. In that case, prove the best upper bound you can. 4. (Applying Balog-Szemeredi-Gowers 3) In both problems 2 and 3, you are given an upper bound for |A1 +A2|. Can you get a reasonable upper bound for |A1 +A1|. An upper bound is reasonable if it is a constant times a power of K times a power of (1 + logK) so for example, the upper bounds you got for |A1 +A2| in problems 2 and 3 were reasonable. 1 C 5. (This is problem 6.4.3 from Tao-Vu.) Let G = G(A, B, E) be a bipartite graph. Here A and B are the parts and E is the set of edges, which we’ve been calling G. Here let |A| = |B| = N with N sufficiently large. Show that there is a function f from (1, ∞) to 2 (1, ∞) so that if |E| > N then G contains a complete bipartite subgraph with at least f(C) logN vertices in each part. Show that logN is the optimal dependence in N for such a result. 2 **## attachment_16.pdf** Problem Set 1 1. (Just checking you can use Cauchy-Schwarz) Suppose that S and T are nonempty finite sets and ρ a map from S to T show that ∑ t |ρ−1(t)|2 ≥ |S| 2 |T | . (This was the final step in my proof of the combinatorial Cauchy-Schwarz inequality that I left to you.) 2. (Applying Balog-Szemeredi-Gowers 1) Suppose that A is a nonempty finite subset of an abelian group Z. Suppose that E(A) = 1 K . Show that there is a constant C independent of K so that there exist sets A1, A2 ⊂ A with |A1| > |A| CK , |A2| > |A| CK , and |A1 +A2| ≤ CK8|A|. (I basically indicated how you can do this in lecture.) 3. (Applying Balog-Szemeredi-Gowers 2) With the same hypotheses as problem 2, show there is a constant C independent of K (but maybe dependent on the base of log that appears in this problem) and A1, A2 ⊂ A with |A1| > |A| CK(1 + logK) , |A2| > |A| CK(1 + logK) , and |A1 +A2| < CK3(1 + logK)5|A|. Hint: When choosing G, sort together those pairs whose sums have approximately the same number of representations. If you get a different upper bound than I did, it could mean that I screwed up this problem. In that case, prove the best upper bound you can. 4. (Applying Balog-Szemeredi-Gowers 3) In both problems 2 and 3, you are given an upper bound for |A1 +A2|. Can you get a reasonable upper bound for |A1 +A1|. An upper bound is reasonable if it is a constant times a power of K times a power of (1 + logK) so for example, the upper bounds you got for |A1 +A2| in problems 2 and 3 were reasonable. 1 C 5. (This is problem 6.4.3 from Tao-Vu.) Let G = G(A, B, E) be a bipartite graph. Here A and B are the parts and E is the set of edges, which we’ve been calling G. Here let |A| = |B| = N with N sufficiently large. Show that there is a function f from (1, ∞) to 2 (1, ∞) so that if |E| > N then G contains a complete bipartite subgraph with at least f(C) logN vertices in each part. Show that logN is the optimal dependence in N for such a result. 2