\magnification=\magstep1
\overfullrule=0pt
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Project Topics}
\centerline{March 14, 2005}
\bigskip\noindent
{\it General Information}
\bigskip
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 
{\it 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.  
\bigskip
\noindent
{\it Schedule}
\bigskip
\noindent
Here are some important dates for the projects:
\bigskip
\item{1.}  {\bf 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.
\item{2.}  {\bf 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.
\item{3.}  {\bf Wednesday, May 4}:  Final projects due.  This is an 
{\it absolutely firm} deadline--no extensions will be possible, so
please don't ask.
\bigskip\noindent
{\it Suggested Topics}
\bigskip
\noindent
The first group oftopics rely mostly on the definitions of graphs, directed
graphs, and so on.  They have few other prerequisites.
\bigskip
\noindent
I.  The K\"onig-Egerv\'ary theorem.
\bigskip
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\"onig-Egerv\'ary 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 {\it 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  {\it 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 
{\it Graph Theory with Applications\/} by Bondy and Murty .

\bigskip
\noindent
II.  Directed Graphs and The Max Flow-Min Cut Theorem.
\bigskip
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  {\it Aspects of
Combinatorics} (on Reserve in the Science Library for our class), 
and Chapter 11 of {\it Graph Theory with Applications\/} by Bondy 
and Murty (on Reserve in the Science Library for our class).

\bigskip
\noindent
III.  Edge-Coloring of Graphs.
\bigskip
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 
{\it 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 {\it 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 {\it 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 
{\it Graph Theory with Applications\/} by Bondy and Murty (on Reserve
in the Science Library for our class).

\bigskip
\noindent
IV.  Planar Graphs.
\bigskip
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 {\it planar\/} graphs; the others are called non-planar.
One interesting question is whether it is possible to 
{\it 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 
{\it 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.
\bigskip
\noindent  
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!

\bigskip
\noindent
V.  Error-Control Codes.
\bigskip
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 {\it 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 {\it 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
{\tt http://mathcs.holycross.edu/\~{}little/SACNAS2004.pdf}
that you may find useful.

\bigskip
\noindent
VI.  Latin Squares, Algebra, and Finite Projective Planes.
\bigskip
A {\it Latin square} is an $n\times n$ array in which 
the entries $\{1,2,3,\ldots, n\}$ appear exactly once each
in each row and each column.  For example,
$$\pmatrix{1 & 2 & 3 & 4\cr
           2 & 4 & 1 & 3\cr
           3 & 1 & 4 & 2\cr
           4 & 3 & 2 & 1\cr}$$
is a $4\times 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 {\it 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 {\it Aspects of Combinatorics}, and 
Chapter 13 of {\it Combinatorial Theory\/} by Hall (on Reserve
in the Science Library for our class) are good references for 
this.
\bigskip
\noindent
VII.  The van der Waerden Conjecture.
\bigskip
The {\it 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 {\it 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 
$${\rm perm}(M) \ge {n! \over n^n}$$
for any $n\times n$ {\it doubly stochastic\/} matrix; and that 
the minimum was achieved if and only if $M$ was the $n\times 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
$${\rm perm}(M) \ge {s^n n! \over 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 {\it Combinatorial Theory\/} by 
Hall (on Reserve
in the Science Library for our class) is a good 
reference for this.
\bigskip
\noindent
VIII.  M\"obius Inversion.
\bigskip
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\"obius 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\"obius 
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.
\bye

