Course Literature :
1) Norman L. Biggs, Discrete Mathematics, Oxford.
2) Some extra material will be handed out during the course.
OBS ! A significant amount of the material I hope to cover is not included in either the course book or the material I intend to hand out. You will therefore be expected to rely first and foremost on your lecture notes for this material. Summaries of all lectures will appear on this site as the course progresses.
Course goals :
The term "discrete mathematics" covers, in principle, a vast swathe of mathematics including combinatorics, mathematical logic, algebra and number theory. Nevertheless, when one uses the term in practice one is usually referring primarily to the combinatorial aspects of these various subjects. Hence, this course is essentially an introduction to combinatorics. I do not intend to do any mathematical logic, apart from studying the complexity of some combinatorial algorithms. Neither do I intend to study any problems in algebra or number theory, however I do hope to study several areas of combinatorics (designs, error-correcting codes, Polya counting) to which methods from these areas can be applied. How far we can go with this will mostly depend on the background of the participants - I'm secretly hoping that everyone will have taken the course on Algebraic Structures !
The way the course is taught will hopefully reflect two generally accepted features of the subject of combinatorics : that it is (a) elementary and (b) useful.
By "elementary" I mean that most of the basic concepts can be defined and understood very easily and one can quickly get into the interesting business of posing and solving problems. I do NOT mean that the solutions to all these problems then turn out to be easy. There are a lot of deep theorems with complicated proofs ; however you will find that many theorems and exercises have short but fiendishly clever proofs, which are easy to understand once you've read them, but not so easy to come up with yourself. Hence the large amount of time to be devoted to problem solving (18 hours of lektioner !).
The elementary nature of the subject also means that there is a huge diversity of material in the literature, and I have to be very selective in deciding what to teach. I've decided to focus on three areas - graph theory, enumerative combinatorics and digital communication (coding and encryption) - but even within these areas I've had to be very selctive.
By "useful" I mean that many problems in the field amount to finding efficient algorithms for performing various tasks, and are often motivated by some practical (in the computer age, that is) application. Hence we will spend quite some time studying problems of an algorithmic nature and examining the efficiency of our solutions.
Course outline (subject to changes) :
We have 16 lectures, which I will divide into three blocks.
Block 1 : Graph theory.
Here we will cover Chapters 7-11 in Biggs and some extra material (see below). I will devote 5-6 lectures to this block.
Block 2 : Enumerative combinatorics.
Chapters 4,5,14,18,20 in Biggs, plus parts of Chapters 6,12,16. More if time permits .... I will devote 5-6 lectures to this block.
Block 3 : Digital communication.
Here I'll introduce the discrete mathematical aspects of two problems with enormous current applications : error-correcting coding (Chapter 17) and public key encryption (handouts). I intend to devote 4-5 lectures to these topics.
Schedule of lectures (subject to change) :
Students are expected to read Chapters 1,2,3 of Biggs on their own. In addition I'm hoping that everyone has taken the course Algebraic Structures, in which case you'll be expected to read on your own Chapters 13,15 and 16.1-16.4. The material in these chapters will not then be examinable, but you might need it to understand some of the stuff we cover.
3/4 : Chapters 7,8.
5/4 : Chapter 9.
10/4 : Chapter 10.
12/4 : Chapter 11.
17/4 : Ramsey theory (handouts).
19/4 : Chapter 5.
24/4, 26/4 : Chapters 12,18.
3/5 : Chapters 4,6,16.
8/5 : Chapters 14,20.
15/5 : Posets and extremal set theory (handouts).
17/5, 22/5 : Error-correcting coding (Chapter 17 and handouts).
24/5, 29/5 : Public key encryption (handouts).
31/5 : Revision. We may do some problems from gamla tentor, but PLEASE NOTE that this is basically a whole new course with not much overlap to the previous discrete math course, so much of the material on the exams from the last few years is not relevant.
Schedule of lektioner (updated regularly) :
3/4 : 8.1.1, 8.2.1, 8.3.1, 8.4.3, 8.5.1, 8.6.2 (i), portkod problemet.
10/4 : Problem 1 : If 6 people are at a party, then either there is a group of 3 who are mutual acquaintances, or a group of 3 who are mutual strangers. Show that this need not be true for 5 people.
Problem 2 : 8.8.5 and 8.8.6 (they go together). Problem 3 : 8.8.11.
Problem 4 : for the diagram of exercise 9.6.1 we will do the following : (i) locate spanning trees using DFS and BFS (ii) locate a min. weight spanning tree using DFS (iii) locate a shortest path from v to w using BFS.
Sammandrag av föreläsningarna (uppdateras regelbundet) ps pdf dvi tex
Inlämningsuppgifter :
Homeworks will be handed out at the end of weeks 15,17,19 and 21. Solutions to the homeworks can yield a maximum of 3 bonus points on the exam (out of a total of 25).
Homework 1 (att lämnas in fre 26/4) ps pdf dvi tex and solutions ps pdf dvi tex
Homework 2 (att lämnas in fre 18/5) ps pdf dvi tex and solutions ps pdf dvi tex
List of required theorems ps pdf dvi tex