24. (Wednesday, June 4)

Today's exercises should all be considered "BONUS;" they are not required for the final exam.

24.1 (Inner product for polynomials) Let f and g be two polynomials and w(x) ≥ 0 be a weigth function. We assume the weight function is "nice," e.g., it is continuous on an open interval and zero outside the interval. We also assume that for all n, the integral ∫_-∞^+∞x²ⁿ w(x)dx converges. Then the inner product of polynomials with respect to w, given by <f,g> = ∫_-∞^+∞ f(x)g(x)w(x)dx, also converges. The polynomials f and g are orthogonal if <f,g> = 0. Prove that the weight function w(x) = e^-x2 satisfies the required convergence condition.

24.2 (Sequence of orthogonal polynomials) If w(x) is a weight function defining a inner product on the space of polynomials then there exists a sequence {f_n(x)} of polynomials such that deg(f_n) = n and for all m ≠ n the polynomials f_n and f_m are orthogonal. Prove that after normalization the sequence {f_n} is unique.

24.3 (Classical orthogonal polynomials) If w(x) = e^-x2 then the sequence of orthogonal polynomials is called the Hermite polynomials (denoted H_n). If w(x) = 1/(1-x²)^1/2 then the sequence of orthogonal polynomials is called the Chebyshev polynomials of the first kind (denoted T_n) while if w(x) = (1-x²)^1/2 then the sequence of orthogonal polynomials is called the Chebyshev polynomials of the second kind (denoted U_n). (Outside the interval (-1,1), these weight functions are defined to be zero.) An alternative definition of Chebyshev's polynomials is via the identities T_n(cos θ) = cos (n θ) and U_n(cos θ) = sin ((n + 1) θ)/sin θ. Prove that Chebyshev's polynomials, defined by these identities, are orthogonal with respect to their corresponding weight functions.

24.4 (Interlacing eigenvalues) Let A be a real symmetric matrix and let _iA_j be the matrix obtained by deleting the i-th row and j-th column. Prove that the eigenvalues of _iA_i interlace the eigenvalues of A.

24.5 (Matching polynomials) Given a graph G, a k-matching is a set of k disjoint edges. Let m_k be the number of k-matchings in . Then the polynomial m_G(x) = ∑m_k x^n-2k is called the matching polynomial of G (n is the number of vertices.) Prove that if G is a tree (or a forest) then m_G(x) is the same as the charecteristic polynomial of the adjacency matrix of G. Prove that (a) m_Kn = H_n; (b) m_path = T_n; (c) m_cycle = U_n; (d) m_Kr,s is a Laguerre polynomial (look them up).

24.6 (Heilmann-Lieb Theorem) For any graph G the roots of m_G(x) are reals and they interlace and there exists a 3-term recurrence.

24.7 If X is a random variable taking non-negative values then the generating function of X is f_X(x) = ∑ Pr(X = k) x^k. Prove that if X,Y are independent random variables then f_{X + Y} = f_X f_Y.

24.8 Let X be the number of edges in a random matching in the graph G (selected uniformly among all matchings). Use the previous exercise and the Heilmann-Lieb Theorem to prove that X can be written as the sum of independent indicator variables (biased coin flips).

Go to top

23. (Monday, June 2)

23.1 (Chebyshev's Inequality) If X is a random variable and λ > 0 then Pr[ |X - E(X)| ≥ λ ) ≤ Var(X)/λ².

23.2 Recall Var(X) = E(X²) - E(X)². If X = ∑ Y_i then Var(X) = ∑ Var(Y_i) + ∑_i≠jCov(Y_i,Y_i), where Cov(X,Y) = E(XY) - E(X)E(Y).

23.3 Find the expected number of cliques of size k in a random graph.

23.4 Find the variance of the number of cliques of size k in a random graph.

23.5 (Second moment method) For a random graph G with n vertices, let X be the number of cliques of size k in G. Prove: for all ε > 0 if k < (2-ε) log n then
(a) E(X) → 0 as n → ∞ ; and
(b) Var(X) = o((E(X)²).
(c) Infer from these two statements that Pr(X = 0) goes to 0.
(d) Infer form (c) that for almost all graphs, the size of the largest clique is asymptotically 2 log n.

Go to top

22. (Friday, May 30)

22.1 (Unit distances) Consider a set S of n points in the plane. Let m(S) denote the number of pairs of points in S that are at unit distance. (Clearly m(S) ≤ (n choose 2).) Let m(n) be the maximum of m(S) over all sets S of n points in the plane. (a) Prove: m(n) = O(n^3/2). [Hint: Use the fact ex(n, K_2,3) = O(n^3/2).] (b) Bonus Problem. Prove: lim m(n)/n = ∞. (c) The best upper bound known is m(n) = O(n^5/4). (d) (Erdős's Conjecture) For all ε > 0,   m(n) = O(n ^1+ε).

22.2 For a set S of n points in the plane, define the maximum-distance graph as the graph with vertex set S; two points of S are adjacent if the distance between them is the diameter of S, i.e., the maximum distance between pairs of points in S. Prove: the number of edges of the maximum-distance graph is at most n. [Hint: Separate the geometry form the combinatorics by defining a property P of graphs such that (a) every max-distance graph in the plane has property P; and (b) every graph with n vertices and with property P has at most n edges.

22.3 Compute ∑_A⊆[n]1/C(n, |A|).

22.4 In class we did the proof of Sperner's Theorem using the BLYM lemma. The BLYM lemma was proved using the Lubell's permutation method. 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.

22.5 (Dilworth's Theorem, 1947) [HW: Look up the definition of POSET (partially ordered sets).] The theorem states that the maximum size of an antichain in a finite poset is equal to the minimum number of chains that cover the entire poset. (HW: Read the proof of the theorem from the book. it is short but subtle.)

22.6 (König vs. Dilworth) Deduce König's ν = τ theorem from Dilworth's Theorem.

22.7 (Bonus 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.

Go to top

21. (Wednesday, May 28)

21.1 (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.

21.2 Find doubly exponentially many extremal set systems.

21.3 (Erdős-Ko-Rado Theorem for intersecting k-uniform families) Let A₁,...,A_m ⊆ [n] be a set system such that (∀ i)(|A_i| = k) and (∀ i ≠ j)( A_i ≠ A_j and A_i ∩ A_j ≠ φ). Such a set system is called an intersecting k-uniform family. Assume k ≤ n/2. Then the maximum possible size of an intersecting k-uniform family is C(n-1, k-1). (The proof uses an averaging argument, see new handout which corrects an error made in class.)

21.4 (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 _⌋). [HINT: 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 method of cyclic permutations to prove the BLYM inequality.

21.5 (Theorem of complete probability) Let Ω be the sample space and Ω₁, ..., Ω_t be a partition of Ω. If A ⊆ Ω is an event then Pr(A) = ∑_iPr(A|Ω_i)Pr(Ω_i). (See online lecture notes.)

21.6 Prove that the degrees of vertex number 1 and vertex number 2 in a random graph are positively correlated.

21.7 (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 !

21.8 Let a_n =(-1)ⁿ C(-1/2, n). Prove that (a) a_n ∼ 1/(πn)^1/2 [Hint: Stirling's formula] (b) (∀ n)(a_n < 1/(πn)^1/2) [Hint: experiment, discover pattern, conjecture, prove].

Go to top

20. (Friday, May 23)

20.1 (Markov's Inequality) If X ≥ 0 is a nonnegative random variable with E(X) = m > 0 then (∀ α > 0) P(X ≥ αm) ≤ 1/α.

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

20.3 (Variance of sum of random variables) Recall that the covariance of the random variables X and Y is defined as Cov (X,Y) = E(XY) - E(X)E(Y). Note that the variance of X is Var (X) = Cov (X,X). Prove that Var ( ∑X_i) = ∑ Var (X_i) + ∑_{i ≠ j} Cov (X_i, X_j). (In the rightmost sum, every term appears twice because Cov (X,Y) = Cov (Y,X).)

20.4 (Triangles in a random graph) For 0 < p < 1, the notation G_n,p denotes the probability distribution on all graphs with vertex set V = [n] defined as follows: ∀ i≠j Pr[(i,j) ∈ E] = p; and these (n choose 2) events are independent. Let G be a random graph selected from the distribution G_n,1/2. Determine the variance of the number of triangles in G. Evaluate the quantity (a) exactly (b) asymptotically. Your asymptotic formula should be of the form an^b. Determine the constants a and b.

20.5 (Erdős-Rado Sunflower Theorem) A "Sunflower" is a set system {A₁, A₂, ..., A_s} such that if C = ∩_i A_i then ∀ i≠j A_i&cap A_j = C. The A_i are called the petals and C 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.

Go to top

19. (Wednesday, May 21)

19.1 (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.

19.2 (Chromatic number of triangle free graph) If the graph G does not contain K₃ then χ(G) ≤ 2n^1/2+ 1.

19.3 (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.

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

19.5 (Erdős's proof of existence of graphs with arbitrarily large girth and arbitrarily large chromatic number) (∀ k,l)(∃ G) such that girth(G)≥ k and χ(G) ≥ l. (Probabilistic method.)

Go to top

18. (Monday, May 19)

18.1 (Diameter of a random graph) Let p_n be the probability that the diameter of a random graph on n vertices is 2. Then
lim_{n → ∞} p_n = 1. The proof follows from the fact that Pr[∃ x ≠ y ∈ V such that x and y has no common neighbor] ≤ C(n, 2)(3/4)^n-2. Prove that for large n,   C(n, 2)(3/4)^n-2 ≤ (0.76)ⁿ and thus goes to zero at an exponential rate as n goes to infinity.

18.2 (Tournaments) A tournament is an oriented complete graph, i.e., every edge of the complete graph is oriented in exactly one direction. Note that the number of orientations of K_n is 2^C(n,2). Prove that every tournament has a directed Hamilton path. (A Hamilton path is a directed path that touches every vertex in the graph exactly once.)

18.3 A digraph is strongly connected if (∀ x,y ∈ V)(∃ a directed path from x to y). Prove that every strongly connected tournament has a Hamilton cycle.

18.4 Give a simple "good characterization" of strongly connected tournaments. (Hint: Prove that a tournament is not strongly connected if and only if there is a cut (partition of the set of vertices into two nonempty parts) such that all edges across the cut go in only one direction.)

18.5 (2-paradoxical tournament) A 2-paradoxical tournament is a tournament where each pair of players is beaten by some player. Construct a 2-paradoxical tournament on 7 vertices. Hint: 7-fold symmetry.

18.6 (k-paradoxical tournament, Erdős) A k-paradoxical tournament is defined similarly. Prove that for every k there exists a k-paradoxical tournament. Estimate the size of the tournament you obtained. (Hint: use the probabilistic method.)

18.7 Erdős's proof of Ramsey lower bound: n does not arrow (2log₂n + 1, 2log₂n + 1). If G is a random graph then Pr[∃ a k-subset A of V such that G on A is homogeneous] ≤ 2C(n,k)/(2^C(k,2)). From this fact prove that if 2C(n,k)/(2^C(k,2)) < 1 then n does not arrow (k,k). Conclude the proof by proving that 2C(n,k)/(2^C(k,2)) < 1 if k ≥ 1 + 2 log₂n.

Go to top

17. (Monday, May 12)

17.1 If G is a regular graph of degree r and girth ≥ 5 then n ≥ r² +1.

17.2 Prove that the automorphism group of Petersen's Graph has order 120 and is isomorphic to S₅.

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

17.4 Prove that the chromatic number of 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 called "Kneser's conjecture" for about four decades, until Lovász proved it using Borsuk's Theorem (see below) combined with the notion of homotopies of a high-dimensional simplicial complex associated with the graph. Subsequently Bárány gave a different proof that combined elementary convex geometry with Borsuk's Theorem.

17.5 Let C be the unit circle (circle of unit radius in the plane). Assume A and B are closed subsets of C and C = A ∪ B. Prove that max{diam(A), diam(B)} = 2, i.e., the circle cannot be covered by two closed subsets of strictly smaller diameter. (Note: obviously, 3 are enough.) -- Note: this is the case r = 1 of Borsuk's Theorem: 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.

17.6 The girth of an undirected graph is the length of the shortest cycle is the graph. The odd-girth of an undirected graph is the length of the shortest odd cycle in the graph. If s = 2t + l then find the odd-girth of K(s,t) in terms of s and l. Note: It will follow from your result that if l is small compared to s then the odd-girth is large.

17.7 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.

17.8 Prove: if the graph G does not contain a triangle then the chromatic number of G is O(n^1/2).

17.9 Prove that if G is a directed graph then χ(G) ≤ 2^χ(L(G)), where L(G) is the line graph of G. Here χ denotes the chromatic number which is defined for directed graphs by ignoring oriantation.

17.10 If G is a DAG of odd-girth l then odd-girth(L(G)) ≥ l + 2. (Here the odd-girth of a directed graph is defined by ignoring orientation.)

17.11 Prove that, ∀ k, l, ∃ graph of χ ≥ k and odd-girth ≥ l. Hint: induction on l. The base case is l = 3, for all k.

17.12 Let G be a digraph. Prove: if G has a vertex with "large" in-degree and "large" out-degree then L(G) contains a "large" complete bipartite subgraph. You need to formalize each occurrence of "large" in this statement.

Go to top

16. (Wednesday, May 7)

16.1 (Esther Klein) Prove that out of any 5 points in the plane with no three on a line, one can select the vertices of a convex quadrilateral.

16.2 (Happy Ending Problem: Erdős - Szekeres 1934) Prove that (∀ k)(∃ l) such that out of any l points in a plane with no three on a line, one can select the vertices of a convex k-gon. (Hint: use Esther Klein's lemma and Ramsey's Theorem).

16.3 (Erdős - Szekeres (1934) bounds for Ramsey numbers) (a) Prove that R(k + 1, l + 1) ≤ R(k, l + 1) + R(k + 1, l).
(b) Corollary: C(k + l, k) → (k + 1, l + 1). (Here C(n, k) denotes the binomial coefficient "n choose k.") [Hint: Prove by induction on k + l. The base cases are the equalities R(k, 2)= k and R(2, l)= l. -- We need infinitely many base cases. Why? ]

Notation. For a graph H, we use ex(n,H) to denote the maximum number of edges of those graphs on n vertices which do not contain H as a subgraph.

16.4 (Mantel - Turán Theorem) Prove: ex(n, K₃) = _&lfloor n²/4 _⌋.

16.5 (Turán's Theorem) Prove: ex(n, K_r) is equal to the number of edges in a complete (r-1)-partite graph with nearly equal parts (the sizes of the largest and smallest parts differ by at most 1).

16.6 (The easy direction of the Erdős - Stone - Simonovits Theorem in Extremal Graph Theory) Prove that for any graph H, ex(n,H) ≥ ex(n, K_r), where r is the chromatic number of H.

16.7 (Tamás Kővári - Vera T. Sós - Pál Turán) Prove that ex(n, C₄) = Ω(n^3/2). Here C₄ denotes the 4-cycle. (Note that this is a lower bound. Recall that in class we proved the upper bound part of the theorem: ex(n, C₄) = O(n^3/2). The conclusion is that the asymptotic order of magnitude of the quantity ex(n, C₄) is Θ(n^3/2).)

16.8 Use Jensen's Inequality to prove that for any n positive numbers the geometric mean is less than or equal to the arithmetic mean. (To which convex function do you need to apply Jensen's Inequality?)

Go to top

15. (Monday, May 5)

15.1 (Matching Polytope) Let us represent a matching of a given graph G=(V,E) by its incidence vector, i.e., a (0,1)-vector of length m=|E| (the number of edges), where the coordinates of the vector (call it x) are indexed by the edges of the graph; we set x_e=1 exactly if the edge e belongs to the matching. The convex hull of the incidence vectors of the matchings is the matching polytope of the graph. It is clear that the matching polytope satisfies the following three sets of linear constraints: (i) (∀ e ∈ E) x_e ≥ 0. (ii) (∀ v ∈ V) Σ_{e:v∈e}x_e ≤ 1. (iii) (∀ odd subsets W ⊆ V) Σ_e∈Wx_e ≤ (|W| - 1)/2.
(a) [Bonus] Prove that constraints (i) and (ii) are sufficient to define the matching polytope for bipartite graphs; (b) [Challenge] Prove that constraints (i), (ii) and (iii) are sufficient to describe the matching polytope for any graph.

15.2 (Challenge: Algorithmic Problem) Given a vector x ∈R^m, decide whether x is in the matching polytope. If x is in the matching polytope then certify it by writing x as a convex combination of at most m+1 matchings. If x is not in the matching polytope then certify it by finding a constraint that is violated.

15.3 (Lemma to Lovász's Greedy Cover bound) Let t = t₁ + t₂ + ... + t_d where t_i ≥ 0. Suppose that for all i = 1, ... , d the quantities t_i satisfy the following linear constraints: it_i+....+2t₂+ t₁≤v_i. Prove that t ≤ v_d/d + Σ_i=1,...,d-1v_i/i(i+1). -- Hint: find a positive linear combination of the constraints that gives the left-hand-side of the conclusion. The coefficients will be unique; check what you get on the right-hand side.

15.4 (Concluding step in the proof of Lovász's Greedy Cover bound) A k-matching of a graph is a collection of edges of the graph (edges can be repeated) such that each vertex is incident to at most k of the edges in the collection. ν_k is the maximum number of edges in a k-matching. Prove that ν_i ≤ iν*. Use this to finish the proof that τ ≤ (1 + 1/2 + 1/3 + ... + 1/d) τ*.

Go to top

14. (Friday, May 2)

14.1 (König's Path Lemma) Prove König's Path Lemma: Given a rooted DAG such that (1) all vertices are reachable from the root (2) all vertices have finite out-degree and (3) there are infinitely many vertices, then prove that there exists a infinite path from the root. Also prove that the lemma is false if the condition (2) is not there.

14.2 Prove that n → ((log₂n)/2, (log₂n)/2).

14.3 Prove that 17 → (3,3,3). Also find a integer N such that N → (3,3,...,3) (r colors). Show that N= ^⌈ er! ^⌉ works.

14.4 Prove n → (clog n, clog n, clog n) for some constant c.

14.5 (Tiling: Bonus Problem [send idea to instructor]) A "tile" is a square with a number written next to each side. Tiles can be put anywhere in the plane by parallel translation but cannot be rotated. If two tiles are adjacent, they must have the same number associated with their shared side. We say that a region of the plane can be tiled by a finite set Σ of tiles if the given region can be cover entirely by nonoverlapping copies of tiles from Σ; there is an infinite supply of each tile. Give Σ, consider the following two questions. (a) Can the entire plane be tiled with Σ? (b) Can the upper right quadrant be tiled with Σ ? -- Obviously (a) ⇒ (b). Prove that (b) ⇒ (a). -- Hint: state a natural question (c) such that (b) ⇒ (c) ⇒ (a). The first of these implications should be straightforward; the second should follow from the König Path Lemma. -- The bonus status of this problem means I expect the idea over email. The "idea" should consist of a concise but clear statement (c).

Go to top

13. (Monday, April 28)

13.1 (Bruck-Ryser Theorem) The Bruck-Ryser Theorem states that if n is 1 or 2 (mod 4) and n cannot be written as a sum of two squares then there does not exist a projective plane of order n. Prove that the Bruck-Theorem rules out infinitely many integers n.

13.2 (Subplanes of projective planes) (a) Prove: if G₁ is a subplane of G₂ and G_i has order n_i then n₁ ≤ (n₂)^1/2.
(b) (Bonus) Find infinitely many examples where n₁ = (n₂)^1/2.

13.3 (a) Prove that the number of automorphisms of a projective plane of order n is n^{O(log log n)}. (b) Whether the number of automorphisms is n^O(1) is an OPEN PROBLEM. (c) For the case of Galois Planes prove that the number of automorphisms is indeed n^O(1).

13.4 (a) Prove that the number of automorphisms of a STS with n points is n^{O(log n)}. (b) Construct infinitely many STS where the number of automorphisms is n^{Ω(log n)}.

13.5 Create up to 6(n !)³ "isomorphic" Latin squares from one Latin square.

13.6 Let L*(n) denote the number of isomorphism types of Latin squares (number of nonisomorphic Latin squares) of order n.
Prove: log(L*(n)) ∼ log(L(n)). Do not use the Permanent Inequality.

13.7 Consider the LPs for the Covering Number and Matching Number of a hypergraph. Prove that the integral optima for these LPs are the same as their (0,1)-optima.

13.8 For an r-uniform t-regular hypergraph with n vertices, determine m (the number of edges), τ* (the fractional covering number), and ν* (the fractional matching number) in terms of r,t,n.

Go to top

12. (Friday, April 25)

12.1 If G is a non-degenerate projective plane then for any two points p₁ and p₂ there exists a line which is not incident with either p₁ or p₂.

12.2 (Gaussian binomial coefficients) (a) Count the k-dimensional subspaces of F_qⁿ. (b) Fix n and k. Then the expression you computed in (a) (called a "Gaussian biomial coefficient") should be a rational function of q (quotient of two polynomials). Evaluate its limit at q → 1. The result should be rewarding for its simplicity.

12.3 Prove that the Galois Planes are self-dual, that is, the dual of a Galois Plane G is isomorphic to G.

12.4 Put homogeneous coordinates on the points and lines of the Fano Plane.

12.5 (Pál Erdős, Alfréd Rényi, Vera T. Sós, 1966) A "friendship graph" is one in which every pair of distinct vertices has a unique common neighbor. (a) Find infinitely many friendship graphs. (b) What is the diameter of a friendship graph? (c) Reduce the statement that "all friendship graphs are flowers" to a clearly stated statement about finite projective planes. (Hint. Given a friendship graph, use it to construct a possibly degenerate projective plane.)

Go to top

11. (Wednesday, April 23)

11.1 Recall that the bipartite adjacency matrix of a bipartite graph is a (0,1)-matrix where the (i,j) entry is 1 if vertex i on the left side is adjacent to vertex j on the right side. (a) Suppose the bipartite graph G has n vertices on each side, so its bipartite adjacency matrix A is n × n. Prove: if det(A) ≠ 0 then G has a perfect matching. (b) By replacing each entry of 1 in the bipartite adjacency matrix by a distinct variable symbol, we obtain the modified bipartite adjacency matrix, B. Prove that det(B) ≠ 0 if and only if G has a perfect matching.

11.2 Let f  be a nonzero polynomial of degree d in n variables. Then if α₁,...,α_n are n independent random numbers from {1,...,Nd} then
Pr[ f (α₁,...,α_n)=0] ≤ 1/N.

11.3 Use the two preceding exercises to construct a simple and efficient randomized algorithm to decide whether or not a given bipartite graph has a perfect matching. In what sense will the algorithm "decide" the existence of a perfect matching?

11.4 A matrix A = (a_ij) is skew symmetric if a_ij = - a_ji. (In particular, the diagonal is zero.) Prove: if A is an n × n skew symmetric matrix and n is odd then det(A) = 0.

11.5 Let G be a graph with adjacency matrix A. Let us modify the adjacency matrix so we make it skew symmetric by switching the sign of every entry below the diagonal. Let us call this matrix S. (a) Prove: if det(S) ≠ 0 then G has a perfect matching. (b) Prove (by example) that the converse is false.

11.6 (Tutte matrix) Let us further modify the matrix S of the preceding exercise by replacing every entry of 1 with a distinct variable symbol, and extending this to the lower triangle to make the matrix skew symmetric. (So every entry of this matrix will be either zero, or a variable symbol, or the negative of a variable symbol.) We call the resulting matrix T the Tutte matrix of the graph. Prove: the determinant of the Tutte Matrix is not zero if and only if G has a perfect matching.

11.7 Give a simple and efficient randomized algorithm to decide whether or not a graph has a perfect matching.

11.8 Construct a pair of k × k orthogonal Latin squares for all odd numbers k ≥ 3. (This is stronger than what was stated in class, and does not require the knowledge of finite fields.)

11.9 Construct a pair of 2^k × 2^k orthogonal Latin squares for all k ≥ 2.

11.10 Prove that there exists a pair of n × n orthogonal Latin squares for all n not congruent to 2 (mod 4). (Hint: If there exists a pair of a × a and a pair of b × b orthogonal Latin squares then there exists a pair of ab × ab orthogonal Latin squares).

11.11 (Incidence geometries, projective planes) An incidence geometry is a triple G = (P,L,I) where P is a set of "points," L is a set of "lines," and I ⊆ P × L is an incidence relation. This relation is described by the incidence matrix (a (0,1)-matrix). The dual of an incidence geometry switches the roles of P and L and reverses I; this corresponds to taking the transpose of the incindence matrix.
Recall that a projective plane is an incidence geometry that satisfies three axioms: (1) there is a unique line through every pair of points; (2) every pair of lines intersects in a unique point; (3) ("nondegeneracy axiom") there exist 4 points, no three on a line.
Prove: the dual of a projective plane is a projective plane. (You need to prove that (1), (2), and the dual of (3) imply (3).)

11.12 Recall that a "degenerate" projective plane was defined as an incidence geometry which satisfies (1) and (2), does not satisfy (3), but satisfies (3'): there exist three points not on a line. Prove that all the degenerate projective planes have all but one of their points on a line. Note that these geometries are self-dual.

11.13 What is the dual of the Fano plane?

11.14 If (P,L,I) is a non-degenerate finite projective plane then (a) all lines have the same number of points; (b) all points have the same number of lines through them; (c) these two numbers are equal; let us call them n+1; we say that n is the order of the projective plane; (d) the number of points is equal to the number of lines and is n²+n+1.

11.15 (a) If L₁, L₂, ... , L_k are pairwise orthogonal n × n Latin squares then k ≤ n-1. (b) There exist n-1 pairwise orthogonal Latin squares if and only if there exists a projective plane of order n.

11.16 (a) If n is a prime number, construct n - 1 pairwise orthogonal n × n Latin squares. (b) Do the same if n is a prime power. (Hint: finite fields.)

Go to top

10. (Monday, April 21)

10.1 (LP Duality) Derive the max ≤ min inequality for LP Duality with equality constraints in the primal (corresponding to unconstrained variables in the dual). (This is the trivial direction of the Duality Theorem; yur solution should be half a line.)

10.2 (Birkhoff's Theorem) The set of doubly stochastic matrices forms the convex hull of the permutation matrices in Rⁿ². (Hint: Consider matrices with rational entries first.) Note that this means that the convex hull of permutation matrices can be defined by the n² nonnegativity constraints and a set of just 2n-1 equations.

10.3 Prove: n! /nⁿ > e^-n. (Do not use Stirling's asymptotic formula; it will yield nothing for "small" values of n. Your proof should be a half line.) Comment. The significance of this inequality in our context is that n! /nⁿ is the permanent of the uniform doubly stochastic matrix (1/n)J, where J is the n × n all-ones matrix.

10.4 Prove: the permanant of a doubly stochastic matrix is ≤ 1. Prove further that it is exactly 1 only for permutation matrices.

10.5 (Counting Latin squares) Let L(n) denote the number of n × n Latin squares. Prove : ln L(n) ∼ n²ln n.

Go to top

9. (Friday, April 18)

9.1 When is the inverse of an integral matrix integral? (Answer: When the determinant is plus or minus 1.)

9.2 (Optimal vertex) If the system of inequalities Ax ≤ b and x ≥0 defines a bounded non-empty set then for all c, there exists a vertex of this polytope that maximizes c^Tx.

9.3 Recall that a matrix is totally unimodular if all its square submatrices have deteminant +1, -1 or 0. (These submatrices are not necessarily contiguous. The entries are 1 × 1 submatrices, so the entries themselves must be 0, 1, or -1.) Prove that if A is totally unimodular and I the n × n identity matrix then the matrix [A,I] is also totally unimodular.

9.4 Prove: If A is a totally unimodular matrix and b an integral vector then for any (real!) vector c ∈ Rⁿ, the LP Ax ≤ b, x ≥ 0, max ← c^Tx has an optimal solution that is integral.

9.5 (Incidence matrix totally unimodular) Prove : The plus-minus 1 incidence matrix of a directed graph is totally unimodular.

9.6 (Equality constraints and duality) Prove that in LP duality, equality constraints correspond to unconstrained dual variables (there is no non-negativity constraint on them).

9.7 (Max-flow-min-cut via LP duality) Derive the max flow-min cut theorem from LP duality. (Use 9.5 and 9.6.)

Go to top

7. (Wednesday, April 16)

7.1 (Network flows) Let x be an s - t flow. We define the flow value as val(x) = outflow(s) - inflow(s). Prove that val(x) = inflow(t) - outflow(t).

7.2 Prove that for any (s,t)-cut (A,B) we have val(x)= x(A,B) - x(B,A).

7.3 Complete the proof of the Max-Flow-Min-Cut Theorem by showing that if A is the set of those vertices reachable from s along special paths and t ∉ A then x(A,B) = c(A,B) and x(B,A) = 0, where B is the complement of A.

7.4 Prove: if all capacities are integers then there exists an optimal flow which is integral (all flow values are integers).

7.5 Prove: the maximum number of edge-disjoint s - t path in a directed graph is the same as the minimum number of edges that block all s - t paths.

7.6 State and prove an analogous statement for the number of vertex-disjoint s - t paths.

7.7 State and prove analogous statements for undirected graphs. Note: exercises 7.5--7.7 concern Menger's Theorems, giving good characterizations of various notions of connectivity in directed and undirected graphs.

Go to top

6. (Friday, April 11) First quiz. Solve!

5. (Wednesday, April 9)

Go to top

4. (Monday, April 7)

4.1 (READING) "Finite probability spaces" except Chernoff's inequality from miniDM.

4.2 (Steiner Triple Systems) Prove: If an STS exists on n points then n ≡ 1 or 3 mod 6.

4.3 (Fano Plane) STS on 7 points.

4.4 (another starter) Construct a STS on 13 points. (Hint: 13-fold symmetry.)

4.4 (Gluing Steiner Triple Systems)

4.5 (SubSTS) Prove: If a STS with n points has a proper subSTS with k points then k < n/2.

4.6 (Isomorphism in quasipolynomial time) Prove: isomorphism of two STSs with n points can be decided in n^{O(log n)} steps.

4.7 (2-colorable set system (Erdös)) Prove: if a k-uniform set system consists of m ≤ 2^k-1 sets then it is 2-colorable.

4.8 (CHALLENGE 2-colorable set system (Erdös) Prove: (&exists; c)(if m is permitted to be as large as c k² 2^k then the inference in 4.7 becomes false.

Go to top

3. (Friday, April 4)

3.1 (Cleaning the corner) (from puzzle sheet)

3.2 READING Asymptotic notation (from miniDM lecture notes)

3.3 (increasing vs decreasing subsequences) Prove: In a sequence of distinct numbers, prove that the max length of an increasing subsequence is the same as the minimum number of decreasing decreasing sequences into which the sequence can be partitioned. (Good characterization!)

3.4 (Tutte's Theorem) In a graph G, a perfect matching exists if and only if for all subsets X of the vertex set, the number of odd components of G-X is at most |X|.

3.5 Prove the easy direction of Tutte's Theorem.

3.6 (CHALLENGE) Prove hard direction of Tutte's Theorem.

3.7 (Grötzsch's graph) Construct a graph with 11 vertices and 5-fold rotational symmetry in the plane which (a) has no triangles (b) is not 3-colorable.

3.8 (counting Latin rectangles) Let L(r,n) be the number of r × n Latin rectangles. Prove: (a) L(2,n) ∼ (n!)²/e. (b) (CHALLENGE) L(3,n) ∼ (n!)³/e³.

3.9 (counting Latin squares) Let L(n) be the number of n × n Latin squares. Observe that ln L(n) < n² ln n (trivially). Prove: ln L(n) > n² ln n/2.

Go to top

2. (Wednesday, April 2)

2.1 (König's Theorem) For bipartite graphs, τ = ν.

2.2 (König - Hall condition for SDR)

2.3 (König - Hall condition for matching one side of a bipartite graph into the other)

2.4 (edge-coloring) Prove: An r-regular bipartite graph is r-edge-colorable.

2.5 (bipartite graphs) A graph is bipartite if and only if it has no odd cycles. (This is a good charcaterization of bipartiteness!)

2.6 (SDR vs bipartite matching) Derive the SDR condition from König's Theorem.

2.6 (many bipartite matchings) Prove: a regular bipartite graph of degree r has at last r! perfect matchings.

Go to top

1. (Monday, March 31)

1.1 (Maximal vs maximum matching) Prove: If M is a maximal matching in a graph and ν is the matching number (maximum number of disjoint edges) then ν ≤ 2|M|. (Hint: prove that the vertices of a maximal matching form a cover.)

1.2 (Matching vs covering number) We proved the inequality τ ≤ 2ν where τ is the covering number of a graph (minimum number of vertices that hit every edge) and ν is its matching number. (a) Prove that this inequality is tight for every ν. (b) Make your examples (that demonstrate tightness) connected.

1.3 (Regular bipartite graphs) Prove: a regular bipartite graph of degree r ≥ 1 has a perfect matching.

1.4 (Latin rectangles) Prove: every Latin rectangle can be completed to a Latin square.

Go to top