everything.study
18.314

Combinatorial Analysis

Undergraduate · Historical course

Fall 2014

Topics

  • Pigeonhole Principle
  • Induction, Elementary Counting
  • Elementary Counting (concluded)
  • Binomial Theorem, Compositions
  • Compositions (concluded), Integer Partitions
  • Integer Partitions (concluded)
  • Set Partitions
  • Permutations, Cycle Type
  • Permutations (continued), Stirling Numbers of the First Kind
  • Permutations (concluded)
  • The Sieve
  • The Sieve (continued), Generating Functions
  • Generating Functions (continued)
  • Generating Functions (concluded)
  • Catalan Numbers
  • Partitions
  • Exponential Generating Functions
  • Exponential Generating Functions (concluded)
  • Vertex Degree, Eulerian Walks
  • Isomorphism, Hamiltonian Cycles
  • Tournaments, Trees
  • Counting Trees
  • Minimum Weight Spanning Trees
  • Matrix-Tree Theorem
  • Matrix-Tree Theorem (concluded), Bipartite Graphs
  • Bipartite Graphs (concluded)
  • Matchings in Bipartite Graphs
  • Latin Rectangles, Konig-Egervary Theorem
  • Matchings in Bipartite Graphs (concluded)
  • Chromatic Polynomials
  • Planar Graphs
  • Polyhedra
  • Polyhedra (concluded)
  • Coloring Maps
  • Ramsey Theory
  • A Probabilistic Proof

Readings

  • Most of the readings are assigned from the required textbook Bona, Miklos. A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory . World Scientific Publishing Company, 2011. ISBN: 9789814335232. [Preview with Google Books ] ↗
    Listed reading
  • SES #: 1 · TOPICS: Pigeonhole Principle · READINGS: Chapter 1
    Reading assignment
  • SES #: 2 · TOPICS: Induction, Elementary Counting · READINGS: Chapter 2 and start Chapter 3.
    Reading assignment
  • SES #: 3 · TOPICS: Elementary Counting (concluded) · READINGS: Chapter 3 (continued)
    Reading assignment
  • SES #: 4 · TOPICS: Binomial Theorem, Compositions · READINGS: Chapter 4
    Reading assignment
  • SES #: 5 · TOPICS: Compositions (concluded), Integer Partitions · READINGS: Chapter 5
    Reading assignment
  • SES #: 8 · TOPICS: Permutations, Cycle Type · READINGS: Chapter 6
    Reading assignment
  • SES #: 11 · TOPICS: The Sieve · READINGS: Chapter 7
    Reading assignment
  • SES #: 13 · TOPICS: Generating Functions (continued) · READINGS: Chapter 8
    Reading assignment
  • SES #: 17 · TOPICS: Partitions · READINGS: Chapter 8 (continued)
    Reading assignment
  • SES #: 20 · TOPICS: Vertex Degree, Eulerian Walks · READINGS: Chapter 9
    Reading assignment
  • SES #: 22 · TOPICS: Tournaments, Trees · READINGS: Chapter 10
    Reading assignment
  • SES #: 25 · TOPICS: Matrix-Tree Theorem · READINGS: Chapter 10 (continued)
    Reading assignment
  • SES #: 26 · TOPICS: Matrix-Tree Theorem (concluded), Bipartite Graphs · READINGS: Finish Chapter 10 and start Chapter 11.
    Reading assignment
  • SES #: 27 · TOPICS: Bipartite Graphs (concluded) · READINGS: Chapter 11
    Reading assignment
  • SES #: 28 · TOPICS: Matchings in Bipartite Graphs · READINGS: Chapter 11 (continued)
    Reading assignment
  • SES #: 30 · TOPICS: Latin Rectangles, Konig-Egervary Theorem · READINGS: Chapter 11 (continued)
    Reading assignment
  • SES #: 33 · TOPICS: Planar Graphs · READINGS: Chapter 12
    Reading assignment
  • SES #: 37 · TOPICS: Ramsey Theory · READINGS: Chapter 13
    Reading assignment
  • Bona, Miklos. A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory . World Scientific Publishing Company, 2011. ISBN: 9789814335232. [Preview with Google Books ] ↗
    Listed reading
  • We will cover Chapters 1 through 13. Additional lecture notes to be provided on the Matrix-Tree Theorem and Eulerian cycles.
    Listed reading
Sources