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 Faculty Handbook entry for 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 2014

Lecturer

Name: Prof Alexander Molev
Room:   Carslaw 707
Phone:   9351 5793
Consultation hour:   Tuesday 2-3 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 2-3 pm
  • Tuesday 3-4 pm
  • Wednesday 2-3 pm
  • Thursday 1-2 pm

In general, lectures are held in the Monday-Wednesday 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, Week 12, when the Thursday time will be a revision lecture, and Week 13, when there will be no Thursday class.

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 2012 exam papers will be useful practice.

Assessment

Your raw mark will be calculated as follows.

  • 60%: Exam
  • 30%: Class quizzes (two, worth 15% each)
  • 10%: Assignment

The two quizzes (the same for MATH2069 and MATH2969) will be held in weeks 5 and 11, during the Thursday 1-2pm class times (not in the tutorials). The quizzes consist of short-answer 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 May 1.

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:  Non-homogeneous 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, Matrix-Tree 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.

Check your marks

Please check that your mark for Quiz 1 has been recorded correctly by entering your 9 digit SID into the box below and then pressing the "Check marks" button.

SID:              

Please note that any corrections to Quiz 1 marks must be made by Friday, Apr 18.

Timetable

Last revised 04/04/14

MATH2069MondayTuesdayWednesdayThursdayFriday
11am Tutorial
454
(Wks 2-13)
R.Tang
 
 
Tutorial
451
(Wks 2-13)
L.Neves
 
noon  
 
Tutorial
453
(Wks 2-13)
R.Tang
 
 
1pm  
 
 
Lecture
159
AI.Molev
 
2pm Lecture
159
AI.Molev
 
Lecture
159
AI.Molev
 
 
3pm Tutorial
453
(Wks 2-13)
VM.Nguyen
Lecture
159
AI.Molev
Tutorial
453
(Wks 2-13)
L.Neves
Tutorial
454
(Wks 2-13)
VM.Nguyen
 
4pm  
 
 
Tutorial
Law022
(Wks 2-13)
VM.Nguyen
 
For questions or comments please contact webmaster@maths.usyd.edu.au