Math 121a
 
Combinatorial Analysis
Fall 2014-15
 
TR 1:00 PM // 11 Downs
Course Description | Policies | Textbooks | Lecture Notes | Handouts | Homework | Sections

Instructor: Chris Ormerod, 284 Sloan, 626-395-4831, cormerod @caltech.edu
Office Hours:  Mondays: 2:30pm-3:30pm
Lead TA:Daodi Lu TBA
Office Hours: Wednesdays: 2:30pm-3:30pm
Feedback Form
Announcements
 

 


 
 



Course Description
  Top

Math 121 is our standard three-term course on combinatorics (though we are only able to offer two terms this year).  The first term covers "structural" combinatorics, the study of interesting discrete structures, both in terms of general properties as well as in terms of the existence or classification of particularly nice or extreme instances.  We will spend much of the term on graphs and related topics (such as Ramsey theory), with the remainder of the term spent covering other important structures (Latin squares, codes, designs, finite geometries, etc.).  The second term will cover more quantititative aspects of combinatorics, as well as applications to and from algebra.

Policies
  Top

Grades: Grades will be assessed on the basis of homeworks, which will be given roughly biweekly. There will be no exams (or midterms). Students may discuss problems with each other but have to write down the solutions independently.

The following restrictions hold for all problems of the set: Students may ask questions to the TA (if one exists) and the professor. Resources which you may use while working on the homework include any books and non-interactive websites (i.e. no posting of the questions on internet fora). For calculations which you can do by hand, you may use a computer algebra program (Mathematica, Maple, etc.); you may also fell free to use a computer to gain intuition (say by solving small instances of the problems), so long as your eventual proof does not depend on such a computation.  If you use significant ideas from any source, other than the books mentioned on this website, you should mention where you got them from.

Textbooks
  Top


Text: A Course in Combinatorics, by J.H. van Lint and R.M. Wilson, 2nd edition. ISBN: 0521006015

Lecture Notes
  Top

Date Description
9/30  Lecture 1 : Graphs, Eulerian and Hamiltonian graphs, Trees and Prufer sequences.  
2/10  Lecture 2: Trees.  
7/10  Lecture 3: Coloring and Ramsey Theory. (See L. Lovasz, Three Short Proofs in Graph Theory for an alternative proof to Brook's theorem on coloring graphs, also J. Bondy, Short Proofs of Classical Theorems ). 
9/10  Lecture 4: Continuation of Ramsey Theory  
14/10  Lecture 5: Turans Theorem. (See M. Aigner, Turan's Graph Theorem.)  
16/10  Lecture 6: Hall's theorem, Konigs theorem and Matchings.  
21/10  Lecture 7: Posets, Dilworth's theorem.  
23/10  Lecture 8: More on flows in networks.  
28/10  Lecture 9: Graph Homology (Some brief notes).  
30/10  Lecture 10: Inclusion Exclusion 
4/11  Lecture 11: Stirling Numbers.  
6/11  Lecture 12: Generating functions.  
11/11  Lecture 13: Catalan numbers.  
13/11  Lecture 14: Combinatorial structures.  
18/11  Lecture 15: Partitions and q-numbers.  
20/11  Lecture 16: Latin Squares.  
25/11  Lecture 17: Latin Squares. (see excerpt from Latin squares: New Developments in the Theory andApplications by J. Denes and A.D. Keedwell.)  
27/11  Note: Thanksgiving, no lecture.
2/12  Lecture 18: Codes and Design.  
4/12  Lecture 19: Lattices and Mobius Inversion.  

Handouts
  Top

Date Description



Homework
  Top

Assignment
Date
Solutions
Assignment 1
 9/10
  
Assignment 2
10/23
  
Assignment 3
 11/6
  
Assignment 4
 11/20
  
Assignment 5
 12/4
  
Assignment 6
 12/12
  


 


 




  | © California Institute of Technology | Questions?  kaubry @ caltech.edu