COMBINATORICS -- MATH 4370/5370.

Winter, 2015

Dalhousie University,

Department of Mathematics and Statistics

Table of Contents

• General Information
• Syllabus
• Assignments
• Class topics and slides
• Topics for Class Projects (new topic added Jan. 21)
• Latex template for final paper
• Useful links (including LateX and writing resources)

General Information

• Time and Place:

  TR 10:05-11:25

  Chase 227

• Instructor

  Dr. Jeannette Janssen,

  Office: Chase Building Room, 223.

  Office hours: Tuesdays 1.30-3.30, or by appointment
  

  Phone 494-8851;

• Recommended texts

  Combinatorics: Topics, Techniques, Algorithms, Peter J. Cameron. Cambridge University Press 1994.

  Extremal Combinatorics, Stasys Jukna, Springer, 2001. Home page 2nd edition. Early draft can be downloaded from here.

  Generationfunctionology, Herbert S. Wilf. Download early version here.

  A Course in Combinatorics, J.H. van Lint and R. M. Wilson. Cambridge University Press, 1992.

  Top

• Class topics and notes
  • Tuesday, January 6. 36 officer problem. Latin squares. Systems of distinct representatives.
  • Thursday, January 8. Hall's Theorem. January 8. SDR's.

  • Tuesday, January 13. More on SDR's. Completion of latin rectangles and counting latin squares. Doubly stochastic matrices. Asymptotic behaviour of discrete functions. BigOh notation. Stirling's formula for approximating n!.
  • Thursday, January 15. Mutually Orthogonal Latin Squares (MOLS). Construction of MOLS January 15. Constructing a finite field.
    • Jan 6-15: Cameron 6.1-6.3, Jukna 5.1-5.3, vLint: some of Sections 5 and 22.
    • Jan 12: Asymptotics and Stirling's formula. Cameron 2.3-2.4, Jukna 1.1. Slides by Pat Morin (see link of course Web page)
    • Notes by Serge Bailiff on MOLS

  • Tuesday, January 20. Inclusion/exclusion principle. Proof using binomial theorem. Derangements. Euler function.
    • Jan. 20. Jukna, Section 1.6, Cameron, Section 5.1.

  • Thursday, January 22. Pigeonhole principle. Erdos-Szekeres theorem about monotone subsequences. Partially ordered sets. Dilworth theorem about chains and antichains.

  • Tuesday, January 27-February 5. More applications of pigeonhole. Proof of Dilworth theorem. Ramsey numbers. Intersecting families.
    • Jan. 22 - Feb 5. Most of this was self-study, due to cancelled classes. Notes for self-study

  • Tuesday, February 10. Generating functions. Introduction and basic facts. Binomial theorem. Using generating functions to prove combinatorial identities. Towers of Hanoi.
  • Thursday, February 12. Generating functions. Review of basic techniques. Use generating functions to find a closed formula for a recursively defined sequence. Fibonacci sequence. Two variable generating functions: binomial coefficients revisited.
    • Generationfunctionology, Sections 1.1-1.3 and 1.5.
    • Notes from an MIT course. See week 11 for generating functions.

  • Tuesday, February 24. Partitions, Stirling numbers. Binomial theorem
  • Thursday, February 26. Formal differentiation of ordinary power series. Definition of e^x. Definition of reciprocal.
    • Generationfunctionology, 1.4, 1.6, 2.1.

  • Tuesday, March 3. Let f(x) be the generating function of sequence {a_n}. What sequence has generating function f^k(x)? Application to number of ways to write an integer as a sum of k parts. Sequence with generating functions f(x)/(1-x). Application: proof of an identity involving Fibonacci numbers and binomial coefficients.
  • Thursday, March 5, composition of formal power series. Definition of inverse. Definition of ops of log(1-x). Exponential generating function. Application to derangements. Finally: application to the number of non-negative integer solutions to a linear equation with rhs n. (Spend n dollars on candy of different prices.) Counting fountains.
    • Generationfunctionology, 2.1-2.3

  • Tuesday, March 10. Steiner systems: definition. Steiner triple systems. Kirkman's school girl problem. Some examples of Steiner triples systems. Necessary conditions for the existence of STS(n).
  • Thursday, March 12. Construction of Steiner triples systems. Construction when n=3 (mod 6), so n=3m with m odd. Construction for n=1+6m, m even, by building on an STS(3m). Generalization of this construction using subsystems. Method of differences: a way to construct an STS(p) where p is prime and p=1 (mod 6).
    • Cameron. Chapter 8.

  • Tuesday, March 17. Designs. Definition and examples. Incidence matrix.
  • Tuesday, March 24. Derived designs, residual designs. Identities involving the number of blocks containing and avoiding certain sets of points. Symmetric designs, projective planes.
    • van Lint and Wilson, chapter 19 (posted here). Cameron. Chapter 16. Jukna, sections 13.1-13.4.

  • Thursday, March 26. Projective planes. Probabilistic method applied to Ramsey numbers, arithmetic progressions.
  • Tuesday, March 31 and Thursday, April 2. Expected value of a random variable. Using indicator variables and linear expectation to compute the expected value.
    • Jukna, Ch. 17, Sections 18.1-18.3, 20.1-20.4. For projective planes, see also popular article by Clement Lam, see linksbelow.

  ---

• Useful Links

  Let me know if you find any other useful links (implementations of algorithms discussed in class, descriptions of interesting graph theory applications or problems, etc.), and I will add them to this list.

  • The search for a finite projective plane of order 10
  • Steiner triple systems notes.
  • Projective planes notes.
  • Finite geometries notes.
  • Introductory tutorial on LateX
  • Page with useful resources on how to write math(including some sample papers)
  • A tutorial on how to write a math paper
  • Big Oh notation explained in simple slides by Pat Morin, Carleton University.
  • Online Encyclopedia of Integer Sequences (OEIS)
  • Wolfram Alpha

  ---

  Last updated April 7, 2015