Topics in Combinatorics

January-April 2018

Instructor: Gábor Tardos tardos@renyi.hu
Teaching assistant: András Mészáros
Classes: Friday 10:00am–12:30pm, room 301.

Office hour by appointment.
Class moved from Fiday, March 16 to Wednesday, March 14. The last class is also moved from Friday March 30 to Wednesday, March 28. Time of classes (10am–12:30pm) is not affected. The class on Friday, March 23 is not moved.

The final will be on Thusday, April 12, 10am–12:30pm.

Recommended books:

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

    • Grading:
  • home work assignments 50%
  • final: 50%

    • 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 12: Origins of graph theory, basic definitions.
    Eulerian graphs.
    Planar graphs, Euler's polyhedral formula and the maximal number of edges in a plnar graph. Five-color theorem. (Four color theorem without proof.)

    1st assignment (submit on or before Wednesday, January 24):
    1. Directed graphs are similar to graphs, but the edges are given an orientation: each edge has a starting vertex (tail) and an ending vertex (head). An Eulerian walk in a directed graph should transverse every edge exactly once and should obey the orientation (should go from tail to head). Formulate a characterizatization for the existence of a closed Eulerian walk in a directed graph similar to the one we had for (undirected) graphs.
    2. Someone wants to write a long text using just the 26 letters of the alphabet such that there is no repetition of five letters. That is, the text should be x1x2...xn and we should not have xaxa+1xa+2xa+3xa+4=xbxb+1xb+2xb+3xb+4 for any 1≤a<b≤n-4. How long can this text be?
    3. Prove that all graphs G have at least χ(G) vertices of degree at least χ(G)-1.


  • January 19: 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.
    Kuratowski's theorem (w/o proof).
    Simple bounds on the chromatic number: ω(G) ≤ χ(G) ≤ Δ(G)+1. Brooks' theorem characterizing G with χ(G) = Δ(G)+1.

    2nd assignment (submit on or before Wednesday, January 31):
    1. We proved that for the number n of vertices and number e for edges in a simple planar graph one has e ≤ 3n-6. Prove a stronger inequality for simple triangle-free planar graphs. Show that your inequality is tight. (A graph G is triangle-free if K3 is not a subgraph of G.)
    2. Find the maximal number of edges of a planar graph on n vertices of girth at least k. The girth of a graph G is length of the shortest cycle of G. It is infinity if G contains no cycles. Note that as the the special case k = 4 you get back to previous problem.
    3. 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 a×b grid for the set of points.


  • January 26: [Game: who defines a larger integer?] The Ackermann function and its use in classifying large functions (and large integers).
    Many different forms of Ramsey's theorem: graphs or hypergraphs, two colors or many colors, finite or infinite.
    Elementary bound on the Ramsey number R(k,l).
    Proof of the infinite graph Ramsey theorem.

    Third assignment (submit on or before Wednesday, February 7):
    1. Apply the simplest form of Ramsey's theorem (graph, two colors, finite) to prove the following statement: (Erdős-Szekeres lemma): For every integer k≥2 there exists another positive integer n such that in any sequence of n real numbers there exist a subsequence (not necessarily consisting of consecutive elements) that is monotoneous (either increasing or decreasing). What is the bound on n you obtain from the bound on the Ramsey numbers? [In class we will see another approach to this problem giving way better (and actually tight) bounds.]
    2. Apply the hypergraph form of Ramsey's theorem to prove the following statement: (Erdős-Szekeres theorem): For every integer k≥2 there exists another positive integer n such that any set of n points in the plane with no three on a line one can find the vertices of a convex k-gon. [Again: we will see another approach to this problem in class giving better bounds.]
    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.


  • February 2: Compactness principle: assume an (infinite) set of variables have to be assigned values with each variable taking a value in a finite set and subject to an (infinite) set of constraints, where each constraint depends only on the values of a finite set of variables. Either (i) there is a way to set the variables satisfying all the constraints or (ii) there is a finite subset of the constraints that cannot be satisfied simultaneously. Proof (through König Lemma on infinite trees) for countable sets.
    Application of compactness principle to chromatic number of infinite graphs. Application to show that infinite form of (hypergraph) Ramsey implies the finite form.
    Proof of the 3-uniform hypergraph Ramsey theorem (infinite form) through a process that finds a sequence of points in an t-edge-colored infinite complete 3-uniform hypergraph such that the color of the hyperedge formed by tree verteces in the sequence is determined by the the first of the three vertices.
    Construction of triangle-free high-chromatic graphs: the Mycielski graphs.

    Fourth assignment (submit on or before Wednesday, February 14):
    1. Consider the false statement in the last problem of the third assignment and add a third possibility (a well defined coloring of the edges that is neither monochromatic nor rainbow) to make it true. Prove this statement. [Can you make a similar statement for infinite graphs?]
    2. In class we turned the infinite proof of the 3-uniform Ramsey into an upper bound on the corresponding finite Ramsey number. In particular we proved that if the hyperedges of a complete 3-uniform hypergraph on Nk vertices is 2-colored, then one can find a monochromatic k-set of vertices, where Nk is obtained by a "tower" of 2k 4's (iterated exponantiation). Modify the proof in a way that the sequence of vertices you find satisfies a weaker property: now the color of the hyperedge formed by three vertices in the sequence is determined by the first two of the three vertices (not the first one as above). What bound does this modified proof give for the hypergraph Ramsey number Nk above?
    3. 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).(Instead of specifying how large the monochromatic set should be we specify that it should contain at least as many elements as the value of its smallest element.)


  • February 9: (Class given by teaching assistant András Mészáros.) The random graph G(n,p). 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. Lower bound on the Ramsey numbers R(k,k) and R(3,k). The existence of small high-chromatic triangle-free graphs. The existence of high chromatic high girth graphs (Erdős). Basic uses of first and second moment techniques, Markov's inequality and Chebyshev's inequality. Threshold probability for the appearence of a triangle in G(n,p).

    Fifth assignment (submit on or before Wednesday, February 21):
    1. 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, looking for a monochromatic k-subset).
    2. Find the threshold probability for 4-cliques to appear in the random graph G(n,p).
    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 (that is, with probability tending to 1), G(n,pn) is H-free.


  • February 16: 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.
    Two version of the Lyusternik-Schnirelmann theorem and their equivalence to the Borsuk-Ulam theorem.

    Detailed notes of the part of the lecture about the Borsuk-Ulam theorem will come next week. No assignment this week.


  • February 23: The Borsuk graph Bkδ, the Kneser graph KG(n,k) and their chromatic number. See my notes from last year.
    The Erdős-Szekeres lemma on monotone sequences. The Erdős-Szekeres theorem on points in convex position. How Ramsey theory gives some results (see problems 1 and 2 of assignment 3) and how methods more attuned to the problem give stronger results.
    On 3-uniform hypergraph Ramsey numbers and problem 2 in assignment 4. See my notes.

    Sixth assignment (submit on or before Wednesday, March 7):
    1. We used subsets of the sphere Sk that get ε close to every point of the sphere. Prove that such finite sets exist for every ε>0 and k. Can you give upper and lower bounds for the cardinality of the smallest such set?
    2. 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.
    3. We proved that the Borsuk graph Bkδ has chromatic number at least k+2. Find explicit δ<2 for which equality does not hold and another δ<2 with which equality holds.


  • March 2: Results from extremal combinatorics. For set systems: Sperner's Theorem, LYM inequality and the Erdős-Ko-rado Theorem. For graphs: Turán's Theorem, the Erdőos-Stone-Simonovits Theorem (w/o proof) and the extremal function of the forbidden graph C4 (Erdős).

    Seventh assignment (submit on or before Wednesday, March 15):
    1. What are the Sperner systems that satisfy the LYM inequality with equality?
    2. I did not have time in class to work out the exact extremal function for C4 beyond that it is some constant times n3/2. What lower and upper bounds can you derive from the techniques presented in class (double counting paths of length 2 and bipartite point-line incidence graphs of finite planes)? Do not worry about lower order terms, concentrate only on the constant in front of n3/2.
    3. We call a set system 2-intersecting if every pair of sets contain at least 2 common elements. A simple way to obtain 2-intersecting families is to fix two elements of the base set and consider all the subsets of the base set of a certain size containing both. Let us call these the simple 2-intersecting families. Here is plausible generalization of the Erdőos-Ko-Rado Theorem:
    Among the 2-intersecting families consisting of m-subsets of a base set of size n ≥ 2m the largest ones are the simple 2-intersecting families.
    Prove that this statement is false for n=8, m=4.


  • March 9: Construction procedure for chordal graphs. Chordal graphs are perfect. 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 are perfect. König's theorem equivalently stated as the perfectness of the complements of bipartite graphs. Geneson's linear algebra 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)|.

    Eighth assignment (submit in email on or before Wednesday, March 21):
    1. We saw in class that chordal graphs can be constructed from complete graphs by repeated application of a "gluing procedure", namely constructing G = G1∪G2 from G1 and G2, where G1∩G2 is a complete graph. In this procedure G1 and G2 can be either complete graphs or graphs we have constructed earlier. Prove that we can restrict G1 to be a complete graph in every step and still we can obtain all chordal graphs. G2 can still be either a complete graph or a graph constructed earlier.
    2. (This is something I wanted to cover in class but ran out of time.) A partial order is any binary relation < on a base set that is irreflexive (i.e., x<x never holds) and transitive (i.e., x<y and y<z imply x<z). Here we assume the base set is finite. A partial order determines a comparability graph: the vertices are the elements of the base set and two are adjacent if and only if one is smaller than the other.
    a. Color each vertex of a comparability graph by the length of the longest increasing chain (in the partial order) ending there. Prove that this is a proper coloring.
    b. Prove that comparability graphs are perfect.
    c. Deduce the Erdős-Szekeres lemma on monotone sequences from part b.
    d. Deduce the following result from part b and the perfect graph theorem:
    Dilworth's Theorem. The base set of a partial order can be partitioned into k chains, where k is the size of the largest antichain. Here a chain is a set of pairwise comparable element, while an antichain is a set of pairwise incomparable elements.


  • Mach 14: 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). Applications to explicit Ramsey graph constructions and the refutation of Bursuk's conjecture on spliting point sets into parts of smaller diameter (Kahn and Kalai). This lecture was based on Jacob Fox's 2009 combinatorics course at MIT. See his excellent notes here, here and here.

    Ninth assignment (submit in email on or before Wednesday, March 30):
    1: How large can be a set system over an n element base set with all pairwise intersections even? Give lower and upper bounds. The closer to each other the better, but they don't have to match.
    2. What is the maximal size of a point set in d-space determining three distinct distances? Derive lower and upper bounds close to each other using similar techniques to the ones seen in class.
    3. Find lower and upper bounds (say, within a constant factor from each other) on the maximal size of a set system over an n element base set such that the size of pairwise intersections are divisible by 6, but the size of no set is divisible by 6.


  • March 21: Hypergraph 2-coloring. A k-uniform hypergraph with less than 2k-1 hyperedges is 2-colorable. (Proof: simplest form of the probabilistic method.)
    Tic-tac-toe-type games and Maker-Breaker games on hypergraphs, their connection to each other and to 2-colorings. The Erdős-Selfridge theorem: Breaker wins on a k-uniform hypergraphs with fewer than 2k-1 edges. (Proof by explicit winning strategy for Breaker: minimize expected number of winning sets obtained by Maker if unclaimed vertices are distributed uniformly randomly.)
    Lovász Local Lemma: bad events and dependency graph (each bad event is independent from the collection of non-neighbors). Simplest form: if p(Δ+1) ≤ e-1 (where Δ is the maximal degree of the degendency graph and p is the maximal probability of a bad event), then all bad events are avoided with positive probability.
    Consequence of LLL: if the maximal degree of a k-uniform hypergraph is at most 2k/(6k), then the hypergraph is 2-colorable.

    Tenth and final assignment (submit in email on or before Wednesday, April 4 - EXTENDED to Sunday, April 8):
    1. Prove that the Erdős-Selfridge theorem is tight by finding a k-uniform hypergraph with exactly 2k-1 edges in which Maker wins. Find one for every k. Recall that Maker starts the game.
    2. A simpler definition of the dependency graph would be connecting two bad events if they are not independent. Show that no version of LLL is possible with such a definition by proving the following statement:
    For every ε > 0 there exists a probability space and a collection of pairwise independent bad events of probability at most ε such that there is no way to avoid all of them.
    3. The common generalization of the two statements covered this class would be the following. Braker wins the Maker-Braker game on a k-uniform hypergraph if the maximal degree of the hypergraph is at most f(k). It is conjectured that such a statement holds for some exponential function f. Unfortunately, only the (much weaker) statement with f(k)=k/2 is known. Prove this result by giving Breaker the following explicit winning strategy: Find a partition of the vertex set into pairs satisfying a certain property and then whenever Maker claims one of the vertices in such a pair claim the other one. (What property should the partition satisfy? Why must there exist such a partition?)


  • March 28: Three forms of the Lovász Local Lemma with proof. Applications of the LLL.
    The inclusion-exclusion formula and two applications: (i) the probability of a random parmutation having no fixed point and (ii) the limit probability that the random graph G(n,c/n) contains a triangle.

    No assignment for this class.

    Have questions? Need consultation? Write.