Topics in Combinatorics

January-April 2014

Instructor: Gábor Tardos tardos@renyi.hu
Classes: Tuesday 8:30–11:00, room 301.

Office hour by appointment.

Recommended books:

  • Béla Bollobás: Modern Graph Theory
  • Reinhard Diestel: Graph Theory
  • Noga Alon, Joel Spencer: The probabilistic method

    • Grading (subject to minor change):

  • homework assignment 10x1.5%
  • midterm: 35%
  • final: 50%


    • Topics covered:

  • Jnauary 14: 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. Three construction for triangle-free graphs with high chromatic number: Zykov graphs, Mycielski graphs and shift graphs.
    Assignment: find the approximate size of smallest k chromatic Zykov, Mycielski and shift graphs (find order). Prove that all k-chromatic triangle-free graphs have Ω(k2) vertices.

  • January 21: Topological methods. Borsuk-Ulam and Lyusternik-Schnirelmann theorems. The Borsuk and Kneser graphs and their chromatic number. I give more details (pdf document) as these topics are not covered in the recommended textbooks. Find the assignments there.

  • January 28: Ramsey numbers R(k,l). Standard upper bound. Lower bound with the probabilistic method. Implications of the lower bound for R(3,k) for the existence of small triangle-free high chromatic graphs.
    Edge colorings, chromatic index, line graph, Vizing theorem.
    Assignment: 1. Use the probabilistic method to (a) lower bound R(4,k) and (b) prove the existence of (small) graphs G with g(G)≥l and χ(G)≥k (Here k and l are arbitrary, g(G) is the girth of G, i.e., the length of the smallest cycle.) 2. True or false: there exists a connected graph H and probabilities pn such that Pr[H≤G(n,pn]→0 but E[♯H≤G(n,pn)]→∞ (that is, H likely does not appear in G(n,pn), but the expected number of subgraphs isomorphic to H is huge).

  • February 4: Perfect graphs. The perfect graph theorem (Lovász, '72, proof 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. Equivalent definition for chordal through construction from complete graphs through union with complete intersection.
    Assignment: 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 K2). The graph obtained is perfect. 2. Prove as much of the following statement as you can. The following three statements on a graph G is equivalent and if they hold the graph is perfect. (a) P4 (the path with 3 edges) is not an induced subgraph of G. (b) In all induced subgraphs H of G all maximal independent sets of H meet all maximal cliques of H. (c) G can be constructed starting from K1 (a single vertex graph) and taking complements and disjoint unions. 3. (Not mentioned in class.) Is "all induced subgraphs" needed in part (b) of the last problem? In other words, is there a graph where all maximal independent sets meet all maximal cliques but the same does not hold for an induced subgraph?

  • February 11: A graph is perfect if and only if α(H)ω(H)≥|V(H)| for all induced subgraphs H. This implies the Perfect Graph Theorem. Gasparien's linear algebra proof.
    Ramsey theorem for hypergraphs. Original proof and the bound it gives for hypergraph Ramsey numbers. Erdős-Rado proof and its better bounds. (See this by Gasarch, Parrish and Sinai for a comparison of these two proofs and the Conlon-Fox-Sudakov proof giving even better bounds. Easy to read but long.)
    Assignment: 1. Find graphs G with α(G)ω(G) much larger than |V(G)| but χ(G) also much larger than ω(G). 2. Give lower bound for the Ramsey number R3(k) (triples colored by two colors, monochromatic k-subset needed). 3. Prove the Erdős-Szekeres theorem: for all k there is n 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 18: 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 25: Extremal set theory. Sperner theorem (proof using matchings and probabilistic proof), Erdős-Ko-Rado theorem (probabilistic proof from Katona). Shattered sets, Sauer lemma (Pajor's proof with number of shattered sets). You find both probabilistic proofs in the Alon-Spencer book, the Sauer lemma is not in the three recommended books, but you can find the simple proof in Wikipedia.
    Assignment (deadline: beginning of class, March 11, meanwhile a midterm on March 4): 1. Characterize Sperner families with equality in the Sperner theorem (we did this for even size universe in class, do it for odd). 2. Characterize intersecting families of k-subsets of an n-set with equality in the Erdős-Ko-Rado theorem. For n=2k lots of those families, for n>2k only the "standard" ones. Suggested proof steps: (i) characterize equality in the lemma about intervals in a cyclic order, (ii) compare cyclic orders differing in the transposition of two adjacent elements. 3. Find many (say more than 3n for large enough universe size n) families satisfying the Sauer lemma with equality.
    Detour at the end of the class: König lemma and compactness arguments. How infinite forms of Van der Waerden's theorem and Ramsey theorem are equivalent to finite forms. How "strong infinite form" is false for Van der Waerden (last assignment) but true for (regular or hypergraph) Ramsey.

  • March 4: Midterm, no class. Please turn in the the assignment from last week on March 11.

  • March 11: Vapnik-Chervonenkis dimension, ε-nets, the Haussler-Welzl theorem: for a ranges of VC-dimension d there exists a ε-net of size O(d/εlog(d/ε)). Alon's theorem that O(1/ε) size ε-nets do not exists for all planar point sets with respect to any of triangles, rectangles or lines. More detailed notes here.
    Assignment: 1. What is the VC-dimension of (a) half-planes, (b) triangles. 2. What is the order of magnitude of f(n)=max|F(S)| for planar sets S of size n, where F(S)={S∩L | L is a half-plane}. 3. Prove that O(1/ε) size ε-nets exists with respect to half-planes.
    Survey question: the syllabus calls for extremal graph theory for much of the rest of the semester, but a majority of you have studied this either this semester with Ervin Győri or earlier elsewhere. Should we still do extremal graph theory or something else (most likely more probabilistic arguments)? Vote in e-mail.

  • March 18: Weak ε-nets for convex stes, see notes. Lovász Local Lemma in simple form and in general form. Application for two-coloring of hypergraphs with bounded degree. See in Chapter 5 of the Alon-Spencer book. Embarassing correction: in the simple form we had d for maximum degree of the dependency graph and p for the maximum probability of a “bad” event and I required dp < 1/e. In the proof I used the “fact” that (1-1/d)d > 1/e. This happens to be false for every d. It is therefore better to make the condition in the lemma a little bit stronger: (d+1)p < 1/e. Then one can use the fact (1-1/(d+1))d > 1/e. The advantage of this approach is that this latter fact happens to be true.
    Assignment: 1 (Problem 3 in chapter 5 of Alon-Spencer): Given a graph G and a set S(v) of at least 10d colors for each vertex v of G. Prove that a proper vertex coloring of G exists such the color of every vertex v is coming from S(v) if the following condition holds: for every vertex v and every color c ∈ S(v) there are at most d neighbors u of v with c ∈ S(u). 2: Prove that the statement of the LLL is false for maximum degree of the dependency graph d=2 and maximum “bad” event probability 0.26. Sketch of proof: Consider a random orientation of a fixed path Pn, let each edge be directed independently (but not uniformly) in a random direction. Let the bad events be that a vertex has no edge leaving it. What is the dependency graph and what are the probabilities of the bad events?

  • March 25: 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: 1: Find a set of d-choose-2 points in d-space determining only two distinct distances. Hint: what is the distance between the incidence (characteristic) vectors of two sets? 2: Could you improve the last construction by d? (This closes cca. 1/3 of the gap to the upper bound proved in class.) 3. How about the maximal size of a point set in d-space determining three distinct distances? Derive both lower and upper bounds.

  • April 1: 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)k2k/2; improved method (G(n,1/2) with vertices removed) gives R(k,k) > (1/e)k2k/2; the Local Lemma gives R(k,k) > (21/2/e)k2k/2. Explicit Ramsey graph constructions: size Θ(k2) (trivial); size Θ(k3) (using oddtown theorem and Fisher's inequality); size kΘ(log k/loglog k) (using Frankl-Wilson theorem). Borsuk conjecture and its disproof by Kahn and Kalai. See Fox's notes.

    • Final exam sceduled at 9–11am, Monday, April 7, room 301.
    First class of Béla Bollobás starts at 1pm on the same day.