Math 340 - Discrete Structures II



Professor  


Louigi Addario-Berry
| louigi@math.mcgill.ca | Tel: (514) 398-3831 (office) | 1219 Burnside Hall | Office Hours: Wednesday 13:00-14:00 or by appointment.


Time and Location  


MWF 11:35-12:25 | ARTS 260 | 4 January -- 14 April, 2010


Description  


Mostly graph theory and probability, and a little number theory.

Matchings, flows, and cuts. Planarity and Graph colouring. Spanning trees and combinatorial trees. Discrete probability and the probabilistic method. Extremal graph theory. Additional topics as time permits.


Evaluation  


There will be four or five assignments, worth a total of 20% of the final grade. There will be an in class midterm on March 8, worth 30% of the final grade, and a final exam covering all course material, worth 50% of the final grade.


Course book  


Matousek and Nesetril, an invitation to discrete mathematics.

Note: some course material is not covered in the textbook. Also, some may find Rosen, the MATH240 textbook and/or Bondy and Murty, and/or Diestel, to be useful references.


Prerequisites  


MATH 235 or MATH 240 or MATH 242. | Corequisites: MATH 223 or MATH 236.


Assignments  


Assignment 1, due Friday, 22 January, 2010, at the start of class. Solutions to Assignment 1.

Assignment 2, due Monday, 8 Feb, 2010, at the start of class. Solutions to Assignment 2.

Assignment 3, due Friday, 19 Feb, 2010, by 4 PM. Solutions to Assignment 3.

Midterm. Solutions to midterm.

Assignment 4, due Friday, 26 Mar, 2010, at the start of class. Solutions to Assignment 4.

Assignment 5, due Friday, 9 Apr, 2010, at the start of class. Solutions to Assignment 5.


Course Outline  


PDF version.


Other resources  


Supplementary textbook: Graph Theory, by Reinhard Diestel. Available for free download at the preceding link.

Words of wisdom from Fields medalist Terence Tao, for undergraduate mathematics students:


George Polya's How to solve it and the Wikipedia version

Slightly off-base: Tim Gowers' mathematical discussions.


Additional Information  


In accord with McGill University's Charter of Students' Rights, students in this course have the right to submit in English or in French any written work that is to be graded.

McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see www.mcgill.ca/students/srr/honest/ ) for more information).

You may work in groups of two or three on the assignments but must write up and hand in your solutions individually. The names of the students you worked with must appear on your assignments; failure to list your group members will result in an automatic grade of zero for the assignment.