Discrete mathematics
Fall 2010

Time and place: Tue 15:45 -- 17:00 West Hall 4; Th 14:15 -- 15:30 East Hall 4
Instructor: Pavel Tumarkin
e-mail: p dot tumarkin at jacobs-university dot de
Office: Research I, 130; Phone: 200-3517
Office hours: Wed 16:00 -- 17:00 and by appointment

Teaching Assistant: Goran Drazic
e-mail: g dot drazic at jacobs-university dot de
Office: Research I, 116a
Office hours: by appointment

Textbooks: John M. Harris, Jeffry L. Hirst, Michael J. Mossinghoff, Combinatorics and graph theory
Reinhard Diestel, Graph Theory; Richard P. Stanley, Enumerative combinatorics (recommended reading)

Preliminary course content (subject to change): Enumerative combinatorics (basic principles of counting, generating functions, Young diagrams), basics of graph theory (trees, planar graphs, chromatic numbers, Ramsey theory, Hamilton cycles), enumeration of trees, basics of mathematical logic

Midterm: The midterm exam will took place on Th, October 21, 13:30, East Hall 4

Topics covered:
- Basic principles of counting: binomial and multinomial coefficients, Pascal triangle, pigeonhole principle, inclusion-exclusion formula
- Generating functions: formal operations, elementary generating functions, integration and differentiation
- Fibonacci and Catalan numbers, their generating functions
- Recurrence relations and rational generating functions
- Partitions and Young diagrams, changing money
- Groups and symmetry: Burnside's lemma, cycle index, pattern inventory
- Stirling numbers
- Graphs: basic definitions, properties, important types of graphs
- Distance in graphs, adjacency matrix
- Trees, spanning trees, enumeration of trees (Cayley's theorem), Matrix Tree theorem
- Eulerian and Hamiltonian graphs
- Planar graphs, Kuratowski's theorem
- Colorings, chromatic number, chromatic polynomial
- Matchings, Hall's theorem, perfect matchings
- Zermelo-Fraenkel axioms, axiom of choice
- Cardinalities of sets, Cantor-Bernstein theorem
- Ordered sets, ordinals and cardinals, transfinite induction

Final exam: Final exam will take place on Saturday, December 4, 10:00 -- 12:30, Lecture Hall Res. II.

Homeworks: There will be regular homework assignments.

Grading policy:

Grades will be computed according to the following rule (subject to minor changes):

Cutoff score: 95% 90% 85% 80% 75% 70% 65% 60% 55% 50% 45%
Grade: 1.0 1.33 1.66 2.0 2.33 2.66 3.0 3.33 3.66 4.0 4.33