MATH2069 Discrete Mathematics and Graph Theory
General Information
This page contains information on the Intermediate Unit of Study MATH2069 Discrete Mathematics and Graph Theory.
This unit is offered in Semester 1.
Lecturer(s): Alexander Molev
For further information on Intermediate Mathematics and Statistics, refer to the Intermediate Handbook. In particular, see the MATH2069 handbook entry for further information relating to MATH2069.
You may also view the description of MATH2069 in the central units of study database.
 Credit point value: 6CP.
 Classes per week: Three lectures, one tutorial and one practice class.
Email enquiries about MATH2069 may be sent to MATH2069@maths.usyd.edu.au.
Students: Please give your name and SID when emailing us. Anonymous emails will not be replied to.
MATH2069/2969 Information in 2016
Lecturer
Name: Prof Alexander Molev
Room: Carslaw 707
Phone: 9351 5793
Consultation hour: Tuesday 23 pm
Email:
alexander.molev@sydney.edu.au
Classes
Lectures and practice classes (joint for MATH2069 and MATH2969) will be held in Carslaw 159 at the following times:
 Monday 23 pm
 Tuesday 34 pm
 Wednesday 23 pm
 Thursday 12 pm
In general, lectures are held in the MondayWednesday times and practice classes in the Thursday times. The exceptions to the latter are Weeks 5 and 11, when the Thursday time will be a quiz, and Weeks 12 and 13, when the Thursday time will be a revision lecture.
In the practice classes you will work through a sheet of questions relating to the material in the preceding lectures; the solutions will be briefly discussed in the class. These questions will be similar to those in the quizzes. The question sheets are printed at the back of the books of lecture notes (see below), and also available on the web resources page, where the solutions will be posted after each week's class.
Tutorials (one per week) start in Week 2. The tutorial sheets are printed at the back of the books of lecture notes. (They will not be distributed in tutorials.) They are also available on the web resources page, where the solutions will be posted. The tutorials in Week 13 will be opportunities for you to try past exam questions; specifically, the 2015 exam papers will be useful practice.
Assessment
Your raw mark will be calculated as follows.
 70%: Exam
 20%: Class quizzes (two, worth 10% each)
 10%: Assignment
The two quizzes (the same for MATH2069 and MATH2969) will be held in weeks 5 and 11, during the Thursday 12pm class times (not in the tutorials). The quizzes consist of shortanswer questions where only the answers will be marked, similar to the practice class questions. More information on these quizzes will be posted on the web resources page closer to the dates.
The assignment (different for MATH2069 and MATH2969) will be posted on the web resources page and will be due on Thursday April 28.
Texts and References
The examinable content of the unit is all contained in the books of lecture notes: Topics in Discrete Mathematics and Introduction to Graph Theory by Anthony Henderson. These may be purchased from Kopystop, 55 Mountain Street, Broadway. Kopystop's phone number is 9211 2733.
Some other reference books, which you may want to consult for additional examples and exercises, are listed on the Acknowledgements page of the two books of lecture notes.
Course Outline
In the first half, we will study several related areas of discrete mathematics, which have applications throughout pure and applied mathematics, as well as in computer science and other sciences. In the second half, we will restrict our attention to one particular area of discrete mathematics, namely graph theory. We will investigate some of the fundamental results on Eulerian and Hamiltonian graphs, trees, and vertex colourings, among other topics.
The sections expected to be covered in each week's lectures (approximately) are as follows.
Week 1: Introduction to discrete mathematics, sets and functions,
counting principles (0,1.1)
Week 2: Ordered selections, binomial coefficients (1.2,1.3)
Week 3: Inclusion/exclusion, Stirling numbers
(1.4,1.5)
Week 4: Recursive sequences, induction, homogeneous linear recurrences
(2.1,2.2,2.3)
Week 5: Nonhomogeneous recurrences, formal power series (2.4,3.1,3.2)
Week 6: Generating functions and recursion
(3.3)
Week 7: Introduction to graph theory, basic definitions (0,1.1,1.2)
Week 8: Degrees, Eulerian and Hamiltonian graphs (1.3,2.1,2.2)
Week 9: Minimal walks, trees (2.3,3.1)
Week 10: Spanning trees, MatrixTree Theorem (3.2,3.3)
Week 11: Vertex colourings, chromatic polynomial (4.1,4.2)
Week 12: Edge colourings (4.3) and revision.
Week 13: Revision
Objectives and outcomes
The objectives of this course are to:
introduce basic concepts of combinatorics  permutations, selections and arrangements;
introduce the concept of generating functions;
illustrate how to find solutions of recurrence relations;
introduce the classes of Eulerian and Hamiltonian graphs,
trees and weighted graphs;
illustrate how to find minimal walks in graphs;
introduce vertex and edge colourings of graphs;
illustrate how to find chromatic polynomials of graphs.
Students who successfully complete this course should be able to:
identify and use combinatorial objects involved in counting problems to solve them;
solve linear recurrence relations by using generating functions and characteristic equations;
identify Eulerian and Hamiltonian graphs;
apply special algorithms to find minimal walks in weighted graphs;
apply special algorithms to find spanning trees in graphs;
find chromatic numbers and chromatic polynomials of graphs.
The distinction in the expected outcomes between the advanced and mainstream units
will be in the depth of understanding the theoretical base of the subject.
The advanced class students should be able to reproduce the proofs of the basic theorems
considered in the course and use them to solve problems by producing their own arguments.
The focus of the mainstream class will be on practical skills relied on the methods and approaches
developed in the course. They will be expected to be able to explain only the most basic arguments
underlying these methods.
MATH2069 students: please check that your mark for Quiz 1 has been recorded correctly by pressing the "Check marks" button.
Please note that any corrections to Quiz 1 marks must be made by Friday, Apr 22.
Timetable
Last revised 20/04/16
MATH2069  Monday  Tuesday  Wednesday  Thursday  Friday 

11am 
Tutorial 454 (Wks 27,913) VM.Nguyen 


Tutorial 451 (Wks 213) N.Sutherland 

noon 

Tutorial QudS227 (Wks 213) KY.Wang 
Tutorial 453 (Wks 213) B.Roberts 


1pm 


Tutorial 454 (Wks 213) B.Roberts 
Lecture 159 AI.Molev 

2pm 
Lecture 159 (Wks 17,913) AI.Molev 

Lecture 159 AI.Molev 


3pm 
Tutorial 453 (Wks 27,913) VM.Nguyen 
Lecture 159 AI.Molev 
Tutorial 453 (Wks 213) KY.Wang 
Tutorial 454 (Wks 213) K.Bulinski 

4pm 



Tutorial Law022 (Wks 213) K.Bulinski 

Show timetable / Hide timetable.