Advanced Combinatorics — CO2

  • Instructor: Attila Sali
  • Contact: saliattila 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 uses handouts.

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.
 

Here we add the CO2 MENU CARD provided by the  chef(instructor) of the course:

BASIC MENU

1. BASIC NOTIONS AND EXAMPLES
1.1. Definitions.  (Incidence matrices, Duality.)
1.2. Examples of hypergraphs. (Paths and cycles, Linear spaces).

2. CHROMATIC NUMBER AND GIRTH
2.1. Chromatic number.
2.2. Graphs from the Hall of Fame. (Graphs of Zykov, Mycielski, Tutte, Shift graph, Kneser graph.)

3. A LOOK AT RAMSEY THEORY.
3.1. Ramsey numbers. (Pigeonholes and parties, Existence of Ramseynumbers,  Upper bound on R(n), Many colors and non-diagonal
Ramsey numbers, Exact values of Ramsey numbers.)
3.2.  Van der Waerden numbers.
3.3.  Tic-tac-toe and Hales-Jewett theorem.

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, Hamiltonian paths.)
4.3. Local Lemma. (Erdõs-Lovász theorem, Improved lower bound on W(k), Even cycles in regular digraphs.)

5. LINEAR ALGEBRA METHODS.
5.1. The dimension bound. (Odd town, Fisher inequality, A cubic lower bound for R(n), Two-distance sets, Cross-intersecting hypergraphs.)
5.2. Homogeneous linear equations. (Partition into complete bipartite graphs, Beck-Fiala theorem.)
5.3. Eigenvalues. (Regular graphs of girth five.)
 

SPECIAL OFFERS
1. FRUIT SALAD.
1.1. Distinct representatives of sets.
1.2. Symmetric chain decomposition.Extensions of Sperner's Theorem
1.3. A property of n sets on n elements.
1.4. A property of n+1 sets on n elements.
1.5. A property of n+2 sets on n elements.
1.6. 3-color-critical hypergraphs. Partition critical hypergraphs
1.7. Sunflower theorem.
1.8. Sum-free subsets of numbers.

2. ADVANCED MENU.
2.1. Factorization of hypergraphs - Baranyai theorem.
2.2. Normal hypergraphs and perfect graphs - Lovász theorem.
2.3. Constructive superpolynomial lower bound for Ramsey numbers.
2.4. Hypergraphs in geometry: the fall of Borsuk conjecture.
2.5. Shelah's proof of Hales-Jewett theorem.