This page contains the program for the course: lectures, exercise sessions, computer labs and home assignments. Other information, such as course goals, teacher(s), literature and examination, can be found in a separate course-PM.

Program

The course schedule is in TimeEdit.

There are 29x2 hour sessions scheduled for this course. Provisionally, 4-6 of these sessions will be dedicated to solving exercises, the remainder to lectures.

N.B.: The above plan will be subject to change, possibly at short notice, because of the necessity of doing everything online during the Corona outbreak. There will be a constant communication with the students.

The course will be divided into two main "themes", along with some lectures which provide a "transition" between the two themes. Not necessarily everything I do will be found in Biggs, but my lecture notes will cover everything.

PART 1: Enumerative Combinatorics (Biggs chapters 5, 6, 10, 11, 12, 19, 25). Not everything listed below is covered in the book (e.g.: Catalan numbers, combinatorial number theory, probabilistic viewpoints). My own lecture notes will cover everything.

- Principles of counting (addition and multiplication principles)
- Permutations, combinations, binomial coefficients and theorem
- Balls and bins
- Inclusion-Exclusion principle
- Pigeonhole principle
- Recurrence relations, including: linear recurrences in one variable, some non-linear recurrences (e.g. Catalan numbers), multi-variable recurrences (e.g.: Stirling numbers, integer partitions)
- Algebraic techniques for recurrence relations: extended binomial theorem and generating functions.

TRANSITION 1-2: Most of the material here is not in the book so consult my lecture notes.

- Application of generating functions to a problem in additive number theory (thin bases)
- Ramsey numbers (provide a nice "transition" from Part 1 to Part 2, and also serve as an introduction to the so-called "probabilistic method in combinatorics")
- Discussion of complexity of algorithms (see Chapter 14 of Biggs for more on this)

PART 2: Graph Theory (Biggs chapters 15, 16, 17, 18). The material on social networks and stable matchings is not in Biggs, so consult my lecture notes for these.

- Basic graph terminology
- Euler paths (postman problem) and Hamilton paths (Travelling Salesmean problem, Keycode problem etc)
- Trees (applications to: sorting, (minimal) spanning trees, search algorithms, counting trees (Cayley's theorem))
- Networks (shortest path, max-flow-min-cut and linear programming, social networks and the Unhappiness Paradox)
- Bipartite graphs and matchings (Turan's theorem, Hall's marriage theorem, stable matchings).

 

Lectures

 

The lecture notes are provisionally gathered into 26 files, based on what was covered in the last edition of the course. I do not expect there to be an exact 1-1 correspondence between a file and a 2-hour lecture. I will mail everyone in advance what I expect to cover at the next lecture and then afterwards update the numbering scheme to reflect where we actually are.

N/A indicates that a topic is definitely not covered in Biggs book.

 

File No.	Chapter in Biggs	Rough Content
1	5, 10.1 - 10.2, 10.4 - 10.6, 11.1	Addition and multiplication principles. Functions. Permutations, Combinations.
2	11.1 - 11.4	Binomial theorem, Balls and bins, Inclusion-Exclusion.
3	10.3, 11.5, 6.1 - 6.4	Inclusion-Exclusion ctd: surjections, Euler-phi, derangements. Pigeonhole principle: Erdös-Szekeres theorem
4	19.1 - 19.2	Linear recurrences and their solution.
5 5.E	19.2, 25.3	More on linear recurrences. Binomial theorem for negative integer exponents. Example of deriving an inhomogeneous linear recurrence
6	25.3 - 25.4	Generalized binomial theorem (ctd.). Generating functions.
7   Fig 7	25.5 - 25.6 N/A	More on generating functions. Catalan numbers (a solvable non-linear recurrence).
8   Fig 8.1       Fig 8.2	N/A 12.1	Catalan numbers (ctd). Stirling numbers.
9 9.E	12.2 - 12.4 N/A N/A	Stirling numbers (ctd.), Integer partitions. Special topic 1: Generating functions in additive number theory. Stirling numbers of the first kind
10   Fig 10	N/A	Special Topic 1 (ctd.) Special topic 2: Ramsey numbers.
11   Fig 11	N/A 15	Special topic 2 (ctd). Includes a probabilisitc viewpoint on the addition, I-E and multiplication principles. Introduction to graph theory.
12 12.E	N/A 15 N/A	Special topic 2 (ctd). Introduction to graph theory (ctd.).  Turan's theorem for extremal graphs without complete subgraphs
13   Figs 13.1-13.4	15.1 - 15.3, *N/A	Graph isomorphism. *Planar graphs and Euler's theorem. Degrees.
14    Figs 14	15.4, *N/A	Euler paths/cycles: The Königsberg problem. *The Keycode Problem (De Bruijn graphs).
15    Figs 15	*N/A 15.4	*The Keycode Problem (De Bruijn graphs), continued. Hamilton paths and cycles: *Dirac's theorem. TSP and NP-completeness.
16 16.E	15.6 - 15.7 N/A	Graph coloring. Full proofs of Theorem 16.8 and of remarks concerning G(n,1/2) after Prop. 16.12
17 Figs 17	15.5, 16.3, 16.6	Trees. Minimum spanning tree and shortest path problems.
18	16.3 17.1, 17.4	Trees (ctd.) Matchings. Hall's marriage theorem.
19   19.E	17.2, 17.5, 17.6 N/A	Matchings (ctd). Systems of distinct representatives. Edge colorings. Stable matchings and assignments
20   Figs 20 20.E	18 N/A	Networks: Max-Flow-Min-Cut (Ford-Fulkerson algorithm) Max-flow-min-cut theorem => König's theorem
3/6	Tentamen	Kl. 14.00 - 18.00 i ??-huset

 

Tillbaka till toppen

Exercises

 

Exercise Session #1 (30/3): Problems and solutions

Exercise Session #2 (20/4): Problems and solutions

Exercise Session #3 (4/5):  Problems and solutions; Figures to problems; Figures to solutions

Exercise Session #4 (13/5): Problems and solutions; Figures to problems; Figures to solutions

Exercise Session #5 (27/5): Problems and solutions; Figures to problems; Figure to solutions

 

Exercises from Biggs

 

Tillbaka till toppen

Datorlaborationer

 

No computer labs in this course

 

Referenslitteratur för Matlab:

1. Material utvecklat av MV som ger en kortfattad introduktion till Matlab
2. Programmering med Matlab,  Katarina Blom. Ger en introduktion till Matlab och lär ut grunderna i programmering med Matlab. Rekommenderas varmt för dig som är nybörjare både vad gäller programmering och Matlab.
3. Learning MATLAB, Tobin A. Driscoll. Ger en kortfattad introduktion till Matlab till den som redan kan programmera. Finns som e-bok på Chalmers bibliotek.
4. Physical Modeling in MATLAB 3/E, Allen B. Downey
   Boken är gratis att ladda ner från nätet. Boken ger en introduktion för dig som inte programmerat förut. Den täcker grundläggande MATLAB-programmering med fokus på modellering och simulation av fysikaliska system.

 

Tillbaka till toppen

Home Assignments

Assignment #1: Exercises and Solutions

Assignment #2: Exercises and figure and Solutions and figures

 

Tillbaka till toppen