Topics in Combinatorics

January-April 2017

Instructor: Gábor Tardos tardos@renyi.hu
Classes: Friday 12:00–2:30pm, room 301.

Office hour by appointment.
All class after February 21 moved from Tuesday to Friday, 12–2:30pm.
Last class March 31, 12 noon

Final on Monday, April 10, 9–11:30am

Recommended books:

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

    • Grading:

  • homework assignments 40%
  • final: 60%

    • 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 acknowledge this fact.


    Topics covered:

  • January 10: Origins of graph theory, basic definitions (degree of vertces, max degree, clique, clique number, proper coloring, chromatic number, etc.).
    Eulerian graphs.
    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 plnar graph. Five-color theorem. (Four color theorem without proof.)
    Mycielski's construction of high chromatic triangle-free graphs.

    1st assignment (submit on or before Sunday, January 15):
    1. State and prove a necessary and sufficient condition for the existence of Eulerian walk in directed graphs. (An Eulerian walk traverses every directed edge exactly once in the correct direction and returns to the point where it started.)
    2. Prove that there exists a sequence of digits 0-9 such that all 100000 patterns of 5 digits shows up in it exactly once as a subsequence of 5 consecutive digits.
    3. Prove that all graphs G have at least χ(G) vertices of degree at least χ(G)-1.


  • January 17: 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.
    Shift graphs and their chromatic number.

    2nd assignment (submit in email on or before Sunday, January 29, extended to Tuesday, February 7):
    1. Prove that the crossing number lemma is tight for all possible n and e (apart from the constant factor).
    2. Prove that the Szemerédi-Trotter theorem is tight for all possible number of points and lines (apart from the constant factor). Hint: use an appropriate axb grid for the set of points.
    3. Prove that all C4-free induced subgraphs of a shift graph are 3-colorable. (What's the case with non-induced subgraphs? I don't know, but I am interested.)
    4. Here is a modified shift graph S'n: The vertices are the triples (i,j,k) with 1≤i<j<k≤n, and there is an edge between (i,j,k) and (j,k,l) for any 1≤i<j<k<l≤n. What is its chromatic number?
    5. Prove that among n points in the plane there are O(n4/3) pairs in unit distance. Hint: use Székely's method.


  • January 24: Ramsey theorem, finite, infinite, graph, hypergraph versions.
    Connection between the finite and the infinite statements: the compactness principle (proved – through König's lemma – only for a countable number of variables).
    Upper bounds on the graph and hypergraph Ramsey numbers. Lower bound for R(k,k) using the probabilistic method.
    The two versions of the probabilistic method (a) take a random graph and prove that with positive probability it has the desired properties and (b) take a random graph and modify it slightly so that it has the desired properties.

    3rd assignment (submit in email on or before Tuesday, February 7):
    1. Prove the following statement (Paris-Harrington theorem): For all positive integers r and k there exists n>k such that for all 2-colorings of the r-subsets of the set H={k,k+1,k+2,...,n} there exists a monochromatic subset S of H with |S|≥min(S).
    2. Prove the following statement (Erdős-Szekeres theorem): For every integer k≥3 there exists n such that among any set of n points in the plane with no three on a line one can find the vertices of a convex k-gon.
    3. (a) Prove that the following statement is false: For every positive integer k there exists n such that for any coloring of the edges of Kn (with an arbitrary number of colors) one finds either a monochromatic k-clique or a rainbow k-clique. We call a clique rainbow if all of its edges have distinct colors.
    (b) Make the statement true by allowing just one more type of k-cliques and prove this statement.
    4. Apply the (simplest form of) the probabilistic method to prove a lower bound on the Ramsey number R(3)(k,k) (3-subsets colored by two colors).
    5. (a) Compute or estimate the size of k-chromatic Mycielski and shift graphs.
    (b) Prove quadratic lower bound on the size of any triangle-free k-chromatic graph.


  • January 31: Lower bound on the Ramsey number R(3,k) and its use to prove the existence of small high-chromatic triangle-free graphs. Basic uses of first and second moment techniques, Markov's inequality and Chebyshev's inequality. Threshold function for triangles and connectednes in the random graphs G(n,p). Inclusion-exclusion and the probability that a random parmutation is fixod-point free.

    4th asignmet (submit in email on or before Sunday February 12):
    1. Find the threshold function for 4-cliques to appear in the random graphs.
    2. Prove the existence of graphs with cromatic number k and no triangle or C4 subgraphs.
    3. Find a connected graph H and probabilities pn such that the expected number of subgraphs isomorphic to H in the random graph G(n,pn) tends to infinity, yet almost surely, G(n,pn) is H-free.


  • February 10: Topological methods. Sperner lemma on simplicial decompositions of a simplex and how it implies Brower's fixed point theorem. See excellent notes of Jacob Fox. The Borsuk-Ulam theorem and its combinatorial counterpart, the Tucker Lemma. Consequences of the Borsuk-Ulam theorem: the ham sandwich theorem. A discrete geometric application: Given m-sets of points S1,...,Sn in Euclidean n-space in general position one can find m pairwise disjoint simplices, each having one vertex in each of the sets Si.


  • February 14: Two version of the Lyusternik-Schnirelmann theorem and their equivalence to the Borsuk-Ulam theorem. The Borsuk graphs, the Kneser graphs an their chromatic number. See these notes.

    5th assignment (submit in email on or before on or before Sunday Februar 26, extended to Wednesday, March 1):
    0. (not really a mathematical problem) Draw the graph KG(5,2).
    1. We saw that the Kneser graphs are edge-transitive. (a) Find which Kneser graphs are 2-edge-path transitive, i.e., when every path of length 2 can be brought to every other path of length 2 by a automorphism of the graph. (b) Show that these graphs are also 3-edge-path transitive.
    2. Deleted.
    3. We proved that the Borsuk graph Bkδ has chromatic number at least k+2. Find explicit δ<2 with which equality holds.
    4. The inclusion-exclusion formula gives the size of the union of finite sets from the sizes of intersections of subsets. Prove that if you truncate the formula by considering only the sizes of the intersections of at most k sets, you get a lower or upper bound on the size of the union depending on k.


  • February 21: Elements of extremal combinatorics. Results from extremal set theory: Sperner's theorem, Erdős-Ko-Rado theorem and Sauer-Shelah lemma. Results from extremal graph theory: Mantel's theorem (on triangle-free graphs), Turán's theorem (on Kk-free graphs) and the Kővári-Sós-Turán theorem (as it applies to C4-free graphs).

    6th assignment (submit in email on of before Wednesday, March 8):
    1. Find all maximal size Sperner systems on a fixed base set of odd size. We did this in class for even size.
    2. Find all maximal size pairwise intersecting families of k-subsets of an n-set. Hint: use these steps. (i) Find the values of the the parameters k and n, where there are very many extremal families. If there are not many: (ii) Characterise families with equality in the Katona lemma on intervals of cyclic orderings. (iii) Compare two cyclic orderings that differ only by a transposition of a pair of neighbors.
    3. Find many maximal size VC-dimension-d families of subsets of an n-set. The more, the better, try to reach at least 3n for any d≥1 and large enough n.
    4. Find any maximal family of VC-dimension d that is not maximal size. You choose n and d and a family of subsets of an n-set of VC-dimension d such that if you add a set to the family the dimension increases but the size of the family does not reach the bound in the Sauer-Shelah theorem.
    5. (a) We found the VC-dimension of the family of open half-planes in the plane to be three. Find the order of magnitude of the growth function of this family. (b) Find the VC-dimension of the family of open circular disks in the plane. Can you say something about the growth function here? (Recall that the growth function f for a family F is defined as f(n) being the maximum cardinality of the set {X∩S|X∈F} for all n-sets S.)


  • March 3: Van der Waerden, Hsles-Jewett, Szemerédi and density Hales-Jewett theorems. Implications among them. Proof of the Hales-Jewett theorem (Szemerédi and density Hales-Jewett theorems not proved). Behrend's construction for 3-term arithmetic progression-free sets. See detailed notes.
    The definition of the Ackermann function as A1(n)=2n, Ak+1(0)=1, Ak+1(n+1)=Ak(Ak+1(n)).
    Erdős-Szekeres cap-cup theorem and the construction showing that it is tight.

    7th assignment (submit in email on of before Wednesday, March 15):
    1. We saw VdW(k,r)≤kHJ(k,r). Modify the argument to get a better bound (without the exponential increase). What about the similar connection between Sz(k,r) and DHJ(k,r)?
    2. We used a doubly exponential function of z for the number of colors in the term defining w in Lemma 1. Modify the argument to get a simply exponential function in the same place.
    3. The Van der Waerden theorem can be equivalently stated as follows: If we color all the natural numbers with finitely many colors there will always be monochromatic arithmetic progressions of arbitrary size. Recall that in the case of Ramsey theorem, we could guarantee not only arbitrary size monochromatic cliques but also infinite monochromatic cliques. Can we also guarantee an infinite monochromatic arithmetic progression if the natural numbers are colored by finitely many colors?
    4. extended—try at least for HJ(3,r) Try to approximate the bound this specific inductive proof gives to HJ(k,2). In this problem you don't have to be precize, but try to reasonably guess how big the obtained bound gets using the values of the Ackermann function as your metric.
    5. Find good setting for the numbers m and t in the Behrend's construction that and find the size of the 3-term AP-free set as a funtion of n. It should be n1-o(1).


  • March 10: The perfect graph theorem (Lovász, 1972) and the strong perfect graph theorem (Chudnovsky, Robertson, Seymour, Thomas, 2006, no proof in this course). Bipartite graphs, comparability graphs are perfect. König's theorem and Dilworth's theorem and how the perfect graph theorem implies them. Chordal graphs are perfect. Geneson's proof of this slightly stronger version of the perfect graph theorem: If G is not perfect but all its proper induced subgraphs are perfect, then α(G)ω(G)<|V(G)|.

    8th assignment (submit in email on or before March 22):
    1. Prove that if G is chordal if and only if it has a perfect elimination order (i.e., a linear order on the vertices where the "forward neighbors" of any vertex form a clique). One direction should be easy from what we had in class, for the other direction prove that if G is chordal and K is a clique in G not containing all vertices, then G has a vertex outside K whose neighborhood is a clique.
    2. The statements (a-c) hold for the same graphs G. Prove that if they (all) hold, then G is perfect. Prove as much of the equivalence of the three statements as you can. (The graphs satisfying these statements are called cographs).
    (a) P4 (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 K1 (a single vertex graph) taking complements and disjoint unions.


  • March 17: Linear algebra techniques in combinatorics. Oddtown theorem (Berlekamp), Fisher's inequality, Frankl-Wilson theorem (modular and non-modular forms). Point sets in d-space determining only two distinct distances (construction and upper bound). This lecture was based on Jacob Fox's 2009 combinatorics course at MIT. See his excellent notes here, here and here.

    9th assignment (submit in email on or before March 29):
    1: We saw how to construct n-choose-2 points in n-space determining only 2 distances. Find an even larger set closing a substatial 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 using similar techniques to the ones seen in class.
    3. Find lower and upper bounds on the maximal size of a set system over an n element base set such that (a) the size of pairwise intersections are divisible by 6, but the size of no set is divisible by 6. Or (b) each set size and each pairwise intersection size is divisible by 6. (Find "reasonable" bounds, do not shoot for the exact maximum.)


  • March 24: k-uniform hypergraph with less than 2k-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 2k-1 of them (proof by fear function). If every hyperedge intersects at most 2k-1/e-1 other hyperedges, then the hypergraph is 2-colorable. Proof: Lovász Local Lemma.

    Three forms of LLL. In each form Ai 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 Ai is independent from the collection of its non-neighbors.
    In the first form of LLL we assume (Δ(G)+1)max(Pr[Ai]) ≤ 1/e.
    In the second form we assume Pr[A_i]+∑j~iPr[Aj] ≤ 1/e for all i. Here j~i means Aj and Ai are neighbors in G.
    In the third form we assume there exist real numbers 0< xi<1 such that Pr[Ai]≤xiΠj~i(1-xj) holds for all i.
    The second conditon clearly implies the first, the third condition implies the second with the choice xi=1-e-ePr[Ai]. So it is enough to prove the LLL with the third condition.
    The main step of the proof is showing that Pr[Ai|C]≤xi, where the condition C is avoiding an arbitrary set of bad events.

    10th (and last) assignment (submit in email on or before April 5):
    1. Can you modify the statement and 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? Modify the weight function in such a way that you can still give Breaker a winning strategy in any game with a bounded number of winning sets, all of size k. Your bound will be smaller than in the original theorem, but should nevertheless be exponential in k.
    2. Let k and n be positive integers. Prove that VdW(k,c) > ck/(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 finding three pairwise independent bad events (in the probability space of your choice), each of probability 1/2 such that one cannot avoid all three. Harder version: find many pairwise independent events of probability 1/k (k arbitrary) that cannot all be avoided. Hint: Recall that the events that two sets are monochromatic in a uniform random coloring are independent unless the sets have more than one elements in common.


  • March 31: Small additions to earlier topics. Applications of the Lovász Local Lemma: independent transversals of bounded degree graphs (if each vertex class is at least 2eΔ), satisfiability of k-CNF formulae with few (less than 2k/(ek)) appearences of each variable. Borsuk's conjecture and its disproof by Kahn and Kalai. The calculation of lim Pr[G(n,c/n) is triangle-free] by inclusion exclusion.


    • Have questions? Need consultation? Write.