What's it all about?

What are we going to study in this class? Graph theory

… studies the properties of graphs. Informally, a graph is a set of objects called vertices (or nodes) connected by links called edges (or arcs) which can be directed (assigned a direction). Typically, a graph is designed as a set of dots (the vertices) connected by lines (the edges)¹.

and combinatorics

… is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. In particular, it is concerned with "counting" the objects in those collections (enumerative combinatorics), with deciding when the criteria can be met, with constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), with finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and with finding algebraic structures these objects may have (algebraic combinatorics)².

We will begin our discussions with graph theory covering §1.1–1.4, §2.1–2.3, and §3.1–3.4 in Applied Combinatorics, 4^th ed. by Alan Tucker. This will introduce us to the basic definitions, cycles, circuits, coloring, trees and searching. The first exam will cover this material. We will then cover §5.1–5.5, §6.1, §6.2, and §6.4 which introduces the basic techniques of counting and generating functions. Exam 2 will cover this material. The remainder of our time will cover §7.1–7.3 and §8.1–8.3 and introduce us to recurrence relations and the principle of inclusion–exclusion.

In addition to the two exams and the final, there will be a research paper and weekly homework assignments. This course will be very problem oriented. A typical week will consist of me presenting ideas and techniques from the book and then assigning problems for you to attempt; the problems will be discussed at the next class session and then homework for the section will be assigned. The class won't work well if you do not attempt the practice problems so that their solutions can be discussed. I encourage you to talk with each other about the problems, but to make sure that everyone writes their solutions independently and that you site on each problem the people with whom you worked. The weighting for each of these components can be found in the syllabus. There may also be some handouts and supplemental problems on which you will work and my hope you will learn the different techniques of combinatorics and how to apply them to real world situations.

For the research paper you will be given a list of topics some being things from the text that we won't cover and others being form sources outside of our text. You will be expected to submit a proposal in the 5^th week, a draft in the 11^th week, give an oral presentation in the 15^th week, and submit the final project the last day of class. You will be allowed to work in groups of up to three on the projects.

I will try to post solutions to homework questions that people have difficulty with to this page. I will also try to keep an updated list of the assigned problems and their due dates. Let's have a great semester!

Math 223

What's it all about?

Getting Help

Announcements

Solutions

Resources

Homework

Ask Me A Question!

Sources