- Course description:
Paul Erdős
(1913 -- 1996) was one of the greatest mathematicians of the twentieth
century. He made pre-eminent contributions to number theory,
probability theory, real and complex analysis, discrete geometry,
approximation theory, and set theory;
some
say that he founded the field of discrete mathematics.We will study a
selection of his results in number theory, geometry, Ramsey theory,
extremal combinatorial problems, and graph theory; in doing so, we
shall highlight his methods and proof techniques -- such as the
probabilistic method -- that are particularly applicable to computer
science. From time to time we will stray from his own work to the work
of his disciples, but we shall never escape the gravitational pull of
the great man.
- More detailed outline:
Proof of Bertrand's postulate. The Erdős-Szekeres and the de
Bruijn-Erdős theorems. Ramsey's theorem and Ramsey
numbers. Property B and hypergraph colouring. Van der Waerden's
theorem and van der Waerden numbers. Positional games. The
Erdős-Ko-Rado theorem. Delta-systems and a proof of the
Erdős-Lovász conjecture. Extremal graph theory. Random graphs and
graph colouring. The probabilistic method and its applications in
theoretical computer science.
|
|
|
|
The subject and the instructor, ca.1976
|
|
