Discrete Mathematics 1
Summer Semester 2015.

Instructor.

  • Tibor Szabó
  • Phone: +49 30 838-75217
  • Office: 211A, Arnimallee 3
  • Office hours: by arrangement
  • Email: szabo at math dot fu-berlin dot de
    • Top

    Top

    Lectures.

  • Monday, 8:30 - 10:00 in Takustr 9, Gr. Hörsaal.
  • Tuesday, 14:15 - 16:00 in Arnimallee 3, Hörsaal 001.
    • Top

    Tutorials.

  • Teaching Assistant: Andreas Loos.
  • Tuesdays 12:15-14:00, Arnimalle 6 SR 031.
  • Thursdays 10:15-12:00, Arnimalle 6 SR 031.
  • Further information about lectures, tutorials, ``homework rules'' and exam.
    Top

    Exam.

  • Exam: Monday, 20th of July, 10:00-12:00, Arnimallee 3, Hörsaal 001
    Grades of those who allowed me to publish it here. You can take a look at your final September 3 (Wednesday), 11-12, SR 210, Arnimallee 3.
  • Make-up exam: Tuesday, 6th of October, 10:00-12:00, Arnimallee 3, Hörsaal 001.
    The results of those who allowed me to publish it here is here . You can take a look at your second final October 9th (Friday) 11:00-12:30 in SR 210 / Arnimallee 3.
    Top

    Textbooks.

  • J. Matousek, J. Nesetril, Invitation to Discrete Mathematics. (German and English editions)
  • M. Aigner, Discrete Mathematics (German and English editions)
  • M. Bóna, A Walk Through Combinatorics
  • L.Lovász, J. Pelikán, K. Vesztergombi: Discrete Mathematics, Elementary and beyond.
  • R. Brualdi, Introductory Combinatorics.
  • D.West, Graph Theory.
  • R.Diestel, Graph Theory, 4th edition.

    • Further reading:
  • M.Aigner, A Course in Enumeration.
  • B. Bollobás, Combinatorics, 1986.
  • S. Jukna, Extremal Combinatorics.
  • A.Tucker, Applied Combinatorics.
  • H.Wilf, Generatingfunctionology
    • Top

    Brief summary of the lectures

    Elementary Counting Principles (Rule of Sum, Rule of Product, Bijection, Double Counting, Identities for binomial coefficients; Aigner Ch 1.1, Bona Ch 3-4, Matousek 3.1-3.3)
    Partition Problems (set partitions, Stirling numbers of the second kind, permutations, cycles, Stirling numbers of the first kind, polynomial identities, integer partitions, The twelvefold ways of counting; Aigner Ch 1.2, 1.3, 1.4, Bona Ch 5, 6.1)
    Generating functions (Fibonacci sequence, homogenous linear recurrences with constant coefficients, fundamental operations on generating functions, Product Formula, Composition Formula, exponential generating functions, Product Formula, Composition Formula; Bona Ch 8, Matousek-Nesetril Ch 12.1-12.4)
    Week 6: Asymptotic Combinatorics (asymptotic notation, basic tricks of estimating, first estimates of factorial, binomial coefficients, estimation of the partition function p(n); Matousek-Neseteril Ch 3.4-3.6, 12.7). Inclusion-Exclusion (Basic problems, Combinatorial proof of the formula for Catalan numbers)
    Week 7: Inclusion-Exclusion (the Formula, Euler totient function, derangements; Matousek-Nesetril 3.7, 3.8, Bóna 7.1, 7.2) Posets (definitions, examples; Bóna 16.1)
    Week 8: Posets (Sperner's Thoerem, Dilworth's Theorem, incidence algebra, Möbius inversion (and its special cases); Matousek-Nesetril 7.2, Bóna 16.1, 16.2)
    Week 9: Pigeonhole Principle (Simple examples, Chinese Remainder Theorem, General Form and averaging, Erdos-Szekeres Theorem on monotone subsequences) Ramsey's Theorem (definition of Ramsey number, small cases, upper bound and lower bound)
    Week 10: Graph Theory (Basic definitions, notations, examples, Handshake Lemma, connectivity, characterization of bipartite graphs,); West Chapter 1
    Week 11: Eulerian graphs, Extremal problems (acyclicity, connectedness, Dirac's Thoerm, Mantel's Theorem) Trees (definitions, characterization); West 7.2, 1.2, 1.3.
    Week 12: Trees (properties, edge exchange proposition, application: Bridg-It (Strategy Stealing, Maker-Breaker connectivity game, Lehman's Theorem), counting labeled spanning trees (Prüfer code) (West 2.1., 2.2, Matousek 8.4); Matchings (definitions, basic examples, characterization of maximum matchings via M-augmenting paths, k-regular bipartite multigraphs have a perfect matching) (West 3.1)
    Week 13: Matchings (Hall's Marriage Theorem, Petersen's Theorem about 2-factors, vertex cover, König's Theorem on minimum vertex covers in bipartite graphs) Connectivity (connectivity of a graph, examples, edge-connectivity of a graph, the former is always at most the latter, characterization of 2-connected graphs, Menger's Theorem (statement)) West 4.1, 4.2.1
    Week 14: Colorings (Definitions, Examples, Lower bounds, Mycielski's Construction, Upper bound) Planar graphs (Definitions, Examples, non-planar graphs, Kuratowski's Theorem (without proof), Euler's formula, upper bound on the number of edges, 5-color theorem, 4-color theorem (without proof)) West
    Some notes
    Elementary Counting Principles
    Lecture 3
    Partition Problems (Updated: 29 Apr)
    Generating Functions
    Generating Functions II
    Asymptotic Counting
    Inclusion-Exclusion
    Posets
    Möbius Inversion
    Pigeonhol Principle, Ramsey's Theorem
    Graphs: Basic definitions
    Bipartite graphs, Connectivity, Eulerian graphs
    Extremal problems---an Introduction
    Trees
    Matchings
    Connectivity
    Four Color Theorem, Colorings, Planar Graphs
    Top

    Homework sheets.

    Exercise sheet -1. (to be solved during the first week exercise class)
    Exercise sheet 0. (to be solved during the second week exercise class)
    Exercise sheet 1. (due April 24th)
    Exercise sheet 2. (due May 1st)
    Exercise sheet 3. (due May 8th) (corrections to Exercises 12 and 15, 05.05.)
    Exercise sheet 4. (due May 15th)
    Exercise sheet 5. (due May 22nd) (correction to Exercise 22, 18.05.)
    Exercise sheet 6. (due May 29th)
    Exercise sheet 7. (due June 5th)
    Exercise sheet 8. (due June 12th) (correction to problem 38, 08.06.)
    Exercise sheet 9. (due June 19th)
    Mock Final (due June 26th) (A possible set of solutions
    Exercise sheet 10. (to be discussed in the Exercise sessions)
    Exercise sheet 11. (due July 3rd)
    Exercise sheet 12. (due July 10th)
    Exercise sheet 13. (A possible set of solutions )
    Exercise sheet 14. (A possible set of solutions )
    Top