Mathematics 357 – Combinatorics Project Topics March 14, 2005

General Information

As announced in the syllabus given out at the beginning of the semester, one of the assignments for the Combinatorics course will be a group project leading to a paper of about 10 pages. Several suggested topics are given below. All of them take material we have learned in this course and extend it in new directions. I will also be happy entertain any ideas you might have designing a project topic of your own. If there is some combinatorial subject you are interested in, or that makes contact with another course you have taken, please do not hesitate to discuss it with me and get my approval before you start to work.

You will work in groups of three or four on these projects. If you need help putting a group together, be sure to talk to me well before March 30.

In working on this paper, you should follow the same procedures you would follow in preparing a research paper for any other course, and of course the College Policy on Academic Honesty applies here, as it does to all of your work. Your grade will depend on the thoroughness of your research, the degree of independent thought about the subject revealed through your work, the organization of the paper, and the quality of your writing. Do not assume that because this is a mathematics paper writing does not matter! A word to the wise: I tend to be rather severe when I read papers with large numbers of misspellings, or many grammatical and other technical errors. The same thing happens with papers consisting largely of masses of undigested quotations from your sources, particularly when those quotations involve technical discussions of mathematics you do not understand fully. To avoid having this happen to you, take me up on the following offer: I will be happy to read a preliminary draft of your paper and give you comments.

Your papers should be word-processed or typed, one side only, double-spaced. Equations can be entered by hand if necessary. You can also use the MS Word Equation Editor if you have it. Your paper should include a bibliography listing all the sources you consulted. Direct quotations should be identified with foot- or end-notes. If you don’t understand all the technical details of an argument, ask me about it, and we can work through it.

Schedule

Here are some important dates for the projects:

1. Wednesday, March 30 (or before): Please inform me which topic you have chosen to work on and who you will be working with. You can do this by sending me a short email message, or by talking to me in person.

2. Week of April 18: During this week, I would like to meet with each group (during office hours, or whenever is convenient for you) to discuss your progress on the project. Of course, you’re always welcome at other times too if you need help.

3. Wednesday, May 4: Final projects due. This is an absolutely firm deadline–no extensions will be possible, so please don’t ask.

Suggested Topics

The first group oftopics rely mostly on the definitions of graphs, directed graphs, and so on. They have few other prerequisites.

I. The König-Egerváry theorem.

In class, we have discussed (or will soon discuss) the graph version of Hall’s Theorem, which gives conditions under which a matching from V_{1} to V_{2} exists in a bipartite graph G = (V_{1}, E, V_{2}). For this project, you would consider a result which can be seen as a generalization of that theorem. The König-Egerváry theorem in effect identifies the size of the biggest possible “partial” matching in such a graph, even if a full matching does not exist. There is also an algorithm (called the “Hungarian algorithm”) for solving the optimal assignment problem based on this result. For this topic, you would present a discussion of the K-E theorem and its proof, include solutions for Exercises 1,2,3 from Chapter 9 of Bryant’s text Aspects of Combinatorics (on reserve for the class in the Science Library), and discuss the application to the optimal assignment problem. Good sources to get started on this topic include the first part of Chapter 9 of Bryant and Chapter 5 of Graph Theory with Applications by Bondy and Murty .

II. Directed Graphs and The Max Flow-Min Cut Theorem.

Directed graphs are frequently used to model flows through networks (for example traffic flows over road or rail systems, fluid flows through pipeline systems, and so forth). In this area, there is a well known theorem, first developed by Ford and Fulkerson, called the Max Flow-Min Cut Theorem. This theorem relates the maximum possible flow through a network to the capacities of its individual components. For this topic, you would present the precise statement of the theorem, give a proof, and then illustrate the result with one or more worked-out examples, the more realistic the better! Good sources to get started on this topic include Chapter 12 in our text, the second part of Chapter 9 of Bryant Aspects of Combinatorics (on Reserve in the Science Library for our class), and Chapter 11 of Graph Theory with Applications by Bondy and Murty (on Reserve in the Science Library for our class).

III. Edge-Coloring of Graphs.

Ever wonder how the Registrar’s Office manages to schedule all the different classes at Holy Cross so that no two classes share the same room assignment at the same time? Many problems like this one can be phrased in terms of edge-colorings of graphs – that is assignment of some color to each edge in a graph so that no two edges meeting at any vertex have the same color. For this topic, you would research a basic result called Vizing’s Theorem, which states that any graph whose maximum vertex degree is d can edge-colored with either d or d + 1 colors. Surprisingly, no more than d + 1 colors are ever needed! Also include solutions to Exercises 3,4,5,6 of Chapter 7 in Bryant Aspects of Combinatorics (on Reserve in the Science Library for our class). Then you would look at the application of edge-coloring of graphs to the time-tabling problem, a generalization of the classroom scheduling problem mentioned above. Good sources to get started on this topic include the first part of Chapter 7 of Bryant and Chapter 6 of Graph Theory with Applications by Bondy and Murty (on Reserve in the Science Library for our class).

IV. Planar Graphs.

As you have no doubt noticed, there are some graphs which can be drawn in the plane so that edges meet only at vertices, and others, such as the complete bipartite graph K_{3,3}, where there is no “room” to draw the edges without having them intersect at other points. Graphs of the first type are called planar graphs; the others are called non-planar. One interesting question is whether it is possible to characterize which graphs are planar and which are not. There is a famous theorem due to Kuratowski which gives a complete answer to this question, and which would be your focus for this project. The background needed for the proof is covered in Chapter 13 of our text, but Brualdi does not give a complete proof of the Kuratowski theorem. For that, you should consult Chapter 9 on Graph Theory with Applications by Bondy and Murty (on Reserve in the Science Library for our class). Bondy and Murty also give an algorithm to check a graph for planarity. A nice added touch if you tried this topic would be to implement the planarity algorithm in the programming language of your choice, and illustrate the theorem by testing several example graphs.

The second group of topics below have more prerequisites in linear and abstract algebra. Give these a look. They indicate some interesting applications of algebraic ideas to combinatorial questions!

V. Error-Control Codes.

For this project, you would start in by learning some of the basics of the theory of linear codes over finite fields – one of the most interesting applications of abstract algebra and combinatorics to a real world problem (in my opinion at least!). Learn the basics of the Hamming distance and how it measures error-correcting capacity of a code. Then go on to linear codes, generator and parity-check matrices. Finally look at the definition of a perfect code and see how this reduces to a great combinatorial problem. Find the key examples of perfect codes that are known (Hamming and Golay codes) and describe them. To get started on this topic, you might begin by consulting the coding theory textbook Fundamentals of Error-Correcting Codes by Huffman and Pless (on reserve in the Science Library for our class), or any one of the other coding theory texts in our library. There is also a decent set of lecture notes for a minicourse on coding theory that I cowrote with a friend at Loyola Marymount in Los Angeles available at

http://mathcs.holycross.edu/~little/SACNAS2004.pdf that you may find useful.

VI. Latin Squares, Algebra, and Finite Projective Planes.

A Latin square is an n × n array in which the entries {1, 2, 3, …, n} appear exactly once each in each row and each column. For example,

( \begin{matrix}1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \\ 3 & 1 & 4 & 2 \\ 4 & 3 & 2 & 1 \end{matrix} )

is a 4 × 4 Latin square. (Note: this is also the group table for multiplication modulo 5(!) if we leave out the class of 0.) Latin squares occur in many applications of combinatorics such as the design of statistical experiments.

There is an interesting connection between Latin squares and algebra, starting with the observation that any finite group table gives an example! For a deeper connection, pairs of orthogonal Latin squares have many connections with finite affine and projective geometries and finite fields. For this topic, you should choose some particular aspect of this story and present it, along with examples, etc. There’s much more than can be done in 10 pages and a lot of current research here, so you’ll need to be selective. If you want to try this topics, see me after you’ve had a chance to look over some of this so we can talk about the choices. Chapter 10 of Brualdi, Chapter 5 of Bryant Aspects of Combinatorics, and Chapter 13 of Combinatorial Theory by Hall (on Reserve in the Science Library for our class) are good references for this.

VII. The van der Waerden Conjecture.

The permanent of a square matrix M is the scalar obtained by expanding along any row or column as in the computation of the determinant, but using all plus signs rather than alternating + and −. The permanent of a 0,1-matrix M gives a way to count the number of different “transversals” (collections of 1’s, one in each row and one in each column) that M contains. In 1926, van der Waerden conjectured that

perm(M) ≥ \frac{n!}{n^{n}}

for any n × n doubly stochastic matrix; and that the minimum was achieved if and only if M was the n × n matrix all of whose entries are 1/n. The corresponding result for a 0,1-matrix M with constant row and column sum s would be that

perm(M) ≥ \frac{s^{n}n!}{n^{n}}

This conjecture remained unresolved until 1980(!) when it was settled (affirmatively) by Egorychev. For this project, you would learn this proof (which contains a lot of good linear algebra – eigenvectors and symmetric bilinear forms!!) and give an expository account of it. The section 5.3 of Combinatorial Theory by Hall (on Reserve in the Science Library for our class) is a good reference for this.

VIII. Möbius Inversion.

The Inclusion-Exclusion Principle that we have studied is a first instance of a general pattern concerning partial order relations on finite sets. The general version is called the Möbius inversion formula. This has many applications in number theory and other algebraic subjects that touch on combinatorics. For this project, you would learn about the basics and show how the general Möbius Inversion formula applies in several different settings. Section 6.6 in Brualdi contains everything you will need here, but be aware that that section builds on two other sections (4.5 and 5.7) that we have not covered in class. So you will probably want to read those too.