53 KAM Mathematical Colloquium

Prof. Ehud Friedgut

Hebrew University, Jerusalem

SOME APPLICATIONS OF FOURIER ANALYSIS IN COMBINATORICS

February 2, 2005

Lecture room S5, II. floor 10:30 AM

---

Abstract

Why do graph properties emerge so suddenly in random graphs when the edge probability changes slightly? What is the largest number of triangles one can construct with one million edges? (an edge can be shared by many triangles.) What are the optimal colorings of the graph of the $n$-fold product of a triangle? And most importantly - what do these questions have to do with Fourier analysis? The answers involve calculating partial derivatives, estimating different norms of certain functions, and understanding the eigenvalues of certain matrices - in short, a delicious mixture of mathematical flavors that arise when applying discrete Fourier analysis to combinatorial questions.