Math 340 -- Discrete Structures II

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:

How can one become better at solving mathematical problems? Note that there is more to maths than grades and exams and methods; there is also more to maths than rigour and proofs.

Don’t base career decisions on glamour or fame. But you should study at different places.

Does one have to be a genius to succeed at maths?

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.

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: How can one become better at solving mathematical problems? Note that there is more to maths than grades and exams and methods; there is also more to maths than rigour and proofs. Don’t base career decisions on glamour or fame. But you should study at different places. Does one have to be a genius to succeed at maths? 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.