Advanced Combinatorics

MATH 544 Spring 2014 course information

Instructor: Dr. André Kündgen
Email: akundgen@csusm.edu
Office: 335 Science Hall 2
Office phone: (760) 750-8070
Office hours: Mondays 2:45-3:45 (when classes are in session), or by appointment.

The easiest way to make an appointment or reach me in general is by email.

Lectures: Monday, Wednesday 4:00-5:15 PM (308 Science Hall 2).
Course Number: 28493

The cougar course page for Math 544 contains useful information, like the lecture notes, your grades, homework assignments, general announcements, and a discussion board for homework and other questions. You should check it regularly.

Textbooks

West, Introduction to Graph Theory (second edition), Prentice Hall (2001).

Diestel, Graph Theory (fourth edition), Springer Graduate Texts in Mathematics (2010).

Bondy and Murthy, Graph Theory, Springer Graduate Texts in Mathematics (2008).

These are the recommended textbook, and they are meant for supplementary reading. The lecture notes will be available from the web on the day of classes.

Prerequisites

A certain amount of mathematical maturity is necessary for this course. MATH 350, or a similar mathematics course that stresses the ability to understand and write proofs is required. It is also sufficient, and probably helpful, if you have already taken a more advanced course in discrete mathematics like MATH 472, MATH 474, MATH 540 or MATH 542.

The course is open to upper level undergraduate students as well as graduate students. No knowledge in graph theory or combinatorics is required, since we will develop everything we need from first principles.

Grading Policies

The numerical scores of all exams and assignments will be used in computing final score that will determine your final letter grade:

Homework 20%
Midterm Exam 25%
Presentation 25%
Final Exam 30%
Letter grade Numerical grade
A 85-100
B 70-84
C 60-69
D 50-59
F 00-49
There will be around 5 homework assignments and a detailed homework policy can be found on the web.

Important Dates

January 22: First day of classes
Mid-late March: Midterm Exam
March 31: Chavez day (no class)
April 1-5: Spring break (no class)
May 7: Last day of classes
May 14: Final Exam, 4:00-6:00 PM

Course content

At a party you sit at a table with 6 other people. It turns out that 3 of them are mutual strangers, that is neither of them knows any of the others. Is this a coincidence, or does it always happen that some 3 people are mutual friends or mutual strangers? What about if we have a group of 100 and try to find some 5 (or 6?) people that are mutual friends or mutual strangers?

The goal of this course is to tackle a wide variety of questions of this type: suppose we have a large collection of objects which does not seem particularly organized, can we nevertheless find some patterns? The answer will always be: YES, within reason. So to some extent this means that total chaos is impossible.

More specifically, we cover my list of major theorems of Ramsey theory and related areas of graph theory (like extremal graph theory and random graphs), number theory, geometry and combinatorics. A draft of this list can be found on the course webpage. This list may be updated as we go along.