MATH 503 Discrete Mathematics 2015 Fall

Instructor: Jozsef Solymosi

Office: MATH 220

solymosi@math.ubc.ca

Prerequisites: Familiarity with discrete structures (such as MATH 443) is desirable but not imperative. Talented undergraduate students are welcome however good grades and some honours math courses are required.

Tue Thu 11:00 - 12:30 Mathematics Annex 1118

Grading: Homework assignments 40%, Take home midterm 20%, Take home final 40%.

Course book (recommended):

Laszlo Lovasz, Combinatorial Problems and Exercises

The Hungarian edition

There is another nice book which is a great read; it is Stasys Jukna’s Extremal Combinatorics. (draft)

Course Material and Topics:

Discrete mathematics (combinatorics) is a fundamental mathematical discipline as well as essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. While in the past many results in this area were obtained mainly by ingenuity and detailed reasoning, the modern theory has grown out of this early stage and often relies on deep, well-developed tools.

The main aim of this course is to introduce many core ideas from this topic, such as extremal set theory, Ramsey theory and design theory as well as some of the dominant proof techniques such as probabilistic methods and algebraic methods.

The course outline follows (with sections taken from Lovasz’ book) with approximately 1 to 2 lectures being spent on each topic.

· Basic enumeration methods (section 1)

· Connectivity in Graphs and Menger’s theorem (section 6)

· Factors of Graphs and Tutte’s theorem (section 7)

· Graph colourings and perfect graphs (section 9)

· Block designs and Wilson’s theorem

· Extremal graph theory and Turan’s theorem (section 10)

· Strongly regular graphs and algebraic methods (section 11)

· Hypergraphs and extremal set theory (section 13)

· Ramsey Theory and probabilistic methods (section 14)

Links

· Stirling numbers Notes from Gabor Hetyei.

· Combinatorial proof to binomial identities I. Examples by Gary MacGillivray.

· Combinatorial proof to binomial identities II. More advanced techniques from Jacques Verstraete.

· Graph Theory With Applications a book by J.A. Bondy and U.S.R. Murty.

· Probabilistic Methods in Extremal Finite Set Theory by Noga Alon.

· Monochromatic Corners by Ron Graham and Jozsef Solymosi.

· Regularity Lemma a survey by Komlos et al.

· Spectral method examples

Problem Sets

1. Enumerations (Due Sept 24.)

· pointers to the solutions

· subsets |2,|3

2. Discrete probability (Due Oct 1.)

· solutions

3. Problem set 3. (Due Oct 8.)

4. Problem set 4. (Due Oct 22.)

5. Problem set 5. (Due Oct 29.)

6. Problem set 6. (Due Nov 12.)

7. Problem set 7. (Due Nov 26.)

F. Problem set F. (Due Dec 11.)