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 ↛ (cn^1/3, cn^1/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))¹⁰⁰. Here ω(G) denotes the clique number (size of the largest clique) of G, i.e., ω(G) = α(G^c). "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 cⁿ² for some constant c < 1.

8.6 DO: Let p_n be a sequence of numbers between 0 and 1. Let us consider the random graph G_n on n vertices where the edges are chosen with probability p_n (independently for every pair of vertices). (a) Prove that the expected number of edges is C(n,2)p_n. (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 np_n → 0 then with high probability G_n has no triangles. (Hint: Markov.) ("With high probability" means the probability approaches 1 as n → ∞.) (f) Prove: if np_n → ∞ then with high probability G_n 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 (p_n = o(1/n)), there will probably be no triangles; if it is much more (1/n = o(p_n)), 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)

Exercise set #6 (Due Monday, May 3)

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) = ∑ a_ii. 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 ∈ R². Determine the corresponding symmetric 2 × 2 matrix A (so A needs to satisfy the identity f(x,y) = x^TAy). 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 = (r₁,r₂,r₃) ∈ R³ be a fixed positive vector ((∀ i)(r_i > 0)). Consider the symmetric bilinear form f(x,y) = per[r, x, y] where x,y ∈ R³. (a) Determine the corresponding symmetric 3 × 3 matrix A (so A needs to satisfy the identity f(x,y) = x^TAy.) (b) Find the characteristic polynomial of A (give a simple explicit expression for each coefficient). (c) Let the eigenvalues of A be &lambda₁ ≥ &lambda₂ ≥ &lambda₃. Find ∑ λ_i and ∏ λ_i (give very simple expressions). (d) Prove that λ₁ > 0 and &lambda₂ < 0 (and therefore &lambda₃ < 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 = S^TAS.) 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 = (l_ij) where l_ii= deg(i) (the degree of vertex i) and for i ≠ j we let l_ij = -1 if vertices i and j are adjacent and l_ij = 0 if they are not adjacent. Notice that L is a symmetric real matrix; let its eigenvalues be &lambda₀ ≤ &lambda₁ ≤ ... ≤ &lambda_n-1. (a) Prove that L is positive semidefinite. (Hint: represent x^TLx as a simple sum of squares.) (b) Prove that &lambda₀ = 0 (i.e., L is not positive definite). (c) Prove: &lambda₁ > 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 &lambda₁ 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 A^TA 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 Rⁿ). (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 = 2^k. (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)| = n^n/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!)²/e. (Hint: inclusion-exclusion.)

Exercise set #4 (Due Wednesday, April 21)

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 ≤ 2^r-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 A^TA. (A^T 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 a_ij ≠ 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)

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 = {A₁,...,A_m} be a set system. Prove: F has a SDR if and only if (∀ I ⊆ [m]) (|∪_{i ∈ I} A_i| ≥ |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 f_G(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 = K_n then f_G(x) = x(x-1)...(x-n+1) and if G is the empty graph on n vertices then f_G(x) = xⁿ. Prove that for every G, the function f_G(x) is a monic polynomial of degree n. ("Monic" means the leading coefficient is 1.)

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⌋)/2ⁿ ∼ 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 a₁,...,a_n 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} a_i = 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 a_i and r such that Pr( ∑_{i ∈ I} a_i = 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 A₁,...,A_m be subsets of the set [n] = {1,2,...,n} of size greater than r. Assume that for every i ≠ j we have |A_i ∩ A_j| = r. Prove that the incidence vectors of the A_i 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)(|A_i| = 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(n^3/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 ≤ cn^3/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 K_2,3 then m = O(n^3/2).

2.8 DO: Prove: if G does not contain the complete bipartite graph K_2,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: n ≥ r² +1. (b) Show that n = r² +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 = r² +1   is also possible when r = 7 (Hoffman - Singleton graph). The Hoffman - Singleton Theorem (1960) says that the only values for which n = r² +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 S^r denote the r-dimensional sphere, i.e., the set of the points in R^r+1 at unit distance from the origin. If A₁,...,A_r+1 are closed subsets of S^r such that their union is S^r then one of the A_i 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 S^r; 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.)

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) - 2ⁿ/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) < e^x (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 e^x.

1.4 HW (due Mon, April 5) (Erdős-Rado Sunflower Theorem) A "Sunflower" is a set system {A₁, A₂, ..., A_s} such that if K = ∩_i A_i then (∀ i≠j)( A_i&cap A_j = K). The A_i are called the petals and K is the kernel of the sunflower. Prove that if {B₁, B₂, ... , B_m} 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 A ⊆ B or B ⊆ A. Let A₁,...,A_m ⊆ [n] be a family of sets such that (∀ i ≠ j)(A_i ≠ A_j and A_i and A_j 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 A₁,...,A_m ⊆ [n] be a set system such that (∀ i ≠ j)( A_i ≠ A_j and A_i ∩ A_j ≠ ∅). (a) Prove that for any x ≤n,   |{A ⊆ [n] | x ∈ A}| = 2^n-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)^α = &sum_n=0^∞ C(α, n)xⁿ, where C(α, n) = α( α-1)...( α -n+1)/n !

1.10 DO: Let a_n =(-1)ⁿ C(-1/2, n). Prove that (a) a_n ∼ 1/(πn)^1/2 (asymptotic equality) [Hint: Stirling's formula]
   (b) CHALLENGE PROBLEM: (∀ n)(a_n < 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 + deg_max colors; in particular, χ(G) ≤ 1 + deg_max. (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 K₃ then χ(G) ≤ 2n^1/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.