Gil Kalai

Telephone numbers: Office (rm 404) 203-4321238, Home 203-7858902

Attention: Yale Discrete Mathematics Seminar: Mondays 4:30 AKW-200

Combinatorics - A graduate course open to undergraduates

MW 11:30 AKW-400

Lectures I,II: January 21,26 - Combinatorics in action:

A problem in additive number theory (For a set A of n numbers, either A+A or A*A is large!) is solved by Elekes using the Trotter-Szemeredi results about incidences and lines and points in the Euclidean plane. Trotter-Szemeredi theorem admots a short proof (by Szekely) based on a theorem by Ajtai, Chvatal, Newborn and Szemeredi and Leighton on crossings in graphs drawn in the plane, which admit a simple probabilistic proof based on Euler's theorem.

Lectures III, IV (and part of V) January 28,February 2 - Power sets and POSETs:

The power set of an n element set in particular and partially ordered sets (POSETS) in general. Sperner's theorem, Dilworth theorem and its baby brother. (Diversion: the perfect graph theorem) Decomposition to symmetric saturated chains and Dedekind problem.

Lectures V, VI VII, February 4, 9 and 11: Extremal Combinatorics

The Erdos Ko Rado theorem, The Erdos- de Bruijn theorem, first an Euclidean plane formulation: A proof using Gallai Sylvester and a recent proof using graphs of intersecting intervals. Linear algebra proof, Finite projective planes.

Special lecture VIII: Friday February 13 11:30 Rm 401 Mathematics Applications of Expanders in Computer Science

(Joint with the class of Alex Lubotzky) The combinatorial definition of expanders and the spectral connection. Applications: 1) Superconsentrators (the context of lower bounds), 2) Error-correcting codes, 3) randomized algorithms and derandomization, 4) algorithm based on rapidly mixing random walks.

Lecture IX: February 16

The shifting technique: The Suar-Shelah theorem. VC-dimension and learnability. The Erdos-Ko-Rado theorem revisited.

Lecture X: February 18

The Erdos-Ko-Rado problem. The Kruskal Katona Theorem.

Lecturs XI,X: February 23,25

Combinatorics in action II: Borsuk's problem. Frankl-Wilson theorem and various applications to geometry.

Special Lecture XI: Friday February 27 11:30

The combinatorics of Linear programming.

Lectures XII,XIII March 1,3

Generating functions, Catalan numbers, rational generating functions. Counting animals (polyominos) which are horizontally convex.

Problems and Excercises

There will be three problems set and one "make up" problem set at the end. The course-requirements are to submit three problem sets.

Problem Set I

Problem Set II