3COM/4COM: Combinatorics

3COM/4COM: Combinatorics

Spring 2016

Lecture Theatre B

Tuesdays 12pm-1pm, Fridays 11am-12pm

Examples class: Tuesday 11am-12pm Lecture Theatre A in weeks 3,5,7,9, 11

Instructors

Will Perkins

w.f.perkins@bham.ac.uk

Office: Watson 211

Office Hours: Fridays, 12:00pm - 1:30pm

Andrew Treglown

a.c.treglown@bham.ac.uk

Office: Watson 314

Office Hours: Mondays 10:30-11:30am, Wednesdays 11:30am-12:30pm

Course Information

Main Topics of the Course:

  1. Ramsey theory for graphs
  2. Ramsey theory for numbers
  3. Asymptotics
  4. Probability theory
  5. First and second moment methods
  6. The Lovasz local lemma

References
  • Graph Theory, by A. Bondy & U.S.R. Murty, Springer Verlag 2008.
  • The Probabilistic Method, by N. Alon and J. Spencer, Wiley, 2000.
Schedule
  • Jan 12 Introduction

    Ramsey numbers for complete graphs

  • Jan 15 Ramsey Theory

    Ramsey numbers for finite graphs

  • Jan 19 Ramsey Theory

    Ramsey numbers for more than two colours

  • Jan 22 Ramsey Theory

    Small Ramsey numbers

  • Jan 26 Ramsey Theory

    Examples class. Lower bounds for Ramsey numbers.

  • Jan 29 Ramsey Theory

    Problem sheet 1 due (summative). Ramsey theory for numbers.

  • Feb 2 Ramsey Theory

    Van der Waerden's theorem

  • Feb 5 Ramsey Theory

    Van der Waerden's theorem continued

  • Feb 9 Asymptotics

    Examples class; Big O notation.

  • Feb 12 Asymptotics and Probability Spaces

    Stirling's Formula; Binomial Coefficients; Problem sheet 2 due (formative)

  • Feb 16 Probability Spaces and Random Variables

  • Feb 19 Independence and Conditioning

  • Feb 23 Random Graphs and Random Walks

    Examples class

  • Feb 26 Expectation

    Problem sheet 3 due (summative)

  • Mar 1 First Moment Method

  • Mar 4 Variance

  • Mar 8 Second Moment Method

    Examples class

  • Mar 11 Applications of the 1st and 2nd moment methods

  • Mar 15 Thresholds in Random Graphs

  • Mar 18 Lovasz Local Lemma

    Problem sheet 4 due (formative)

  • Mar 22 Applications of the Local Lemma

    Examples class