This page contains the program for the course: lectures, exercise sessions. The two homeworks will be placed here eventually. Other information, such as course goals, teacher(s), literature and examination, can be found in a separate course-PM. In addition, there is a pdf file below, giving further information about the course that we will go through on the first day.

Program

THIS COURSE WILL START OFF USING ZOOM: See first announcement.

The course schedule is in TimeEdit.  (BUT THE ROOMS LISTED THERE SHOULD BE IGNORED AT THIS POINT.)

There are 29x2 hour sessions scheduled for this course. Provisionally, 6 of these sessions will be dedicated to solving exercises, the remainder to lectures. This plan can be subject to change.

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 the lecture notes from last year's class (further below) will cover most of the other things. There are also some small supplementary lecture notes I have written; see course literature. There are some topics below that we might not cover and other topics not below which we might do. However, the below is a very good approximation.

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

• 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 the lecture notes further below.
• - 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")
• - Brief Discussion of complexity of algorithms (see Chapter 14 of Biggs for more on this)
  
  PART 2: Graph Theory (approximately Biggs chapters 15, 16, 17, 18). The material on social networks and stable matchings is not in Biggs, but in the lecture notes further below. However, it is not clear how much of that we will do.
•    
• - Basic graph terminology
• - Euler paths, Hamilton paths, Keycode problem
• - Trees, (minimal) spanning trees, algorithms, counting trees (Cayley's theorem)
• - Graph colorings and the chromatic number
• - Discussion of the 4 color Theorem for Planar graphs and proof of the 5 color theorem
• - Turan's Theorem
• - Bipartite graphs and matchings (Hall's marriage theorem, stable matchings).
• - Networks (shortest path, max-flow-min-cut social networks and the Unhappiness Paradox)
  
  

I will be following somewhat closely the way the course was taught last time by Peter Hegarty. For this reason, further below, I have kept parts of the previous running of the course. This includes the approximate schedule, exercise session problems, etc.

 

Introduction comments for first day

 

Exercise session problems go here.

First exercise session

Second exercise session

3rd exercise session

Two homework sets will go here.

1st homework set (optional)

2nd homework (optional)

 

Lecture notes from the lectures will be placed here.

March 21 lecture

March 23 Lecture

march 25

march 28 lecture

march 30 lecture

April1 lecture

April 4 lecture

April 6 lecture

April 8 lecture

April 25

April 27 lecture

April  29 lecture

may 2nd lecture

notes may 4

May 6 notes

may 11 lecture

may 13 lecture

may 16 lecture

may 18 lecture

may 20 lecture

23 may (last lecture)

EVERYTHING BELOW IS FROM THE PREVIOUS RUNNING OF THE COURSE AND NOTHING BELOW THIS LINE WILL BE MODIFIED.

...................................................................................................................................................................................................

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

 

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