Topics in Combinatorics

January-April 2015

Instructor: Gábor Tardos tardos@renyi.hu
Classes: Tuesday 2:00–4:30pm, room 310/A.

Office hour by appointment.

Recommended books:

Béla Bollobás: Modern Graph Theory

Reinhard Diestel: Graph Theory

Noga Alon, Joel Spencer: The probabilistic method

Normal grading (subject to major change in favor of assignments):

homework assignment 10x1.5%

midterm: 35%

final: 50%

Midterm on March 3 during regular class hours.
Final at 12–2:30pm, April 10, 2015 in the usual room (310/A).

Assignments given after the February 17 and February 24 classes are due on Sunday, March 8. All later assignments due on the next Sunday, five days after the class at which they are assigned. These assignments will be somewhat easier on popular demand.

Assignment problems are intended for you to solve alone. If you get stuck, ask me (it's "free" - no deductions for hints I may give). Some of the problems are "standard" and could be looked up in a library or on the internet. Please don't do so. If you did find the solution in a book or online, or you discussed it with somebody else, simply acknowledge this fact.

Topics covered:

Jnauary 13: Basic definitions (simple graph, clique, stable set, path, cycle, proper coloring, clique number, chromatic numbe, etc.) Simple bounds on the chromatic number: ω(G) ≤ χ(G) ≤ Δ(G)+1. Brooks' theorem characterizing G with χ(G) = Δ(G)+1. Planar graphs, Euler's (polyhedron) formula and the maximal number of edges in a planar graph. Four color theorem (w/o proof), five color theorem (with proof).
Assignment: 1. What is the minimal number of edges in a k-chromatic graph? 2. What are the k-chromatic graphs with the minimal number of edges? 3. (not mentioned in class) An interval graph is a graph whose vertices can be represented by intervals on a line and two are connected if and only if the intervals intersect. Prove that ω(G)=χ(G) for any interval graph G.

January 20: Kuratowski's theorem (w/o proof). Crossing number of a graph. The crossing number lemma of Ajtai-Chvatal-Newborn-Szemerédi and Leighton. Székely's method: application of the crossing number lemma to prove the Szemerédi-Trotter theorem on point-line incidences in the plane.
Three explicit constructions of triangle-free graphs with large chromatic number: the Zykov graphs, the Mycielski graphs and the shift graphs.
Assignment: 1. Characterize graph drawings with the number of crossings equal to e-(3n-6). Note: e = number of edges, n = number of vertices. Hint: the plane drawings with e=3n-6 is a special case. This special case is characterized by "plane drawing with all faces triangles". 2. For what values of n and e do you have a graph G with cr(G)=e-(3n-6)? 3. Prove that the crossing number lemma is tight for all possible n and e (apart from the constant factor). That is, show that for n and e with 4n ≤ e ≤ (n-choose-2) one has a graph G with n vertices and e edges and cr(G) = O(e³/n²). 4. Prove that among n points in the plane there are O(n^4/3) pairs in unit distance. Hint: use Székely's method. 5. Approximate the number of vertices of the first k-chromatic Zykov/Mycielski/shift-graphs and find the relative order (i.e., which construction is more efficient). 6. Prove that any triangle-free k-chromatic graph has Ω(k^2) vertices.

January 27: Topological methods. Sperner's lemma and Brouwer's fixed point theorem, see the excellent notes of Jacob Fox. (These notes will be also used later where appropriate.) Borsuk-Ulam theorem and Tucker's lemma. Neither proved, the latter just mentioned, but the equivalence of three distinct forms of the Borsuk-Ulam (Lyusternik-Schnirelmann) proved. The infinite and the finite Borsuk graphs, and lower bound on their chromatic number. See these notes.
Assignment: 1. We proved that the chromatic number of the Borsuk graph B^k_δ is at least k+2 for any δ<2. Find an explicit value of δ for which equality holds. 2. We constructed finite graphs with high chromatic number and no short odd cycles: the finite Borsuk graphs. Make it explicit and estimate the number of vertices in a C₃, C₅, C₇-free k-chromatic finite Borsuk graph. It is enough to give an upper bound of the order of the magnitude (here 3-5-7 are fixed, k goes to infinity). 3. Consider the following variant of the shift graphs: vertices are ordered pairs (i,j) with 1≤i,j≤n, i≠j. We have an (undirected) edge between (i,j) and (k,l) if and only if j=k or l=i. Prove that the vertices can be partitioned into two sets, such that the induced subgraph on either set is isomorphic to the "standard" shift graphs considered in class. Estimate the chromatic number of this graph as a function of n. (Give a proper coloring with only slightly more colors than the corresponding standard shift graphs.)

February 3: Kneser graphs, Kneser conjecture (Lovász, 1979). See notes. Ramsey theory: Three forms of the Ramsey theorem, the proof of the simplest form giving R(k,l)≤(k+l-2)-choose-(l-1). Here R(k,l) is the Ramsey number, the smallest number R such that every graph on R verices has a clique of size k or an independent set of size l.
Assignment: Let H be the set of vertices in KG(m,k) that do not contain two neighboring integers (recall that vertices are k-subsets of [m]) and let G=KG[H] be the subgraph induced by H. 1. Prove that χ(G)=m-2k+2 by repeating Greene's argument for a specific set S={x₁,...,x_m}, where x_i=(-1)ⁱy_i/||y_i|| and y_i=(1,i,i²,...,i^u). 2. Is it true for (a) the Kneser graph KG(m,k) or for (b) its subgraph G defined above that you can decrease its chromatic number by removing just a single vertex from the graph? If yes, does every vertex work in every case? 3. True or false: For every k there is an n such that no matter how you color the edges of the complete graph K_n with an arbitrary number of colors one either has a monochromatic clique of size k or a rainbow clique of size k. Here rainbow means that all the edges have distinct cololors.

February 10. The general (hypergraph) Ramsey theorem with two proofs. The random graph G(n,p) and lower bound for the (graph) Ramsey number R(k,k) using the random graph G(n,1/2). Improved version of this probabilistic method with “removing problems” and how it gives a lower bound for R(3,k).
Assignment: 1. Find good lower bound for R(3,l) by substituting a reasonable choice for n and p in the general bound we had in (the last minute of the) class. (You do not have to find the very optimal choice, if your choice gives a lower bound 100 times lower than the best choice it is still fine.) 2. Apply the bound you obtained in the first problem to prove that there are small k-chromatic triangle-free graphs. How small are the graphs you found? 3. Prove the Erdős-Szekeres theorem: for all k>2 there is n>k such that among n points in the plane with no 3 on a line one can always find the vertices of a convex k-gon.

February 17: Van der Waerden, Hales Jewett, Szemerédi and density Hales Jewett theorems. Implications among them. A tricky proof of the Hales Jewett theorem (Szemerédi and density Hales Jewett theorems not proved). See detailed notes and the assignment in this pdf file.

February 24: Three results from extremal set theory: Sperner's theorem, the Erdős-Ko-Rado theorem and the Sauer-Shelah lemma.
Assignment (due on March 8 together with previous assignment): 1. A family of sets is called 2-intersecting if every pair of sets from the family have at least two common elements. Fix a base set S and two elements x,y of S. All the subsets of S containing both x and y form a 2-intersecting family. Prove that this not the largest one, that is, (unless S is too small) there is another 2-intersecting family of subsets of S that is larger. 2. Consider the family of the sets of size less than d in a base set S. This family shatters no set of size d and by the Sauer-Shelah lemma all larger families do. Find many other such families, namely families of VC-dimension less than d with the same maximal size. Here ‘many’ should be exponential in the size of S (or, for extra credit, at least 3^|S|, for large enough |S|). 3. What is the VC-dimension (size of largest shattered set) of the family of all open half-spaces in the plane. For extra credit: what is the VC dimension of all open circular disks in the plane?

March 3: Midterm.

March 10: Perfect graphs. The perfect graph theorem (Lovász, '72, proof possibly next time) and the strong perfect graph theorem (Chudnovsky, Robertson, Seymour, Thomas, 2006, no proof in this course). Comparability graphs are perfect. König's theorem and Dilworth's theorem and how the perfect graph theorem implies them. Chordal graphs are perfect.
Assignment (due by Sunday night):
1. Lovász used the following statement in his proof of the perfect graph theorem (we will use a different approach). Do the opposite: give a simple proof of this statement using the perfect graph theorem. Statement: Let x be a vertex of a perfect graph G and add a new vertex x' to G that is adjacent to x and all neighbors of x (i.e., replace x with K₂). The graph obtained is perfect.
2. Prove that if G₁ and G₂ are induced subgraphs of G, both are chordal, G₁∪G₂=G and G₁∩G₂ is a clique, then G is also chordal.
3. The statements (a-c) hold for the same graphs G. Prove that if they (all) hold, then G is perfect. For extra credit prove (part of) the equivalence of the three statements. (The graphs satisfying these statements are called cographs).
(a) P₄ (the path with 3 edges) is not an induced subgraph of G.
(b) In all induced subgraphs H of G all (containment) maximal independent sets of H meet all (containment) maximal cliques of H.
(c) G can be constructed starting from K₁ (a single vertex graph) and taking complements and disjoint unions.

March 17: k-uniform hypergraph with less than 2^k-1 hyperedges is 2-colorable (proof: simplest form of the probabilistic method). Stronger result from Erdős and Sefridge: The Maker-Breaker game is won by the Breaker if the winning sets are size k and there are fewer than 2^k-1 of them (proof by fear function). If every hyperedge intersects at most 2^k-1/e-1 other hyperedges, then the hypergraph is 2-colorable. Proof: Lovász Local Lemma.

Three forms of LLL. In each form A_i are the “bad events” of a probability space and we conclude that the probability of avoiding them all is positive. These events are the vertices of the “dependency graph” G such that A_i is independent from the collection of its non-neighbors.
In the first form of LLL we assume (Δ(G)+1)max(Pr[A_i]) ≤ 1/e.
In the second form we assume Pr[A_i]+∑_j~iPr[A_j] ≤ 1/e for all i. Here j~i means A_j and A_i are neighbors in G.
In the third form we assume there exist real numbers 0< x_i<1 such that Pr[A_i]≤x_iΠ_j~i(1-x_j) holds for all i.
If I did not convince you that the proof of the third form was easy find it in Wikipedia (less than a screenfull). The deduction of the second form from the third was supposed to be in the assignment, but I found three better problems. Here is the key to the deduction anyway: take x_i=1-1/(1+ePr[A_i]).

Assignment:
1*. Can you modify the proof of the Erdős-Sefridge theorem so that it applies to games where Maker takes 2 vertices of the hypergraph at every turn but Breaker still takes just one? Prove that if the number of winning sets is small Breaker still wins (here small will naturally be smaller than the original thrashold of 2^k-1).
2. Let k and n be positive integers. Prove that VdW(k,c) > c^k/(3ck), that is, with n below this threshold [n] can be colored with c colors such that no k term arithmetic progression is monochromatic.
3. A simpler definition of the dependency graph would be connecting two bad events if they are not independent. Prove that the LLL with this definition of the dependency graph does not hold by deducing from it the false statement that the Fano plane is 2-colorable. (The Fano plane is the seven point projective plane over the 2 element field, and here we consider it as hypergraph with the lines being the hyperedges.)

March 24: Linear algebra techniques in combinatorics. Oddtown theorem (Berkelamp), Fisher's inequality, bound on the size of sets in Euclidean d-space determining only two distinct distances, Frankl-Wilson theorem and its modular form. This lecture was based on Jacob Fox's 2009 combinatorics course at MIT. See his excellent notes here and here.
Last assignment (due by the last class):
1: We saw that the indicator vectors of two element sets form a large 2-distance set in n-space. Find an even larger set closing part of the gap toward the upper bound.
2. How about the maximal size of a point set in d-space determining three distinct distances? Derive both lower and upper bounds.
3.In this problem we consider set systems over an n element base set. (a) Prove a linear upper bound on the size of a set system if the size of pairwise intersections are divisible by 6, but that size of no set is divisible by 6. (b) Give an example of an exponentially large family where each pairwise intersection is even and so is each set size.

March 31: A graph is perfect if and only if α(H)ω(H)≥|V(H)| for all induced subgraphs H (Lovász). This implies the Perfect Graph Theorem. Gasparien's linear algebra proof.
Lower bound on the Ramsey number R(k,k) using the probabilistic method: simplest method (random graph G(n,1/2) “as is”) gives R(k,k) > (2^-1/2/e-o(1))k2^k/2; improved method (G(n,1/2) with vertices removed) gives R(k,k) > (1/e-o(1))k2^k/2; the Local Lemma gives R(k,k) > (2^1/2/e-o(1))k2^k/2.
Explicit Ramsey graph constructions: size Θ(k²) (trivial); size Θ(k³) (using oddtown theorem and Fisher's inequality); size k^{Θ(log k/loglog k)} (using both versions of the Frankl-Wilson theorem).
Borsuk conjecture and its disproof by Kahn and Kalai.
See Fox's notes.

Final exam sceduled at 12–2:30pm, April 10, 2015 in room 310/A.

Have questions? Need consultation? Write.