## Topic outline

• ### General

Lärare:
Backelin, Jörgen

Föreläsningarna kommer att hållas på svenska, såvida inte minst en student önskar att de hålles på engelska. Skrivningens språk kommer också att anpassas efter studenternas önskemål.

The lectures will be taught in English, if at least one student wishes this to be the case; else they will be held in Swedish. Likewise, the language of the written exam will be (reasonably) accommodated to the needs of the students.

Course contents

The goal of this class is to learn the basic notions and principles of combinatorics such as permutations, graph theory, trees and search algorithms, directed graphs, recursive methods, generating functions, partitions.

Textbook

Grimaldi, Discrete and combinatorial mathematics, 5th edition, Addison-Wesley

Examination

There will be a final written exam. We may at the course start agree on supplementing this with bonus-enablng  studentactivities.

Tentative plan of the course:

The listed exercises are recommendations. In general, they should be made to the lecture after the one where they are listed. You may well do more excercises.

It is also important that you also checks that you understand the underlying terminology, whether or not it appears in exercises. Inter alia, employing and understanding basic set notation is absolutely indispensable in this course.

Day 1: Fundamentals; counting principles

Text: 1.1-1.4
Exercises:
1.2: 10,16,20,22,32,34,36
1.3: 10,12,16,18,20,26,28,30
1.4: 2,4,10

Day 2: Sets, functions, pidgeon hole principle
Text: 5.1-5.3, 5.5
Exercises:
5.3; 8,10,17
5.5: 4,8,10,12,20

Day 3: Inclusion-exclusion formula, derangements
Text: 8.1-8.3
Exercises:
8.1: 4,16,20;
8.2: 2,4;
8.3: 4,6,10

Day 4: Rook polynomials, generating formal power series
Text: 8.4-8.6, 9.1-9.2
Exercises:
8.5: 4,6,12
9.1: 2 (here r pennies instead of 35 pennies make more sense)
9.2: 2,4,6,8,10,16,30

Day 5: Exponential generating formal power series
Text: 9.3-9.5
Exercises:
9.3: 2,4,10
9.4: 2,4,6
9.5: 2,4

Day 6: Linear recursions
Text: 10.1-10.2
Exercises:
10.1: 2
10.2: 4,12,14,22,24

Day 7: Solving recursions with generating formal power series
Text: 10.2-10.4
Exercises:
10.2: 26,28
10.3: 2,6,8,12
10.4:1

Day 8: Graphs, subgraphs, isomorphic graphs, degree, Euler paths
Text: 11.1-11.3
Exercises:
11.1: (2),4,(8),(10),14
11.2: (2),6,8,10,12
11.3: 2,4,8,10,20,22,(24),30

Day 9: Hamilton paths, planarity
Text: 11.4-11.5
Exercises:
11.4: 2,6,(8),(10),12,14,18,22
11.5: (2),6,8,10,12,18
In 11.5 10b assume again that |V_1| <> |V_2| as in (a).

Day 10: Coloring, chromatic number, chromatic polynomials
Text: 11.6
Exercises:
11.6: (2),(4),6,8,10,14,16

Day 11: Trees and applications
Text: 12.1-12.2
Exercises:
12.1: 2,4,(6),8,10,(12),16,(18)
12.2: 2,8,10,16

Day 12: Combinatorial optimization problems: shortest paths, minimal spanning tree
Text: 13.1-13.2
Exercises:
13.1: 2
13.2: 2,4

Day 13: Flows and matchings
Text: 13.3-13.4
Exercises:
13.3: 4,6 (find in 4 also the corresponding minimal cut); always try to start with a flow with large flow value
13.4: 2,(4),6,8

Day 14: Reserve, review

Day 15: Review