Advanced Discrete Mathematics 2013

Exam

The exam will be on Monday, June 17th, from 09:15 to 12:00, in CM1. Please be on time.

In the Exam Guide you can find everything you need to know about the exam, but don’t hesitate to ask us anything by email or otherwise.

Here is a practice exam.

Lectures

Lecture 1: Introduction

Introduction slides

► Example of a probability proof: Large bipartite subgraphs.

     Online: [MatoušekVondrak-Thm3.3.1-p20] — Books: [AlonSpencer-Thm2.2.1-p16]

► Example of a linear algebra proof: Fisher’s Inequality.

     Online: [Penna-Thm2-p6] — Books: [Jukna-Sec7.3]

 

Lecture 2: Various proofs with linear algebra

► Generalized Fisher’s Inequality:

     Online: [Penna-Thm2-p6, Matoušek-Ch4] — Books: [Jukna-Sec7.3]

► Equiangular Lines:

     Online: [Matoušek-Ch9]

► Graham-Pollak Theorem:

     Online: [Penna-Sec2, Matoušek-Ch8] — Books: [Jukna-Sec13.2]

 

Lecture 3: Various proofs with the probability method

► Ramsey numbers – upper bound (no probability yet):

     Online: [Fox-Lecture5-Thm1-p2] — Books: [BondyMurty-Thm12.9-p313]

► Ramsey numbers – first lower bound:

     Online: [MatoušekVondrak-Thm2.1.2-p12, RiordanThm1.4-p4] — Books: [AlonSpencer-Prop1.1.1-p1, Diestel-Thm11.1.3-p312]

► Ramsey numbers – second lower bound:

     Online: [Riordan-Thm1.6-p5] — Books: [AlonSpencer-Thm3.1.1-p27]

► Graph with large girth and large chromatic number:

     Online: [MatoušekVondrak-Thm4.2.1-p22, Riordan-Thm1.23-p8] — Books: [AlonSpencer-p41, Diestel-Thm11.2.2-p317]

 

Lecture 4: Extremal graph theory

► Turán’s theorem with probabilistic proof:

     Online: [Gasarch-Thm2.1] — Books: [AlonSpencer-p95]

► Kővári-Sós-Turán theorem, Alon-Krivelevich-Sudakov theorem and dependent random choice:

     Online: [FoxSudakov-Lem2.1&Thm3.1] — Books: [AlonSpencer-p303]

 

Lecture 5: Extremal set theory

► Oddtown theorem: Online: [Penna-Sec1, Matoušek-Ch3] (Here is a nice discussion on the blog of Tim Gowers)

► Eventown theorem: Online: [Pikhurko-Sec4]

► L-intersecting set systems: Online: [Penna-Sec4, Fox-Sec3] — Books: [Jukna-Sec13.6]

► Ramsey graph construction: [Online: Fox-Sec2, Penna-Sec5] — Books: [Jukna-Sec13.7]

 

Lecture 6: Distances

► Equilateral sets: Online: [Matoušek-p145(only that page!)]

► Odd-distance sets: Online: [Reference will come after the next lecture…]

► Two-distance sets: Online: [Matoušek-Ch15, Fox-Sec2] — Books: [Jukna-Sec13.5]

► Blokhuis’s improvement: Original paper

 

Lecture 7: Points and lines

► Crossing lemma and Szemerédi-Trotter theorem: Online: [Terence Tao’s blog] — Books: [Jukna-Sec18.5, AlonSpencer-p285]

► Sum and product sets: Online: [Terence Tao’s blog] — Books: [Jukna-Thm25.13] 

Lecture 8-10: Eigenvalues of graphs

Notes for lectures 8, 9, and 10 – Might still be changed a little. Please let Frank know if you find any mistakes or if anything is unclear.

 

Lecture 11-13: The regularity method

Notes for lectures 11,12, and 13. Please let Bartosz know if you find any mistakes or if anything is unclear.

Texts

Work in progress – more references will appear here as we use them.

Online notes:

Books:

  • Jukna – Extremal Combinatorics (LA, P, GE) – Draft available on author’s website.
  • Matoušek – 33 Miniatures (LA, GE) – Draft available on author’s website.
  • Alon-Spencer – The Probabilistic Method (P)
  • Diestel – Graph Theory, 4th edition (P, RL) – Electronic edition available on author’s website.
  • Bondy-Murty – Graph Theory, 2nd edition (P, RL)

LA = proofs with linear algebra, P = proofs with probability, GE = graph eigenvalues, RL = regularity lemma

Details

The course covers probabilistic and algebraic methods in discrete mathematics. The order of topics is:

    Linear algebra proofs of discrete theorems
    Probability proofs of discrete theorems
    Eigenvalues of graphs
    Szemerédi regularity and applications

There is no required textbook, but we suggest various online texts and books. The exam is written.

Feel free to email with any questions.