Übungen - Problem sheet 1 - 9 PDF

Preview

Summary

Problem sheet 1 - Problem sheet 2 - Problem sheet 3 - Problem sheet 4 - Problem sheet 5 - Porblem sheet 6 - Problem sheet 7 - Problem sheet 8 - Problem sheet 9 merged files: 01-sheet.pdf - 02-sheet.pdf - 03-sheet.pdf - 04-sheet.pdf - 05-sheet.pdf - 06-sheet.pdf - 07-sheet.pdf - 08-sheet.pdf - 09-she...

Description

summer term 2016

Extremal Graph Theory

Problem sheet 1 Discussion of solutions: April 28, 2016.

Problem 1. Let f (n) denote the largest number of edges among all triangle-free graphs that are non-bipartite. Prove that 1 (a) f (n) ≤ (n − 1)2 + 1, 4

1 (b) f (n) = (n − 1)2 + 1, 4

if n ≥ 5 is odd.

Problem 2. Consider a graph G on n vertices and m edges. (a) Prove that G contains at least

4m (m 3n

−

n2 ) 4

triangles. 2

(b) Prove that G contains at least ⌊2n⌋ triangles if m ≥ ⌊ n4 ⌋ + 1. Show that the result is sharp for n ≥ 3.

Problem 3. Let S be a set of n points in R2 such that the distance between any pair of points is at 2 most 1. Prove that there are at most ⌊ n3 ⌋ pairs of points in S whose distance is greater than √12 .

Problem 4. Consider a graph H. A graph G, with |V (G)| ≥ |V (H )|, is called H-saturated if G contains no copy of H, but adding any edge to G yields a graph containing H . For any n ≥ t ≥ 3 determine the minimum number of edges in a Kt -saturated graph on n vertices.

Jonathan Rollin

http://www.math.kit.edu/iag6/edu/extremalgt2016s

summer term 2016

Extremal Graph Theory

Problem sheet 2 Discussion of solutions: May 12, 2016.

Problem 5. Let H be a graph with χ(H) = t. (a) Prove that ex(n, H) ≥ ex(n, Kt ) for all n ≥ 1. (b) Suppose that ex(n, H) = ex(n, Kt ) for some n ≥ t. Prove that there is an edge e in H such that χ(H − e) < t. (c) Let tr (n) denote the number of edges in a Tur´an graph on n vertices with r parts, n ≥ r ≥ 1. Prove that for each ǫ > 0 there is an integer n0 such that for all n ≥ n0 we have 2 tr (n) ≥ (1 − r1 − ǫ) n2 .

Problem 6. For k ≥ 2 let G be a k-connected graph that does not contain an independent set of size k + 1. Prove that G contains a Hamiltonian cycle. Hint: Consider a longest cycle C in G, a component G′ of G − C, and the neighbors of G′ in C.

Problem 7. Determine the minimum number of edges in a connected graph on n, n ≥ 3, vertices where each edge is contained in a triangle.

Jonathan Rollin

http://www.math.kit.edu/iag6/edu/extremalgt2016s

summer term 2016

Extremal Graph Theory

Problem sheet 3 Discussion of solutions: May 12, 2016. Problem 8. Prove the following statements. (a) An ǫ-regular partition of a graph G is an ǫ-regular partition the complement of G. (b) If (X, Y ) is an ǫ-regular pair with density d, then at most ǫ|X| vertices in X have more than (d + ǫ)|Y | neighbors in Y . 2

(c) For each ǫ > 0 each graph G with |E(G)| ≤ ǫ3 ⌊ n4 ⌋ has an ǫ-regular partition with two parts. Problem 9. A = X0 ∪ X1 ∪ · · · ∪ Xk with exceptional set X0 is called ǫ-regular if P partition V (G) 2 |Xi ||Xj | ≤ ǫn , where the sum is taken over all not ǫ-regular pairs (Xi , Xj ), 1 ≤ i, j ≤ k. Consider the following function for a partition P that is similar to the mean square density q(P ) =

X

|Xi ||Xj | d(Xi , Xj )2 n2

1≤i,j ≤k

+

k XX

|Xi | d(Xi , {v})2 n2

v∈X0 i=1

+

X X

1 d({u}, {v })2 . n2

v∈X0 u∈X0

Prove the following statements. (a) Let P be a partition V (G) = X0 ∪ X1 ∪ · · · ∪ Xk with |X1 | = . . . = |Xk |, that is not ǫ-regular. Then there is a partition V (G) = Y0 ∪ Y1 ∪ · · · ∪ Yℓ , with k ≤ ℓ ≤ k23k , |Y0 | ≤ |X0 | + 2nk , |Y1 | = . . . = |Yk |, that has q-value least q(P ) + ǫ5 . (b) For each integer k0 ≥ 2 and each ǫ > 0 there is an integer K such that for any graph G on n ≥ k0 vertices there is an ǫ-regular partition V (G) = X0 ∪ X1 ∪ · · · ∪ Xk , with k0 ≤ k ≤ K, exceptional set X0 of size at most ǫn, and |X1 | = . . . = |Xk |. Hint: Follow the proof in Conlon’s lecture notes while after each application of Lemma 1 in Lecture 5 cut the sets into pieces of size ⌊2−3k |Xi |⌋. Problem 10. Let 0 < ν < 23 and consider a triangle-free graph G with n vertices and minimum degree at least ( 31 + ν)n. (a) Apply the regularity lemma in the form of Problem 9 (b) to obtain an ǫ-regular partition V (G) = X0 ∪ X1 ∪ · · · ∪ Xk with exceptional set X0 . Consider the partition [ VI with VI = {v ∈ V (G) | |NG (v) ∩ Xi | ≥ 9ν|Xi | ⇔ i ∈ I}. V (G) = I⊆{1,...,k}

Prove the following statements for each I ⊆ [k]. (i) If | ∪i∈I Xi | ≤ 32n, then any two vertices in VI have a common neighbor. (ii) If | ∪i∈I Xi | ≥ 32 n, then there is an ǫ-regular pair (Xi , Xj ), i, j ∈ I, of density at least 9ν . (iii) Each set VI is either independent or empty. (b) Prove that there is a constant C, depending on ν only, such that χ(G) ≤ C . Remark: One can show that four colors are sufficient using more sophisticated arguments. Moreover there are graphs on n vertices with minimum degree at most 13 n and arbitrarily large chromatic number. Jonathan Rollin

http://www.math.kit.edu/iag6/edu/extremalgt2016s

summer term 2016

Extremal Graph Theory

Problem sheet 4 Discussion of solutions: May 19, 2016.

Problem 11. A graph is triangle-formed if each edge is contained in exactly one triangle. Prove that for every λ > 0 there is n0 such that each triangle-formed graph on n vertices, with n ≥ n0 , has at most λn2 edges.

Problem 12. Let t be a positive integer and δ > 0. Prove that there is n0 such that for any n ≥ n0 and any bipartite graph with parts {u1 , . . . , un } and {v1 , . . . , vn } and at least δn2 edges there are arithmetic progressions x1 , . . . , xt and y1 , . . . , yt in [n] of length t and of common difference such that {ux1 , . . . , uxt } ∪ {vy1 , . . . , vyt } induces a complete bipartite graph.

Problem 13. Let G be a bipartite graph with parts A and B and density d. (a) Prove that there are A′ ⊆ A, B ′ ⊆ B , with |A′ | ≥ d|A|, |B ′ | ≥ 2−|A| |B| such that A′ ∪ B ′ induces a complete bipartite graph in G. (b) Prove that there is a constant c that depends on d only such √ that, if |A| = |B| = n, then there is a copy of Ka,b in G with a ≥ c log(n) and b ≥ n. Hint: Count pairs like in the proof of Theorem 1 in Lecture 8.

Jonathan Rollin

http://www.math.kit.edu/iag6/edu/extremalgt2016s

summer term 2016

Extremal Graph Theory

Problem sheet 5 Discussion of solutions: June 2, 2016.

Problem 14. For a prime number p consider the construction of a K2,2 -free graph G(p) in Lecture 8. (a) Draw the graph G(5). Hint: The automorphism group is isomorphic to the symmetry group of a square. (b) Prove that for distinct (x, y), (x′ , y ′ ) ∈ Zp × Zp \ {(0, 0)} the system of equations ux + vy = 1, ux′ + vy ′ = 1 has at most one solution (u, v) ∈ Zp × Zp . Conclude that G(p) is K2,2 -free.

Problem 15. Prove that for each bipartite graph H with t vertices and m edges and for each n ≥ 2 ex(n, H) ≥ 641 n

t−2 2−m−1

.

Deduce Theorem 1 from Lecture 10. Hint: Consider a random graph.

Problem 16. A 1-subdivision of a graph is obtained by subdividing each edge exactly once. Let ǫ ≤ 12 . 2 Prove that each 1graph on n ≥ 16ǫ− 3 vertices and ǫn2 edges contains a 1-subdivision of 3 Kt with t ≥ ǫ 2 n 4 . Hint: Dependent Random Choice

Jonathan Rollin

http://www.math.kit.edu/iag6/edu/extremalgt2016s

summer term 2016

Extremal Graph Theory

Problem sheet 6 Discussion of solutions: June 2, 2016.

Problem 17. Let ex(n, C≥k ) denote the largest number of edges among all graphs on n vertices that do not contain any cycle of length at least k, k ≥ 3. (a) Prove that for all k ≥ 2 and n ≥ 1 ex(n, C≥k+1) ≤

k (n − 1). 2

You may use the following fact without proof: For each k ≥ 2, each 2-connected graph with minimum degree k contains a cycle of length at least 2k or a Hamiltonian cycle. (b) Prove that for each k ≥ 2 there are infinitely many values of n with ex(n, C≥k+1) =

k (n − 1). 2

Problem 18. (a) For each k ≥ 1 and infinitely many positive integers n give a graph on n vertices and 21 (k − 1)n edges that does not contain any tree on k edges. (b) Prove that there is a constant c = c(k) ≥ 0 that depends only on k such that for any tree T on k edges 1 ex(n, T ) ≥ (k − 1)n − c. 2 (c) Prove that ex(n, P ) ≤ 12 (k − 1)n for any path P on k edges and all n ≥ 1.

Problem 19. Let G, H be bipartite graphs where G has parts A and B . We call G H-saturated, if G contains no copy of H but adding any edge between A and B to G yields a graph containing H . Let G be an arbitrary bipartite graph with parts A, |A| = m ≥ s, and B, |B| = n ≥ t. (a) Call a non-edge e of G between A and B critical, if adding e to G yields a bipartite graph with more copies of K2,t than G. Prove that at most (m − 1)(n − t + 1) of the non-edges of G are critical. (b) Prove that any K2,t-saturated graph G has at least n + (m − 1)(t − 1) edges. (c) Find a Ks,t-saturated graph G with (s − 1)n + (m − s + 1)(t − 1) edges.

Jonathan Rollin

www.math.kit.edu/iag6/edu/extremalgt2016s

summer term 2016

Extremal Graph Theory

Problem sheet 7 Discussion of solutions: June 9, 2016.

Problem 20. (a) Is there a graph G with at least two edges and ex(n, G) = 4n for some n ≥ 2?  (b) Is there a graph G with ex(n, G) ≥ 2n − n for all n ≥ 2?

Problem 21. Let Mk denote a matching on k ≥ 1 edges. (a) For n ≥ k − 1 find a graph G on n vertices that does not contain a copy of Mk with   + (k − 1)(n − k + 1). |E(G)| = k−1 2 (b) For n ≥ 3k prove that the graph from part (a) is the unique graph on n vertices with ex(n, Mk ) edges, i.e.,   + (k − 1)(n − k + 1). ex(n, Mk ) = k−1 2

Problem 22. Let G be a graph on n vertices. (a) Prove that, if G has ⌈2k⌉ vertices of degree n − 1, then G contains a copy of Ck . (b) Prove that, if xy is a non-edge of G with d(x) + d(y) ≥ 2n − k and G + xy contains a copy of Ck , then G contains a copy of Ck . (c) Calculate ex(n, Cn ) for all n ≥ 3.

Jonathan Rollin

www.math.kit.edu/iag6/edu/extremalgt2016s

summer term 2016

Extremal Graph Theory

Problem sheet 8 Discussion of solutions: June 16, 2016.

Problem 23. A hypergraph is called r-partite, if there is a partition of the vertices into r parts such that each edge contains at most one vertex from each part. The chromatic number χ of a hypergraph is the smallest number of colors needed to color the vertices such that each edge contains at least two vertices of different colors. (a) Prove that the Tur´an density is well-defined, i.e., prove that the following limit exists for each r-uniform hypergraph H π(H) = lim

n→∞

ex(n, H) n . r

(b) Is there a uniform hypergraph H with π(H) = 1? (c) Is there an r-uniform hypergraph H with π(H) = 0 that is not r-partite? (d) Let r ≥ 3. Is there an r-uniform hypergraph H with χ(H) = 2 and π(H) > 0?

Problem 24. (3) Let V1 , V2 , V3 be pairwise disjoint sets of size t and let Kt,t,t be the hypergraph with vertexset V = V1 ∪ V2 ∪ V3 that contains an edge E ⊆ V if and only if |E ∩ Vi | = 1 for all i = 1, 2, 3. Prove that there is a constant c (depending on t) such that for all n (3)

1

ex(n, Kt,t,t) ≤ c n3− t2 . (3)

Hint: Consider some H without Kt,t,t and count pairs (U, P ), where U , P ⊆ V (H) with |U | = 2, |P | = t, and U ∪ {p} ∈ E(H) for each p ∈ P . Apply Theorem 1 from Lecture 8.

Problem 25. Let k, r ≥ 1. An r-uniform sunflower with k petals and core C is a hypergraph that consists of k edges E1 , . . . , Ek of size r such that Ei ∩Ej = C, 1 ≤ i < j ≤ k, and |C| ≤ r − 1. (r) Let ex(n, S k ) denote the largest number of edges in an r-uniform hypergraph that does not contain any sunflower with k petals. Prove that for each n ≥ r(k − 1) (r) (k − 1)r ≤ ex(n, Sk ) ≤ r!(k − 1)r .

Ek

E1 E2 C

Hint: If there are only few pairwise disjoint edges, then there is a vertex contained in many edges.

Jonathan Rollin

Ei

www.math.kit.edu/iag6/edu/extremalgt2016s

summer term 2016

Extremal Graph Theory

Problem sheet 9 Discussion of solutions: June 23, 2016.

Definition. For graphs G and H the graph Ramsey number r(G, H ) is the smallest integer n such that in any coloring of the edges of Kn with colors red and blue there is either a red copy of G or a blue copy of H. We write r(G) = r(G, G).

Problem 26. Let Cn be a cycle with n vertices. (a) Calculate r(C3 , C4 ). (b) Calculate r(C4 , C4 ).

Problem 27. Let d ≥ 1. The d-cube Qd is the graph with vertex set {0, 1}d , i.e., all binary vectors of length d, where two vertices are adjacent if and only if they differ in exactly one coordinate. Use the method of dependent random choice to prove that r(Qd ) ≤ 23d = |V (Qd )|3 . Hint: Consider the majority color class in a coloring of K23d . Similar to Lemma 1 from Lecture 9, choose 32 d random vertices and prove that their common neighborhood contains a subset of size 12 |V (Qd )| where each d-tuple has at least |V (Qd )| common neighbors.

Problem 28. Prove that for all m, n ≥ 2 we have r (m, n) − r (m, n − 1) ≥ 2m − 3. Hint: Color the edges of Kr(m,n−1)+2m−4 . Use a red Km−2 in a coloring of Kr(m,n−1)−1 .

Jonathan Rollin

www.math.kit.edu/iag6/edu/extremalgt2016s...