Meetings: MWThF 2:10-3:00 PM, HARING 2016.
Instructor: Prof. Jesús A. De Loera.
contact information: (email) deloeramath.ucdavis.edu (phone) 530 574 9702
URL: http://www.math.ucdavis.edu/~deloera/
Office hours: Mondays and Wednesdays 3-4pm or by appointment.
My office is 3228 Mathematical Science Building.
Teaching Assistant: Mr. Benjamin Fineman
contact information: fineman@math.ucdavis.edu
Office hours: Tu 10-11am at 3123 MSB.
Description and Prerequisites Algebraic Combinatorics is a part of Mathematics that emphasizes the use of algebraic structures (e.g., matrices, groups, rings, fields, etc) to answer questions about discrete or finite objects (e.g. graphs, codes, algorithms, etc). In MATH 146 we will study applications of groups and generating functions to solve problems about graphs, running times of computer algorithms, codes, designs, and discrete geometry. Applications of algebraic techniques toconcrete combinatorial-computational examples will be emphasized. Here is an overview of the topics we will study:
Groups in Symmetry and Combinatorics (3 to 4 weeks) : Quick review of basic Combinatorics and counting. The structure of permutations, the 15-puzzle, group actions, orbits, graphs and automorphisms, Finite groups of rigid motions, Polya's theory of counting with symmetry.
The Ring of Generating Functions for Enumeration (6 to 7 weeks) : Formal Power Series and how to count with them. Recursion and how to solve them. Ordinary Generating Functions, exponential Generating Functions. Products and composition of Generating Functions. Applications to asymptotic estimation and Computation. Counting latin squares and magic squares. Multivariate generating functions.
The prerequisites for this class are Math 145 or Math 150A (or equivalent preparation and maturity) and the willingness to solve many exercises.
Textbook and Resources For the first three weeks of the class will use some lecture notes by the teacher:
Here is part 1 of the notes by the teacher .
Here is part 2 of the notes by the teacher .
Here is part 3 (last) of the notes by the teacher .
For the second part we will use the wonderful (free!) book generatingfunctionology by Wilf is available at the University Bookstore. You can also find it at the Shields Library and freely available online at http://www.math.upenn.edu/%7Ewilf/DownldGF.html.
In combinatorics is helpful to experiment with the problems to figure out the answer of a problem. Playing with computers is something that we highly recommend. MAPLE has some nice capabilities to play with permutations and generating functions that we will use a bit during the course. Here are the notes for Groups of permutations with MAPLE . Moreover here is the MAPLE worksheet used in class
You can obtain a computer account for this class go to http://www.math.ucdavis.edu/comp/class-accts to obtain an account. For this you will need the CRN number of this class.
The Online Encyclopedia of Integer Sequences is a great resource for finding generating functions and connections between various counting sequences.
Grading policy: The course grade will be based on 5 quizzes (15 points each). About a third of problems will be coming from the weekly homework. The lowest one will be dropped, for a total of 60 points. The final exam is worth (40 points). It will take place June 9th 10:30am (same place). The quizzes will take place during recitation (Thursday's at 2-3pm). The tests will be closed-book and closed-notes. I will assign grades based on an statistical curve of points obtained by all students, with the mean roughly corresponding to a $C+$ or a $B-$.
HOMEWORKS