Instructor: Dr. Attila SALI
Text: The course is based on handouts.
Prerequisite:
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.
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.
1. BASIC NOTIONS AND EXAMPLESBASIC MENU
1.1. Definitions. 1.2. Examples of hypergraphs
2. CHROMATIC NUMBER AND GIRTH
2.1. Chromatic number.
2.2. Graphs from the Hall of Fame.
2.3. How to glue hypergraphs to get graphs?
3. A LOOK AT RAMSEY THEORY.
3.1. 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.
4.2. Probability method.
4.3. Local Lemma.
4.4. Jokes
5. LINEAR ALGEBRA METHODS.
5.1. The dimension bound.
5.2. Homogeneous linear equations.
5.3. Eigenvalues.
SPECIAL OFFERS
1. FRUIT SALAD.
1.1. Distinct representatives of sets.
1.2. Symmetric chain decomposition.
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.
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.
2.6. Graphs with large chromatic number and girth - the proof of Erdõs.