Math 316/416Course Information 29 January 2001

Prerequisites: Math 220 (Higher Mathematics: An Introduction), Math 142 (Discrete Structures I), or Math 200 (Discrete Mathematics), or my consent is required. In addition, I recommend that you take Math 342 (Discrete Structures II) prior to or concurrently with this course.

Class time and place: Tuesdays and Thursdays, 9:20-10:35, Darwin 137. Last class: Thursday, May 17.

Instructor: Ben Ford; office: Darwin 133D; phone: 664-2472; fax: 664-3012; e-mail address: ben.ford@sonoma.edu

Office Hours: Tuesdays and Thursdays 10:35-11:05 in the Math Lab, Darwin 127; Tuesdays and Thursdays 2:50-3:30 in the Math Lab, by appointment, or by chance.

Text: Applied Combinatorics (Third Edition), by Alan Tucker. Some supplementary materials will be handed out from time to time. We will cover topics from all three parts of the book.

316 vs. 416: Math 416 is a more advanced treatment of the same topics as 316. Math 416 is appropriate for those who plan to attend graduate school in Mathematics or theoretical Computer Science. Each problem set and exam will have one or more problems that are required only of those students enrolled in Math 416; and students enrolled in 416 will conduct a research project (on a combinatorics/graph theory topic of their choosing) which will include a written paper and a class presentation.

Proofs: Though you have had some experience with writing and discovering proofs, you will become much better at it during this course. Indeed, one objective of the course is that you become confident in reading and understanding proofs in texts, and in inventing proofs of your own. This can be a difficult process!

There will be proofs on every exam, and in every homework assignment. The purpose of this is not to scare you, but to emphasize the above objective. Please come to my office hours if you feel you aren't understanding the proofs, and we'll work on it.

Reading the text: You must do the readings as they are assigned. I am amazed that this somehow has become unexpected in Mathematics classes -- imagine attending a literature seminar without doing the reading before attending the class at which it will be discussed!

To facilitate your reading, I will hand out a ``reading summary'' to accompany each reading, which will consist of a few questions you should think about as you read. You should answer these as you go, though you are not expected to be able to fully answer all the questions based solely on reading. These summaries will form the basis for our discussion in class -- if nobody has trouble with a particular item, we won't have to spend time on it. This frees up time for the hard stuff.

Tests: On the exams you may use two letter-size pages (total of 187 square inches) of notes in your own handwriting (no printed or copied material). There will be one midterm exam, on Thursday, March 15. The final exam will be Thursday, May 24 from 8:00 to 9:50 a.m. Any make-up exams must be arranged with me before the scheduled exam. Make-up exams may be harder than the originals.

Homework: There will be four problem sets which will constitute the majority of your grade. In addition, there will be daily homework problems, which you will discuss with your classmates and sometimes present in class but not hand in. Some of these problems might be hard, and it is OK if sometimes you can't get all of them.

Schedule, Grading:

Date	Item	Points
February 13	Problem Set 1 due	40
March 6	Problem Set 2 due	40
March 15	Midterm Exam	40
April 10	Problem Set 3 due	40
May 10	Problem Set 4 due	40
May 24	Final Exam	60
	Class Participation	40

First Reading Assignments

Thursday, February 1

Read all the handouts from class.

Read appendix A.1 and section 1.1.

1. What is a set? Is ``the collection of all sets'' a set? Why or why not?
2. Why is it appropriate to use similar symbols for ``intersection'' of sets and ``conjunction'' in Boolean algebra?
3. Is the following statement True? ``$\sim$(today it is cloudy) $\wedge$(There are more women than men at SSU)''
4. What's a graph in this course? What are other meanings for the word?
5. What's the difference between a path and a circuit?
6. In example 1 (section 1.1), can you teach one person to do one new job and make the problem solvable?
7. What's an independent set? In Figure 1.7(a), find the largest independent set you can.
8. What's the relationship between an independent set of largest possible size and an edge cover of smallest possible size?
9. What's an interval graph?

Exercises: A.1: 1, 2, 13, 17; 1.1: 3, 4, 11, 13, 15, 19, 20, 27.

Tuesday, February 6

Read appendix A.2 and section 1.2.

1. Evaluate:

   Theorem: Every ball on a pool table is the same color as every other ball on the table.

   Proof: Let n be the number of balls on the table. The statement is true if n = 1, because the one ball is the same color as itself. Now assume n > 1 and the statement is true for 1, 2, 3,..., n - 1. Pick one of the balls and remove it from the table. Now there are n - 1 balls on the table, so by the assumption they are all the same color. Put the ball you removed back, and pick up a different ball. Again, all the balls on the table are the same color by the inductive assumption. So both of the balls you removed are the same color as all the other balls on the table; hence the statement is true for n.

2. In example 2 (Appendix A.2), is induction used to find the formula or to prove that it works?
3. What is an isomorphism of two graphs?
4. What is the degree of a vertex?
5. Draw two graphs with the same number of vertices, and the same degrees for corresponding vertices, which are not isomorphic.
6. What is a complete graph?
7. How do you decide whether two graphs are isomorphic?
8. What is the complement of a graph?

Exercises: A.2: 1, 5; 1.2: 1-11, 14.

First Problem Set (due February 13).

1. 1.4 #13; add (c) Must the complement of a disconnected graph be connected? Prove it or give a counterexample.
2. Show that every graph has two vertices with the same degree. [416 only: With a careful analysis, find all graphs with exactly one pair of vertices with the same degree.]
3. Determine whether the following two graphs are isomorphic. Prove it.
   

4. Find all nonisomorphic graphs with four vertices, proving that they are all nonisomorphic and that you have found all of them.

• About this document ...