MA/CS 415G 001 Combinatorics and Graph Theory

Instructor: Rafael S. González D'León
Email: rafaeldleon@uky.edu
Homepage: http://www.ms.uky.edu/~rsgo226
Office: Patterson Office Tower, Room 767.
Office Hours: Thursdays 2:00PM to 3:00PM or by appointment.

Lectures

Monday, Wednesday and Fridays 1:00pm-1:50pm CB 339.

Literature

A First Course in Discrete Mathematics. Ian Anderson.

Course Contents

This course is a basic course in the theory of counting and graph theory. Counting. Subsets and binomial coefficients. Partitions and Stirling numbers. Permutations and permutation statistics. Fibonacci and Catalan numbers. The inclusion-exclusion principle. Recurrences. Generating functions. Graphs. Eulerian and Hamiltonian cycles. Graph colouring. Most of chapters 1 to 6 from Anderson's book.

Examination and Grading

Tests (30%)

There will be 2 tests. These will be announced at least one week in advance.

Final (30%)

There will be a comprehensive final to be worth 30%.

Homework and Quizzes(40%)

There will be a set of problems to be handed in at the end of every week. To work on the homework problems is crucial for your understanding of the material presented in class. Be sure to separate enough time each week to think and write your solutions. It is recommended that you think and attempt every problem on your own before seeking any help. You are encouraged to discuss the material of the course with your classmates, however you must write your own solutions using your own words. There can be unannounced quizzes that will count towards your homework grade.

Problem Sessions

There will be various in-class problem sessions during the semester whose goal is to reinforce the concepts learned during a given week. During the problem sessions you are strongly encouraged to share what you have learned and to learn from your fellow class mates (share and learn).

Suggested problems

There will be some additional suggested problems. These problems will be assigned after some of the classes and also posted in the web page of the course.

Grading Scale

PercentageGrade
>=90%A
>=80%B
>=70%C
>=60%D
<60%E

Syllabus

This is an approximate schedule of the course containing the syllabus:
DateTopic
Wed 08/24Introduction. What is combinatorics?
Fri 08/26Review of mathematical proofs.
Mon 08/29Basic Principles of counting. Permutations and factorials
Wed 08/31Combinations and selections
Fri 09/02Combinations and selections
Mon 09/05ACADEMIC HOLIDAY. LABOR DAY
Wed 09/07Binomial coefficients and Pascal's triangle
Fri 09/09Binomial coefficients and Pascal's triangle
Mon 09/12Selections with repetitions, Compositions
Wed 09/14A useful matrix inversion
Fri 09/16A useful matrix inversion
Mon 09/19Recurrences
Wed 09/21Auxiliary equation method
Fri 09/23Auxiliary equation method
Mon 09/26Generating functions
Wed 09/28Generating functions
Fri 09/30Derangements. Sorting algorithms
Mon 10/03Derangements. Sorting algorithms
Wed 10/05Test 1 Review
Fri 10/07Test 1
Mon 10/10Catalan numbers
Wed 10/12Graphs
Fri 10/14Graphs
Mon 10/17Paths and Trees
Wed 10/19Spanning trees
Fri 10/21Spanning trees
Mon 10/24Bipartite graphs. Planarity
Wed 10/26Chords of a circle. Polyhedra
Fri 10/28Chords of a circle. Polyhedra
Mon 10/31Hamiltonian Graphs
Wed 11/02The travelling salesman proble
Fri 11/04Eulerian graphs
Mon 11/07Eulerian graphs
Wed 11/09Test 2 Review
Fri 11/11Test 2
Mon 11/14Graph colouring
Wed 11/16Chromatic polynomial
Fri 11/18Partitions
Mon 11/21Partitions
Wed 11/23THANKSGIVING HOLIDAY
Fri 11/25THANKSGIVING HOLIDAY
Mon 11/28Partitions
Wed 11/30The inclusion-exclusion principle
Fri 12/02The inclusion-exclusion principle
Mon 12/05Applications of the IEP
Wed 12/07Applications of the IEP
Fri 12/09Review Final

Calculators Policy

Calculators are not allowed in quizzes, tests or the final exam.

Code of Conduct

Students should consult the students rights and responsibilities outlined in the Student Code of Conduct. Any offense to the Code of Conduct will result in a grade of "E" for the course and a referral to the Dean of Students.

Excused Absences

University Senate Rule 5.2.4.2 defines the following acceptable reasons for an ”excused absence” from class: Students should notify the instructor of an excused absence prior to the absence whenever possible and complete all work prior to the absence (unless for illness or for the illness or death of a family member).

Students with Disabilities

Students with documented physical‚ learning‚ or temporary disabilities may receive assistance and support from the Disability Resource Center. It is recommended that students contact the Disability Resource Center early to request specific assistance so that the required medical or psychological documentation can be reviewed and reasonable accommodations can be provided from the beginning of class work in order to achieve the greatest benefit to the student.

Changes to this Syllabus

This syllabus may have some changes during the semester. It is responsibility of the students to visit frequently the webpage of the course for up to date information.