Advanced Combinatorics

  • Instructor: dr András Gyárfás
  • Contact: gyarfasa at gmail dot com
  • Prerequisites: A course in discrete mathematics (or combinatorics or graph theory) is required. A minimum knowledge of discrete probability and linear algebra is useful for Sections 4 and 5).
  • Text: The course is based on handouts of the instructor.

Course description: The basic concepts of Hypergraph Theory are introduced. Using this framework, classical and relatively new results are discussed from the theory of finite set systems. The emphasis is on studying several successful proof methods including the Linear Algebra and the Probability methods.
BASIC MENU:

1.1. Definitions. Notations, Incidence matrix, Duality, Intersection graph.
1.2. Examples of hypergraphs. Paths and cycles, Linear spaces, Steiner systems, Planar linear spaces, Intersecting linear spaces, Finite planes.
2. CHROMATIC NUMBER AND GIRTH
2.1. Chromatic number. Proper coloring, Greedy algorithm.
2.2. Graphs from the Hall of Fame. Graphs of Zykov, Mycielski, Tutte, Shift graph, Kneser graph.
2.3. How to glue hypergraphs to get graphs? Nesetril-Rôdl hypergraph.
3. A LOOK AT RAMSEY THEORY
3.1. Ramsey numbers. Pigeonholes and parties, Number of monochromatic triangles, Non-recursive and recursive upper bounds, Many colors and non-diagonal Ramsey numbers, Exact values of Ramsey numbers, Convex $n$-gons in planar point sets.
3.2. Van der Waerden numbers.
3.3. Tic-tac-toe and Hales-Jewett theorem with Shelah's proof.
3.4. Mysteries of the infinite.
4. COUNTING AND PROBABILITY
4.1. Proofs by counting. Antichains, intersecting hypergraphs, 3-chromatic uniform hypergraphs.
4.2. Probability method. The Erdôs lower bound on R(n) , Lower bound for W(k) , Tournaments, Large transitive subtournaments, Existence versus construction, Paradoxical tournaments with the Klein - Szekeres lower bound, Using expectation.
4.3. Local Lemma. Dependency bound, Erd\H os-Lov\'asz theorem, Improved lower bound on W(k) , Even cycles in regular digraphs.
4.4. Jokes. The triangle is 2 -chromatic, Spencer's injections.
5. LINEAR ALGEBRA METHODS
5.1. The dimension bound. Oddtown theorem, Fisher inequality, A cubic lower bound for R(n) , Two-distance sets, Cross-intersecting hypergraphs.
5.2. Homogeneous linear equations. Partition of K_n into complete bipartite graphs, Discrepancy of hypergraphs.
5.3. Eigenvalues. Cages of girth five (Hoffman - Singleton theorem).

SPECIAL OFFERS

6. FRUIT SALAD
Distinct representatives of sets, Chain decompositions, Properties of hypergraphs with n vertices and n,n+1,n+2 edges, Critical 3-colorable hypergraphs, Sunflower theorem, Sum-free subsets of numbers, Factorization of K_n and Steiner triple systems.

7. ADVANCED MENU Cyclic generators in Desarguesian planes, Factorization of hypergraphs, Two proofs of the perfect graph theorem, Constructive super-polynomial lower bound for R(n) , Hypergraphs in geometry: fall of Borsuk's conjecture, Graphs with large chromatic number and girth, Paley graphs and Paley tournaments.}