Math 536 - Combinatorics II - Spring 2013

## Professor: Ron Gould

Text: Combinatorics - Topics, Techniques, Algorithms by Peter J. Cameron, Cambridge Univ. Press, 1994, 1997 and other supplied materials.
We will concentrate on Chapters 10, 15, 16, 17 (all of which will be suplemented with additional material).

Other references besides those given last semester:

• Lindner and Rodger, Design Theory, CRC Press. (For Chap 8, 16)
• van Lint and Wilson, A Course in Combinatorics, Cambridge Press.
• Bona, Intro to Enumerative Combinatorics, McGraw-Hill.
• B. Landman and Robertson, Ramsey Theory on the Integers, AMS.
• R. Graham, R. Rothchild and J. Spencer, Ramsey Theory, Wiley.
• V. Pless, Theory of Error-Correcting Codes, Wiley- InterScience Series.

 Office: E432 Math and Science Center Office Hours: 11:30am-1:00PM MF or by appointment Office Phone: 404-727-7924 email: rg@mathcs.emory.edu

Main Topics for the semester: Designs, Codes, Hadamard Matrices, Ramsey Theory, Counting under group actions (not necessarily in this order)

Combinatorics Hall of Fame: (2nd semester)

Steiner Kirkman Ramsey Polya Hamming

• ### Reading Assignments: Posted as needed

• Chapter 16

• Handout on Ramsey Theory
• ### Written Assignments: Posted as needed

(Usually due one week after chapter materials are completed in class.)

• Assignment 1: From Chapter 16,
• Problems: 1 (note: v+1 divides b(k+1) should be k+1 divides b(v+1)),
• 3, 7, 8, 10, 11, 12
• plus class assigned problems.

• Assignment 2: problems assigned in class on coding theory. Due, Monday March 9.

• Assignment 3: Due April 15 Now due next Monday April 20. From the handout, page 362, problems 8, 9, 12 and find the graph that shows r(3,4) is at least 9.

1. (a) Show that in any 2-coloring of the edges of the complete graph on 6 vertices, there are at least two monochromatic triangles.
1. (b) Show that in any 2-coloring of the edges of a complete graph on 7 vertices, there are at least 4 monochromatic triangles.

2. A student has 37 days to prepare for an exam. She knows she will require no more than 60 hours of study. She wishes to study at least 1 hour per day. Show that no matter how she schedules her study time (in an integer number of hours per day), there is a succession of days during which she will have studied exactly 13 hours.

3. Prove that no matter how the integers 1, 2, ..., 12 are positioned around a circle, some set of three consecutive integers sums to at least 19.

4. Prove Shur's Theorem.

5a Find a lower bound on S(3,4).

5b Bonus: Show that the Schur number s(3) = 14.

• Assignment 4: (Due Monday, May 4, 2015)
Chapter 15, Problems 1, 2, 5. (Note in 5b - this means find all nonisomrphic graphs on 4 vertices.)

Q1 Find the number of distinct bracelets of 5 beads made from yellow, blue and white beads. Two bracelets are indistinguishable if the rotation of one will yield another (no flips allowed).

Q2 The six faces of a cube are to be painted with 6 different colors, each face with a distinct color. In how many ways can this be done?

Q3: How many ways are there to 3-color the vertices of a wheel \$W_5\$?

Bonus: Determine the number of directed graphs on 3 unlabeled vertices using Polya techniques.