# CMSC 37200 -- Combinatorics -- Spring 2010

Course home | Tests | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | Solutions #4

# Exercises

Homework due in writing is indicated by "HW." Do not hand in solutions to "DO," "Reward," "Puzzle" problems. The "DO" exercises are part of the regular course material, do solve them. The solution to a "Reward" or "Puzzle" problem is its own reward; these problems are meant to be challenging; "Puzzle" problems tend to have an "AH-HA" solution (which may not be easy to find). If you solved or plan to solve a Challenge, Reward, or a Puzzle problem, let the instructor know (by email). If you hand in a solution to a Challenge Problem, put it on a separate sheet (do not mix it with regular homework).

For typographical reasons, we use C(n,k) to denote the binomial coefficient {n choose k}.

### Exercise set #9 (Due Wednesday, May 26) Warning: solve Exercise set #8 by Monday, May 24.

9.0 REVIEW: Finite probability spaces (from instructor's online lecture notes (miniDM)), especially independence of random variables and Chebyshev's inequality.

9.1 DO: Prove: if M is a proper sub-Latin-square of a Latin square L of order n then M has order ≤ n/2 . ("Proper" means M ≠ L.)

9.2 DO: Prove: if R is a sub-STS of an STS of order n then R has order ≤ (n-1)/2 .

9.3 DO: Let T=(V,E) be an STS. We say that a subset W ⊆ V generates T if no proper sub-STS contains W. Prove: T has a set of ≤ log2 (n+1) generators (where n = |V| is the order of T).

9.4 DO: Let T be an STS of order n > 1. Prove: | Aut(T) | < nlog2 (n+1).   (Aut(T) denotes the group of automorphisms of T.)

9.5 DO (number of STSs): Let L(n) denote the number of n × n Latin Squares. Let S(n) denote the number of STSs on the vertex set [n].
Prove: (a) S(n) ≤ nn(n-1)/6.    (b) S(3n) ≥ (S(n))3L(n).    (c) S(3n-2) ≥ (S(n))3L(n-1).
(d) Theorem: log S(n) ∼ (n2 log n)/6 for all n for which an STS exists (i.e., n is congruent to 1 or 3 mod 6). Prove this asymptotic equality for n = 3k.

### Exercise set #8 (Due Monday, May 24)

By "random graphs" we mean uniformly distributed random graphs (edge probability 1/2) unless expressly stated otherwise.

8.1 HW (explicit Ramsey bound by Zsigmond Nagy, 1972): (a) Let v be a positive integer. We define Nagy's graph N(v) as follows. The set of vertices is the set V of triples from [v], so the graph has C(v,3) vertices. Two vertices A, B ∈ V are adjacent if | A ∩ B | = 1. Prove: α(N(v)) ≤ v and also α(N(v)c) ≤ v, where the superscript c indicates complement. Your solution should be very short and elegant (with reference to results proved [not just stated] in class). State the exact results from class you are using. (b) Show that part (a) implies the arrow relation n ↛ (cn1/3, cn1/3) for some positive constant c (if you can't read the symbol it says "does not arrow"). Estimate the value of c for large n.       (12 + 6 points)

8.2 HW: Prove: almost all graphs G satisfy the inequality χ(G) > (ω(G))100. Here ω(G) denotes the clique number (size of the largest clique) of G, i.e., ω(G) = α(Gc). "Almost all graphs have a property" means the probability that a random graph on n vertices has the property approaches to 1 as n → ∞.       (12 points)

8.3 HW: Recall that the lines of the affine geometry AG(t,3) forms an STS (Steiner Triple System). (The triples are the affine lines in the t-dimensional vector space over the field of order 3.) (a) Count the points. (b) Count the lines. (c) Let a(t) denote the independence number of this STS, i.e., the maximum number of vertices that do not contain a line. Prove that the limit L = lim (a(t))1/t exists (as t → ∞). (d) Prove: 2 ≤ L ≤ 3 . (e) Prove: 2 < L . Find the best lower bound on L you can. For this part, you may use the literature you can find on the web regarding the card game "SET." If you do, explain the connection.       (2+5+15+6+8 points) Note: it is an open question whether or not L < 3.

8.4 DO: Prove: almost all graphs have diameter 2. (The diameter of a graph is the maximum distance between pairs of points.)

8.5 DO: Prove: for n ≥ 3, the probability that a random graph has no triangle is less than cn2 for some constant c < 1.

8.6 DO: Let pn be a sequence of numbers between 0 and 1. Let us consider the random graph Gn on n vertices where the edges are chosen with probability pn (independently for every pair of vertices). (a) Prove that the expected number of edges is C(n,2)pn. (b) Determine the variance of the number of edges. (c) Determine the expected number of triangles. (d) Determine the variance of the number of triangles. (You should get a simple closed-form expression.) (e) Prove: if npn → 0 then with high probability Gn has no triangles. (Hint: Markov.) ("With high probability" means the probability approaches 1 as n → ∞.) (f) Prove: if npn → ∞ then with high probability Gn has at least one triangle. (Hint: Chebyshev.) In fact, w.h.p., the number of triangles will go to infinity.
Comment: evolution of random graphs. Around 1960, Erdős and Rényi studied the evolution of random graphs as the edge probability increases from 0 to 1. They found interesting "threshold phenomena." The exercise above shows that the threshold probability for the appearance of triangles in a random graph is 1/n: if the edge probability is much less (pn = o(1/n)), there will probably be no triangles; if it is much more (1/n = o(pn)), there will probably be triangles (in fact, a lot of them: approximately as many as their expected number).

8.7 DO: Interpret the cover design of your textbook.

8.8 DO: Construct p-1 orthogonal Latin Squares of order p, for all primes p. (You are asked to construct a set of p-1 Latin Squares that are pairwise orthogonal.) Prove that your Latin Squares are orthogonal.

8.9 DO: Construct 3 orthogonal Latin Squares of order 4.

8.10 DO: Construct 2 orthogonal Latin Squares of order n=2k+1, for all k ≥ 1. Prove that your Latin Squares are orthogonal.

8.11 DO: (a) Prove that there are no more than n-1 orthogonal Latin Squares of order n. (b) Prove: a set of n-1 orthogonal Latin Squares exists if and only if there exists a projective plane of order n.

### Exercise set #7 (Due Monday, May 10)

This problem set is mostly about the Shannon capacity Θ(G) of a graph G. Click here for the
Third Quiz. Read the quiz for the full texts of problems 7.2 and 7.3.

7.1 DO (Fekete's Lemma): (a) Let f : Z+ → R+ be a submultiplicative function from the positive integers to positive reals: f(r+s) ≤ f(r)f(s). Prove: The limit limn → ∞ (f(k))1/k exists and is equal to supn(f(k))1/k. (b) Recall from class how the same conclusion follows in one line for supermultiplicative functions.

7.2 HW (due Mon, May 10): Solve Quiz-3 problem 3:   Prove that Θ(G) ≤ χ(G--) where G-- denotes the complement of G.     (12 points)

7.3 HW (due Mon, May 10): Solve Quiz-3 problem 4:   Prove: if the graph G is self-complementary then Θ(G) ≥ √n.     (10 points)

7.4 DO (Lovász): Let d = d(G) denote the smallest dimension in which the graph G has an orthonormal representation (as defined by Lovász). Prove: Θ(G) ≤ d(G).

7.5 DO: (a) Prove: d(G) ≤ χ(G--) where G-- again denotes the complement of G. (Note that 7.2 follows by combining 7.4 and 7.5. If you wish, you may submit a solution to 7.4 and a solution to 7.5 in lieu of a direct solution to 7.2, although this is not recommended.) (b) Find a graph where the inequality is strict.

7.6 DO: (a) Prove: Θ(GH) ≥ Θ(G)Θ(H). (Here GH denotes the strong product of the graphs G and H.) (b) Prove: Θ(G2) = (Θ(G))2.

7.7 (this problem was in error, deleted)

7.8 DO: Let A, B be (not necessarily square) matrices over the field F. Prove: the rank of the Kronecker product of A and B is rk(A) rk(B).

7.9 DO (Haemers): Let A denote the adjacency matrix of the graph G and let p be a prime. Prove: Θ(G) ≤ rkp(I+A). Here rkp denotes the rank over the field Fp. (Note: this bound beats the Lovász θ function for some classes of graphs.)

7.10 DO: Let F(n,k) = ∏j=0 C(n , k/2j) where the fraction in the lower part of the binomial coefficients should be rounded down. Prove: there exists a constant C such that for all n and k we have F(n,k) ≤ Cn. State an explicit value of C for which you proved this statement.

### (WARNING: Do homework set #5 by Friday, April 30)

This homework set is posted in advance, do NOT submit the solutions together with Homework set #5. Mixing the two sets will cause confusion and may result in your solutions getting lost.

6.1 HW (due Mon, May 3): A hypergraph is d-regular if every vertex has degree d. (The degree of a vertex is the number of edges containing it.) It is regular if every vertex has the same degree. (a) Prove: if H is a nonempty regular r-uniform hypergraph on n vertices then τ(H) ≥ n/r. (b) Prove that the n/r lower bound is tight for every n and r in the sense that given n ≥ r ≥ 1 there exists a (nonempty) regular r-uniform hypergraph H with τ(H) = ⌈ n/r ⌉ (rounded-up value of n/r). Elegance counts; your solution to each part should be just a few lines.   (8+8 points)

6.2 DO: Let H be an r-uniform hypergraph with n vertices and m edges. Prove: τ(H) ≤ &lceil (n/r) ln m ⌉. (Hint: random selection. To make your calculations elegant, do not use the given expression for the upper bound on τ until the last line of your solution.)

6.3 HW (due Mon, May 3): Prove that the limit of the Gaussian binomial coefficient [n "choose" k]q is C(n,k) as q → 1. (In actual print, the n is above the k within the brackets as written on the blackboard.)   (6 points)

6.4 HW (due Mon, May 3): Consider the following hypergraph Hn,k (n > k > 1). The vertex set of Hn,k is F2n \ {0} (the vector space of n-tuples over the field of order 2, with zero deleted, so Hn,k has 2n - 1 vertices). The edges of Hn,k are the k-dimensional subspaces of F2n with zero deleted from each. So Hn,k is a (2k - 1)-uniform hypergraph with [n "choose" k]2 edges. (a) Prove that Hn,2 is a STS (Steiner Triple System). (b) Prove: χ(Hn,2) ≤ n.   (3+10 points) (c) CHALLENGE PROBLEM. Prove: χ(Hn,2) → ∞. (COMMENT. The vertices of Hn,k are the points of the (n - 1)-dimensional projective geometry over F2, and the edges of Hn,k are the (k - 1)-dimensional flats of this geometry. The 1-dimensional flats (k = 2) are the lines.)

6.5 HW (due Mon, May 3): With the notation of the previous exercise, prove: 2n-k < τ(Hn,k) < 2n-k+1.   (6+8 points)

6.6 DO: Let us color the edges of the complete graph Kn with t colors. (Warning: in this problem, colors are assigned to the edges! There is no condition like "legal" coloring here.) Prove: if n > e t!   then there will be a monochromatic triangle. (First prove this for t=2 and t=3; in these cases, the condition is n ≥ 6 and n ≥ 17, respectively.)

6.7 DO (I. Schur): Let us color the elements of a finite Abelian group G of order n by t colors. Prove: if n > e t!   then there will be three distinct elements x,y,z ∈ G of the same color such that x+y=z. (We write the operation in G as "addition.")

### Exercise set #5 (Due Friday, April 30)

5.0 STUDY the solutions to Homework set #4 (click "Solution #4" on the banner).

5.1 DO: For every n ≥ 3 construct a maximal set of Oddtown clubs which is not maximum. (n is the number of residents in Oddtown.)

5.2 HW (due Fri, Apr 30): Find the eigenvalues and an orthonormal eigenbasis for the matrix [1, 2; 2, 3] (the first row is [1,2], the second row is [2,3]).   (8 points)

5.3 DO: Let A be an n × n matrix over C; let f   be its characteristic polynomial, i.e., f(t) = det(tI - A). Let f   factor over C as f(t) = ∏ (t - λi) (there are n terms in this product; the λi are the eigenvalues of A, represented here with their algebraic multiplicities). The trace of A is defined as the sum of its diagonal elements: Tr(A) = ∑ aii. Prove: (a) Tr(A) = ∑ λi   (b) det(A) = ∏ λi.

5.4 DO: Recall that if A and B are n × n matrices (over any field) then det(AB) = det(A)det(B). Prove that the analogous statement is false for permanents. Construct counterexamples for every n ≥ 2.

5.5 DO: Consider the symmetric bilinear form f(x,y) = per[x, y] where x,y ∈ R2. Determine the corresponding symmetric 2 × 2 matrix A (so A needs to satisfy the identity f(x,y) = xTAy). Find the eigenvalues and an eigenbasis of A. Notice that the quadratic form f(x,x)   is indefinite.

5.6 HW (due Fri, Apr 30): Let r = (r1,r2,r3) ∈ R3 be a fixed positive vector ((∀ i)(ri > 0)). Consider the symmetric bilinear form f(x,y) = per[r, x, y] where x,y ∈ R3. (a) Determine the corresponding symmetric 3 × 3 matrix A (so A needs to satisfy the identity f(x,y) = xTAy.) (b) Find the characteristic polynomial of A (give a simple explicit expression for each coefficient). (c) Let the eigenvalues of A be &lambda1 ≥ &lambda2 ≥ &lambda3. Find ∑ λi and ∏ λi (give very simple expressions). (d) Prove that λ1 > 0 and &lambda2 < 0 (and therefore &lambda3 < 0). (This means f   is "Lorentzian.") Use your answers to (c) in your proof; do not use major results on permanents, discussed in class.    (4+4+4+4)

5.7 HW (due Fri, Apr 30): For every n, construct two symmetric n × n matrices with integer entries which are congruent over the reals but not congruent over the rationals. (Recall: the matrices A and B are congruent over the field F if there exists an invertible matrix S over F such that B = STAS.) Your proof of non-congruence should be elegant, only a few lines. (Hint: determinants.)   (8 points)

5.8 HW (due Fri, Apr 30): Let G=([n], E) be an undirected graph. We define the Laplacian of G as the n × n matrix L = (lij) where lii= deg(i) (the degree of vertex i) and for i ≠ j we let lij = -1 if vertices i and j are adjacent and lij = 0 if they are not adjacent. Notice that L is a symmetric real matrix; let its eigenvalues be &lambda0 ≤ &lambda1 ≤ ... ≤ &lambdan-1. (a) Prove that L is positive semidefinite. (Hint: represent xTLx as a simple sum of squares.) (b) Prove that &lambda0 = 0 (i.e., L is not positive definite). (c) Prove: &lambda1 > 0 if and only if G is connected. (d) Prove: ∑ λi = 2m where m is the number of edges.   (12+5+8+5 points) (COMMENT. The value of &lambda1 is an important algebraic measure of the strength of interconnectedness of G; it is closely related to the expansion rate of the graph and the speed of convergence of the random walk on the graph.)

5.9 HW (due Fri, Apr 30): Prove: if A is a real matrix (not necessarily square) then ATA is a positive semidefinite symmetric matrix. Your solution should be one or two lines.   (6 points)

5.10 DO: An Hadamard matrix is an n × n matrix such that every entry is 1 or -1, and the rows are orthogonal (under the standard dot product in Rn). (a) Prove: if such a matrix exists and n > 2 then n must be divisible by 4. (b) Construct an n × n Hadamard matrix for every n = 2k. (c*) (Reward problem) Construct an n × n Hadamard matrix for every n = p + 1 where p is a prime, congruent to -1 modulo 4.

5.11 HW (due Fri, April 30): Let H be an n × n Hadamard matrix. Prove: |det(H)| = nn/2. Your proof should be no more than 2 lines.   (8+8 points)

5.12 DO: Let L(n,k) denote the number of k × n Latin rectangles. Prove that log L(n,k) ∼ kn log n (asymptotically equal) as n → ∞ and k takes arbitrary values between 1 and n. Use the Permanent Inequality (a.k.a. van der Waerden's conjecture, or the Falikman - Egorychev Theorem).

5.13 DO: Prove: L(n,2) ∼ (n!)2/e. (Hint: inclusion-exclusion.)

### Exercise set #4 (Due Wednesday, April 21)

Start early on the problems; it is best if you read and understand the questions before Monday's class.

4.0 DO: Solve the problems of the second quiz. The quiz is posted (click "Grading, tests" on the banner of the course home page, and then click "Second Quiz"). Observe that Problem 5 (that per(A) ≠ 0 for doubly stochastic matrices) is essentially identical with the "turtles" problem below (Ex. 3.5).

4.1 HW (due Wed, Apr 21): (a) Define legal colorings of a hypergraph. (b) Prove: if an r-uniform hypergraph H has m ≤ 2r-1 edges then H is 2-colorable (i.e., χ(H) ≤ 2).     (2+8 points)   (This problem was previously assigned in class and then in Quiz-2.)

4.2 HW (due Wed, Apr 21): Recall from class that an n × n matrix A is fully indecomposable if it does not contain a k × (n-k) all-zero submatrix for any k (1 ≤ k ≤ n-1). (An r × s submatrix consists of the cells at the intersection of any r rows and any s columns of A.) Prove: if A is a nonnegative, fully indecomposable matrix then so is ATA. (AT is the transpose of A; a matrix is nonnegative if all entries are nonnegative.)     (8 points)

4.3 DO (due Wed, Apr 21): An n × n matrix A is irreducible if it does not contain a k × (n-k) all-zero submatrix B which has no element in the diagonal of A (so the set of k row indices and (n-k) column indices that define B are disjoint) for any k. (a) Note that if A is fully indecomposable then it is irreducible.
(b) Associate with A a digraph with vertex set [n]; put in a directed edge (i,j) if aij ≠ 0. Prove: this digraph is strongly connected if and only if A is irreduclible.

4.4 HW (due Wed, Apr 21): Let A be a nonnegative, irreducible n × n matrix. Let x be a nonnegative eigenvector of A, i.e., x is a column vector such that Ax = λ x for some λ ∈ R, and all entries of x are nonnegative and not all are zero. Prove: x is positive (i.e., all entries of x are positive). Use Ex. 4.3 without proof.     (8 points)

4.5 HW (due Wed, Apr 21): Let A be a nonnegative, irreducible n × n matrix. Let x,y be nonnegative eigenvectors. Prove: x is a scalar mutiple of y (i.e., there exists a number α ∈ R such that x = α y). (Use Ex. 4.4.)     (8 points)

### Exercise set #3 (DO exercises due Friday, April 16)

3.1 DO: Review the proof of Dénes König's Theorem that for bipartite graphs, τ = ν (τ denotes the size of a minimum cover, ν the size of a maximum matching). Method: alternating paths.

3.2 DO (Marriage Theorem, König -- Hall): Let G be a bipartite graph with the vertex set partitioned as R ∪ G (all edges go between R and G). Observe that there is a matching that matches every vertex in R ("R can be matched") exactly if |R| = τ. Prove that this is also equivalent to the condition that (∀ S ⊆ R)(|N(S)| ≥ |S|). Here N(S) denotes the set of neighbors of S, i.e., those vertices which have at least one neighbor in S. Use König's Theorem.

3.3 DO (system of distinct representatives (SDR)): Let F = {A1,...,Am} be a set system. Prove: F has a SDR if and only if (∀ I ⊆ [m]) (|∪i ∈ I Ai| ≥ |I|). (Hall's conditions). (Note: This is a direct translation of the Marriage Theorem.)

3.4 DO: Prove that every regular bipartite graph of degree ≥ 1 has a perfect matching. (Use the Marriage Theorem.)

3.5 DO (turtles): Beyond the seven seas there is a tiny island, 6 square miles in all. The island is inhabited by six native tribes and by six turtle species. Each tribe and each turtle species occupies one square mile of territory. The territories of the tribes don't overlap with one another; nor do the territories of the different turtle species. Each tribe wishes to select a totem animal from among the turtle species found in the tribe's territory; and each tribe must have a different totem animal. Prove that such a selection is always possible. State the exact result proved in class that you use.

3.6 DO (Birkhoff's Theorem): A permutation matrix is an n × n matrix in which every row and every column has exactly one entry equal to 1, all other entries are zero. An n × n matrix is doubly stochastic if all entries are nonnegative and all row sums and all column sums are 1. A convex combination of vectors over R is a linear combination where each coefficient is nonnegative and the sum of the coefficients is 1. Note that (1) all permutation matrices are doubly stochastic and (2) any convex combination of doubly stochastic matrices is doubly stochastic. (a) Count the permutation matrices. (b) Prove: every doubly stochastic matrix is a convex combination of permutation matrices. (Hint: turtles.)

3.7 DO (Chromatic polynomial): Let x be a nonnegative integer. For a graph G = (V,E), let fG(x) denote the number of legal colorings of G using a given set of x colors. (Not all the colors need to be used.) For instance, if G = Kn then fG(x) = x(x-1)...(x-n+1) and if G is the empty graph on n vertices then fG(x) = xn. Prove that for every G, the function fG(x) is a monic polynomial of degree n. ("Monic" means the leading coefficient is 1.)

### Exercise set #2 (Includes 4 HW problems due Mon, April 12, before class)

2.0 SOLVE FIRST QUIZ including the bonus problems. (I mistakenly stated that 5(b) had a one-line solution. The solution I know is simple, but it does involve linear algebra.) The quiz is posted (click "Grading, tests" on the banner of the course home page, and then click "First Quiz"). (You may need to press your browser's "Refresh" button, which is a good idea before any session anyway with a frequently updated website.) [Added on 4-9, 2:30pm]

2.1 STUDY ASYMPTOTIC NOTATION from instructor's "miniDM" lecture notes (click "Text" on the banner at course home page). The symbols you need to study: asymptotic equality (∼), little-oh, big-Oh, big-Omega (Ω), and big-Theta (Θ).

2.2 DO: Prove: C(n, ⌊n/2⌋)/2n ∼ c/√n for some constant c. Determine the value of c. (The symbols around n/2 indicate the "floor" function.)

2.3 HW (due Mon, April 12)(Littlewood - Offord problem, baby version): Let a1,...,an be nonzero real numbers; let r be any real number. Let us pick a subset I ⊆ [n] uniformly at random.
(a) What is the size of the sample space for this experiment?
(b) Prove: Pr( ∑i ∈ I ai = r) = O(1/√n). The big-Oh notation means the following: there exists a constant c such that the probability in question is at most c/√n. Hint: Sperner's Theorem.
(c) For every n find values ai and r such that Pr( ∑i ∈ I ai = r) = Θ(1/√n).    (2+10+4 points)

2.4 HW (due Mon, April 12) (R. C. Bose's proof of Fisher's inequality): Let r be a positive integer. Let A1,...,Am be subsets of the set [n] = {1,2,...,n} of size greater than r. Assume that for every i ≠ j we have |Ai ∩ Aj| = r. Prove that the incidence vectors of the Ai are linearly independent over R.    (10 points)    If this is too difficult, prove the result under the additional assumption that the set system is uniform: (∀ i)(|Ai| = k).    (6 points)

2.5 HW (due Mon, April 12) (Tamás Kővári - Vera T. Sós - Pál Turán, 1954): Let G be a graph without 4-cycles. Prove: m = O(n3/2), where, as usual, m denotes the number of edges and n the number of vertices of G. In other words, you need to show that m ≤ cn3/2 for some constant c. Hint: count the paths of length two in two different ways.    (12 points)

2.6 DO: Use the preceding theorem to prove: if the graph G has no 4-cycles then χ(G) = O(√n).

2.7 DO (KST 1954 as above): Prove: if G does not contain the complete bipartite graph K2,3 then m = O(n3/2).

2.8 DO: Prove: if G does not contain the complete bipartite graph K2,3 then χ(G) = O(√n).

2.9 DO: Recall that the girth of a graph is the length of its shortest cycle. (A tree has infinite girth.) A graph is regular of degree r if every vertex has degree r.
(a) Suppose G is a regular graph of degree r and G has girth ≥ 5. Prove: nr2 +1. (b) Show that n = r2 +1   is possible when r = 1, 2, 3. In the case of r = 3, the (unique) solution is a famous graph. Name the graph.
Note: n = r2 +1   is also possible when r = 7 (Hoffman - Singleton graph). The Hoffman - Singleton Theorem (1960) says that the only values for which n = r2 +1   is possible are 1, 2, 3, 7, 57. The question whether or not r = 57 is actually possible remains open.

2.10 DO: Recall that the odd-girth of a graph is the length of its shortest odd cycle. (A bipartite graph has infinite odd-girth.)
For a directed graph G, let us define its "undirected odd-girth" as the odd-girth of the undirected graph obtained by ignoring the orientation of the edges.
A DAG (directed acyclic graph) is a directed graph without directed cycles.
Prove: if G is a DAG and L(G) is its directed line-graph then the undirected odd-girth of L(G) is greater than the undirected odd-girth of G.

2.11 HW (chromatic number of directed line-graph): The directed line-graph of the directed graph G=(V,E) is defined as the directed graph L(G)=(E,L) where the directed edges (a,b), (c,d) ∈ E form an edge ((a,b), (c,d)) ∈ L in the line-graph if b = c. Prove: if G is a directed graph then χ(G) ≤ 2χ(L(G)). (Here χ denotes the chromatic number which is defined for directed graphs by ignoring orientation.)    (8 points)

2.12 DO (graphs with large chromatic number and large odd-girth): Prove: (∀ k, g)(∃ graph G)( χ(G) ≥ k and odd-girth(G) ≥ g). Hint: combine the preceding two exercises for a proof by induction on g (starting from g = 3).

2.13 (Kneser's Graph): For s ≥ 2t + 1, let K(s,t) denote Kneser's Graph, defined as follows. The vertices of Kneser's Graph are the subsets of [s] of size t (so there are C(s,t) vertices). Two vertices are adjacent if the corresponding t-subsets are disjoint. Prove that K(5,2) is Petersen's Graph.

2.14 Prove that the chromatic number of Kneser's graph K(s,t) is ≤ s-2t+2.
Note: This bound is tight (i.e., this value is the exact chromatic number of K(s,t)). This statement was known as "Kneser's conjecture" (1955) until László Lovász proved it in 1978 by a topological method, using the notion of homotopies of a high-dimensional simplicial complex associated with the graph to reduce Kneser's conjecture to Borsuk's Theorem in geometry (below). Within weeks of Lovász's proof, Imre Bárány gave a different proof that used elementary convex geometry to reduce Kneser's conjecture to Borsuk's Theorem.
Borsuk's Theorem (1933): Let Sr denote the r-dimensional sphere, i.e., the set of the points in Rr+1 at unit distance from the origin. If A1,...,Ar+1 are closed subsets of Sr such that their union is Sr then one of the Ai has diameter 2.

2.15 DO: Prove Borsuk's Theorem for r = 1 (the unit circle).

2.16 DO: (a) If s = 2t + l then express the odd-girth of the Kneser graph K(s,t) in terms of s and l. The answer will be 2 ⌈ t/l ⌉ +1. [NOTE: Formula corrected 4-14, 10pm. In the original posting, the formula was erroneously given as 2 ⌈ s/l ⌉ +1.]
(b) (Another construction of graphs with large odd-girth and large chromatic number.) Prove: (∀ k, g)(∃ s,t)( χ(K(s,t) ≥ k and odd-girth(K(s,t)) ≥ g). Hint: combine part (a) with Kneser's Conjecture (above).

2.17 DO (Borsuk graph): Following Erdős and Hajnal (1965), define Borsuk's ε-graph as follows. This is an infinite graph. Its vertices are the points of the r-dimensional unit sphere Sr; two points are adjacent if their distance is at most 2 - ε.
(a) For fixed r, prove that the odd-girth of Borsuk's ε-graph is &Theta(1/ε1/2).
(b) Use Borsuk's Theorem to prove that for all ε > 0, the chromatic number of Borsuk's graph is ≥ r + 2.

2.18 CHALLENGE PROBLEM (Erdős and de Bruijn (1950)). Let G be an infinite graph and k an integer. Prove: G is k-colorable if and only if every finite subgraph of G is k-colorable. ("k-colorable" means there exists a legal k-coloring.)

2.19 DO: Combine the preceding two exercises to yet another proof that there exist finite graphs with large chromatic number and large odd-girth. (This observation by Erdős and Hajnal, and their remark that Kneser's graph appeared to have similarities with Borsuk's graph, motivated Lovász's proof of Kneser's Conjecture.)

### Exercise set #1 (Due Mon, April 5, before class)

1.1 HW (due Mon, April 5) Let S(n,3) denote the number of those subsets of an n-set which have size divisible by 3. In other words, S(n,3) = ∑k C(n,3k). Prove: | S(n,3) - 2n/3 | < 1.    (10 points) Give a short and elegant solution. Hint: binomial theorem, complex numbers.

1.2 DO: Prove: C(n,k) ≥ (n/k)k.

1.3 HW (due Mon, April 5) Prove: C(n,0)+C(n,1)+...+C(n,k) < (ne/k)k. (1 ≤ k ≤ n). Give a short and elegant proof. You may use the inequality (1+x) < ex (valid for all x ≠ 0). HINT: binomial theorem.    (10 points)    If this is too difficult, prove that C(n,k) < (ne/k)k. (1 ≤ k ≤ n)    (6 points) HINT: power series of ex.

1.4 HW (due Mon, April 5) (Erdős-Rado Sunflower Theorem) A "Sunflower" is a set system {A1, A2, ..., As} such that if K = ∩i Ai then (∀ ij)( Ai&cap Aj = K). The Ai are called the petals and K is the kernel of the sunflower. Prove that if {B1, B2, ... , Bm} is a k-uniform set system and m > k !(s - 1)k then there exists a sunflower with s petals among them.    (10 points)

1.5 (Done in class: Sperner's Theorem) Two sets A and B are said to be comparable if either AB or BA. Let A1,...,Am ⊆ [n] be a family of sets such that (∀ ij)(AiAj and Ai and Aj are incomparable). Such a family is called a "Sperner Family" or an "anti-chain." Sperner's Theorem states that the maximum possible size of a Sperner family is C(n, ⌊n/2⌋). Solution: BLYM Inequality: If F is a Sperner family then ∑A ∈ F (1/C(n, |A|)) ≤ 1. (a) Use the BLYM Inequality to prove the Theorem. (b) Use the linearity of expectation to prove the BLYM inequality.

1.6 (Reward Problem: Sperner revisited) In class we proved Sperner's Theorem via the BLYM inequality. Give another proof of Sperner's Theorem by proving that the power set of [n] (denoted P([n]) is a union of C(n, ⌊n/2⌋) chains.

1.7 DO (Intersecting Families): Let A1,...,Am ⊆ [n] be a set system such that (∀ ij)( AiAj and AiAj ≠ ∅). (a) Prove that for any x ≤n,   |{A ⊆ [n] | xA}| = 2n-1. (b) Prove that this is the maximum possible size of set systems under this constraint, i.e., the maximum value of m.

1.8 DO: Find doubly exponentially many extremal set systems for the preceding problem.

1.9 (Study: Newton's Binomial Theorem) If |x| < 1 and α is a complex number, then (1+x)α = &sumn=0 C(α, n)xn, where C(α, n) = α( α-1)...( α -n+1)/n !

1.10 DO: Let an =(-1)n C(-1/2, n). Prove that (a) an ∼ 1/(πn)1/2 (asymptotic equality) [Hint: Stirling's formula]
(b) CHALLENGE PROBLEM: (∀ n)(an < 1/(πn)1/2) [Hint: experiment, discover pattern, conjecture, prove].

1.11 READING: Finite Probability Spaces Chapter in the online text, including Chebyshev's Inequality and the independence of random variables.

1.12 DO: (Greedy coloring) The greedy coloring algorithm colors the vertices of a graph sequentially, always using the first available color. (The "colors" are the nonnegative integers.) Color s is "not available" for vertex i if some neighbor j < i has been assigned color s. (a) Prove: the greedy coloring algorithm never uses more than 1 + degmax colors; in particular, χ(G) ≤ 1 + degmax. (b) Note that the number of colors used by the greedy coloring algorithm depends not only on the graph but also on the numbering of the vertices. Prove: the vertices of every graph can be numbered in such a way that he greedy coloring algorithm produces an optimal coloring. (c) Show that greedy coloring can be very far from optimal: for every k, find a bipartite graph on 2k vertices such that the greedy coloring uses k colors.

1.13 HW (due Mon, April 5) (Chromatic number of triangle free graph) If the graph G does not contain K3 then χ(G) ≤ 2n1/2+ 1.

1.14 DO: (Chromatic number of a directed graph) (a) Prove: If in a directed graph all vertices have out-degree ≤ k then χ ≤ 2k +1. (b) Prove that this bound is tight for every k.

1.15 DO: (Chromatic number vs independence number) Prove: for every graph G,   χ(G)α(G) ≥ n.

1.16 (Reward Problem: Coloring the unit distance graph) Consider the infinite graph of which the vertices are all points in the plane; two points are adjacent if they are at a unit distance. Let K be the chromatic number of this graph. Prove: 4 ≤ K ≤ 7.