Analysis of points and lines (TCC)

In a nutshell

Synopsis |  Syllabus | Organisation | Assessment | Bibliography

Synopsis

How well distributed can a set of n points in the plane be? How many incidences can there be between a finite set of points and lines in the plane? Does a dense subset of the set of words of length n over an alphabet of size k always contain a combinatorial line?

This course deals with these and other fundamental questions about points and lines that arise in a variety of different settings. The problems studied are elegant and relatively easily accessible, and the techniques range from harmonic analysis through relatively elementary algebraic and probabilistic arguments to hands-on but often ingenious combinatorics. As such it should be suitable for any graduate student with an interest in discrete mathematics, analysis, number theory and discrete geometry.

We shall begin by proving van der Waerden's classical theorem on the existence of monochromatic arithmetic progressions, as well as the Hales-Jewett theorem on combinatorial lines in high-dimensional spaces. The latter has recently claimed a fair amount of attention, its density version having been successfully proved by a polymath project.

In the second part of the course we shall see a number of classical results in discrepancy theory, which deals with how far from equidistributed a finite set of points in Euclidean space can be. This is a very rich subject which has many applications throughout mathematics, and beautifully combines analytic, algebraic and combinatorial methods.

Next we study the incidence theory of points in lines in Euclidean space as well as over finite fields, currently a hot topic in arithmetic combinatorics. It has important implications for Erdős' and Szemerédi's famous sum-product conjecture, which remains open to this day and asserts, roughly speaking, that the real line does not contain any approximate (finite) subfields.

The final quarter of the course will be dedicated to some applications of the aforementioned results in theoretical computer science, specifically the subfield of communication complexity. Please rest assured that no prior knowledge or affinity for computers is required for the enjoyment of this part!

The prerequisites are minimal. We shall need the fundamental notions of (discrete) Fourier analysis as well as basic concepts from linear algebra and discrete probability.

Note that there is no overlap in material with the course I taught last year, so students who took 'Introduction to additive combinatorics' in 2013 can get credit for this course.

Feel free to contact me at julia.wolf at bristol.ac.uk with any questions prior to the start of term.

Return to top

Syllabus

The following syllabus is tentative and subject to change.

Return to top

Organisation

I will be visiting all of the nodes (Oxford, Warwick, Bath and London) in the autumn, so office hours can be arranged locally according to demand. Please watch this space for times that I will be available, and email me if you would like to meet.

Return to top

Assessment

At the end of the course, participants will choose from a list of original research articles and write up an exposition of the chosen result. This exposition should place the result in the context of what has been discussed in the course, and should be sufficiently detailed for other course participants to be able to follow the main steps of the argument. The completion of the short weekly problem sets is optional but strongly encouraged.

Return to top

Bibliography

The following reading material may be helpful to course participants. You may also wish to consult my personal roadmap for interesting surveys and original research articles in this general area.

Return to top