*Instructor: *Dr. Ervin GYÕRI;S

*Text*: The course is based on handouts.

*Prerequisite*: Familiarity with binomial coefficients may be enough
in case of exceptionally talented students but at least one course in

combinatorics or in graph theory is required in general.

A minimum knowledge of linear algebra and discrete probability is advantageous
(for Sections 6 and 7).

*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 thechef(instructor) of the course:

BASIC MENU

**1.1. Definitions.** (Incidence matrices, Duality.)
**1.2. Examples of hypergraphs**. (Paths and cycles, Linear

**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.)
**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, Existence of Ramsey
numbers, 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.** \rm (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.)
**4.4. Jokes** (Triangle is 2-chromatic, Spencer's injections.)

**5. LINEAR ALGEBRA METHODS.**

5.1. The dimension bound. (Oddtown, 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

**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.**
**2.6. Graphs with large chromatic number and girth - the proof of
Erdõs.**
**2.7. Addressing with the squashed cube - Winkler's theorem.**