Graph Theory and Applications/Discrete Applied Math I

Fall 2011

Instructor: Michael Pelsmajer

office: E1 206, phone: 312-567-5344

office hours: by appointment

email: pelsmajer_(AT)_iit_(DOT)_edu

Syllabus: Chapters 1-7 from Introduction to Graph Theory, 2ed, by D.B.West
(Corrections, Typos, Comments and Updates)

Generic Syllabi: Math 454, Math 553
ADA Syllabus Statement

Exam 1: Monday October 17, on material up to and including Section 3.1

Exam 2: TBA

Final Exam: Friday December 9, 2pm-4pm

1:50pm-3:15pm MW in Engineering 1 room 035

You should attend every class. Before and after material is presented in class, you should read the same material in the textbook.

I **strongly recommend** that you attend the Collaborative Problem Session each week, which will probably be:

1:50pm-3:15pm F in Engineering 1 room 035 (probably)

Homework problems are assigned on Mondays. By Friday, you should have already worked hard on the problems. Then you will be ready to take advantage of the session, and you will be able to finish by the following Monday, when it is due.

Often there will be Bonus Problems given at Friday sessions, and later posted here. These are worth *much less* than normal homework problems. I am not so concerned about the quality of writing, just the answers. I may give extra bonus for clever/nice ideas. I will collect them on Wednesday.

**What is a...** Simple Graph? Path? Trail? Perfect Matching? Etc. Graph Theory has many definitions and examples that you will not have seen in other classes, and you need to make them your "friends", to be as comfortable with them and their basic properties as you are with Sin(x), pi, and continuity.

**Theorems** Not just the statements, but being able to perform straightforward applications, and recognizing situations where the theorem can be applied.

**Solving Challenging Problems** using "techniques" such as

- The Try -> Fail -> Try Again process, which leads to better ideas.
- Generate specific/small examples, but also a "quasi-example" with some specified parts... the meaning of that depends on context, but one thing that is clear is that small examples are not enough.
- Much More.

**Write Clear, Complete Explanations** (Proofs)

Math 454 students can skip one homework problem in each assignment.
~~Math 553 students each have to do a project, eventually giving a talk. (More about this later.)~~ Exam and homework scores are interpreted differently.

Students are encouraged to discuss problems together, but solutions must be written up individually.

- p14-18 #14,15,22,30,38. Due Monday, August 29.
- p31-34 #7,10,11,15,25,26,29,42. Due Monday, September 12.
- p47-53 #17,18,31,40,41,57. Due Monday, September 19.
- p63-66 #10,22,25,29, p77 #33. Due Monday, September 26.
- p76-79 #35,47,60, p92 #6. In addition, everyone should do either p76-79 #29 or #39. Due Monday, October 3. (So Math 454 students do 4 problems total, and Math 553 students do 5 problems total.)
- p103-106 #2,3,5,14,21, p118-121 #8,9,13,28,29,31.
Hand in all of these problems on Monday, October 17 (but I suggest doing them by Wednesday, October 12).
~~p103-106 #2,3,5,14,21. p118 #8,9. Try to do them by Monday, October 10, although they won't be collected then because there is no class that day.~~ - p145-147 #2,8,15,22,24. Due Monday, October 31.
- p158-160 #(1 & 2), 9,12,23,25,28. Due Monday, November 7. (1 and 2 count as one problem, so there are 6 problems total, and Math 454 students do 5 of them and Math 553 students do all the problems.)
- p172-175 #1, 11, 12, 24, 28. Due Monday, November 14.
- p188-190 #2, 3, 7, 13a, 14. Due Monday, November 21.
- p199-202 #19,29,31,48. Due Wednesday, November 31?

Here are some additional problems, for those of you that want more practice and/or more of a challenge:

- p14-18, #26/27,28,31,37,41,47
- p47-53, #22,32,33

- Due August 31: three little problems
- Due September 14: (a) Is there an 8-vertex simple graph with vertex degrees 1,1,2,2,3,5,5,5? (b) Is there an 8-vertex simple graph with vertex degrees 1,1,1,2,4,5,5,5? (Use only elementary stuff. Specifically, there's a theorem coming up soon that gives the answer, and you may not use it.)
- Due September 21: How many components are there in the graph with this adjacency matrix?

Homework 40%, two exams and a final exam 20% each

October 31 announcement: If you do a project, it will be factored in, worth 10-15% of the overall grade

I would like to revise the syllabus to make the projects optional for everyone, including 454 students. However, if I don't approve your project plan, then you cannot do it, and your grade will be determined entirely from homeworks and exams. (Which is fine. I think that the homeworks are the main part of the course, so I am happy when someone chooses to put all their effort there. But I also like nice projects.)

Grading: Worth 10-15% of the overall grade, if you decide to do a project. A good project could raise your grade, and a bad project could lower your grade.

Each project will have at most 2 people.

There must be some kind of presentation, and if there are 2 people, both must share the job equally.

It must involve graph theory in a substantial way.

It must be new to you (for those of you who have seen graph theory elsewhere).

Possible topics:

- 1. Graph theory application to some non-math topic
- 2. Graph theory application to some math, but not discrete math, topic
- 3. A section or more from Diestel's Graph Theory Book (free "preview" on-line),
and maybe some exercises, too:

E.g., sections 3.2, 3.3, 3.5, 5.5, 7.1, 7.4&7.5, 11.?, 12.2, 12.3

Let me know if there are any objections. And if you are thinking about doing a project, talk to me about it ASAP so that we can agree on what it will consist of.

Not yet.

Reasonable accommodations will be made for students with documented disabilities. In order to receive accommodations, students must obtain a letter of accommodation from the Center for Disability Resources and make an appointment to speak with me [the instructor] as soon as possible. The Center for Disability Resources (CDR) is located in Life Sciences Room 252, telephone 312-567-5744 or disabilities@iit.edu.