Discrete Mathematics (Autumn 2012)

Time and location

Event	Time	Location
Lectures	Thu 14:15 - 15:45	Liivi 2-405	Peeter Laud
Practice sessions	Thu 16:15 - 17:45	Liivi 2-202	Margus Niitsoo
	Mon 14:15 - 15:45	Liivi 2-207
Behind the scenes			Reimo Palm
1st test	Sep 27th, 14:15 - 15:45	Liivi 2-405
	Jan 10th, 9:15 - 12:00	Liivi 2-122
2nd test	Nov 15th, 14:15 - 15:45	Liivi 2-405
	Jan 21st, 9:15 - 12:00	Liivi 2-122
3rd test	Dec 20th, 14:15 - 15:45	Liivi 2-405
	Jan 28th, 9:15 - 12:00	Liivi 2-122

Grading: there will be three tests during the term. The first one will be worth 15 points, the second and third both 30 points. It is possible to collect up to 30 points from solving the home exercises, and up to 7.5 points from checking the solutions of other students. The grade limits will be computed as if the maximum number of points were equal to 100.

Homework submission and feedback: The homeworks must be submitted electronically, by e-mailing them to Margus Niitsoo (firstname dot lastname at ut dot ee). The deadline for submission is at the start of the working day of the Thursday two weeks after the associated lecture. The subject line of the submission e-mail should start with DM: and the number of the homework. It is permitted to do the homeworks in groups, in this case the other members of the group must be CC:'ed and their names must be listed in the body of the e-mail.
The feedback will be given through Moodle.

The tasks in the tests will be similar in nature to the tasks considered in practice sessions, hence it makes sense to visit at least the practice sessions regularly.

The lectures will cover a number of topics from graph theory and combinatorics. We plan to talk about

• Recap: sets, relations, functions
• Elements of graph theory
  • Eulerian and Hamiltonian graphs
  • Flows, covers, matchings
  • Edge and vertex coloring
• Basics of counting
  • Combinations, permutations, etc.
  • Principle of inclusion and exclusion
  • Generating functions
  • Ramsey theory (ordered substructures of random structures)
  • (if time: Polya theory of counting)

News:

• Dec 4th: Last Thursday, we agreed on the days of second attempts for the three tests. Please see the schedule above.
• Oct 29th: The second test will take place on November 15th. The third test will take place on December 20th. Both will take place instead of the lecture.
• Sep 14th: The process of homework submission has been detailed.
• Sep 14th: The first test will take place on September 27th, instead of the lecture.
• Aug 30th: The first lecture will be on 6th of September. There is no practice session on 3rd of September.

Slides of the lectures will appear below. As a rule, they will not contain proofs of “simple” statements.

• September 6th and 13th
  • Slides of the second lecture added on September 9th
• September 20th — Eulerian and Hamiltonian graphs.
• October 4th — Network flows and Ford-Fulkerson algorithm.
• October 11th — various theorems somehow related to matchings in graphs. I believe these slides are suitable as setting the pace of the lecture, but not as a material for independent studies.
• On October 18th, we'll continue from where we stopped last time. After that, we'll consider necessary and sufficient conditions for the existence of perfect matchings in any graph (the slides are in Estonian, an English version with significant bit-rot is available here).
• On October 25th, we plan to cover two topics. First, we want to speak about finding maximum matchings in arbitrary graphs (not just in bipartite ones; we already know how to do this). There is a set of slides covering this topic, but we hope to do the development mostly without them. Second, we look at the number of colours we need to correctly colour all edges of a graph.
• On November 1st, we again plan to cover two topics. We will discuss planar graphs and the coloring of vertices of graphs.
• November 8th, 22nd, 29th, December 6th, containing
  • permutations, combinations, and identities involving binomial coefficients;
  • generating functions;
  • Polya theory of counting.
• On December 13th, we speak about Ramsey theory on regular substructures and on the probabilistic method of proving the existence of certain objects.