\def\ssc{\bigskip\noindent{\it Some Specific Comments}\bigskip}
\def\finish{\bigskip\noindent{\it Grade: }\vfill\eject\noindent}
\magnification=\magstep1
\noindent
{\it Jacqueline Markot, Gerardina Bueti, Matthew Surabian -- Error Control 
Codes}
\bigskip
This is a generally good introductory account of the beginnings of the 
mathematics behind error control codes.  Most of what you say is 
correct and pretty well presented.   The main ``missing pieces'' that 
I would have liked to see are:
\bigskip
\item{1)}  A fuller discussion of the properties of the 
Hamming distance (see Comment 8 below), and then using that
a precise statement of 
the reasoning (i.e. the proof!) that shows that if the minimum distance
of a code is $d = 2e + 1$, then you can correct any $e$ bit or symbol
errors in a received word by finding the codeword closest to the
received word.  You use this in the discussion of perfect codes
without really saying why it is true. Since this result is probably the 
most important single idea in coding theory and it would have been good 
to give a complete account of this.  
\item{2)}  Some explicit examples of codes.  For instance, you discuss
Hamming codes in the last section, but you don't ever look at an 
explicit example.  You could do this by introducing the generator
matrix for an $n = 7, k = 4$ binary Hamming code for instance.  One
such code has
$$G = \pmatrix{1& 0 & 0 & 0 & 1 & 1 & 1\cr
0 & 1 & 0 & 0 & 0 & 1 & 1\cr
0 & 0 & 1 & 0 & 1 & 0 & 1\cr
0 & 0 & 0 & 1 & 1 & 1 & 0\cr}$$
\ssc
\item{1)}  As you say later, not all codes are binary.  In fact any 
finite alphabet could be used.  The most common choices are the
finite fields ${\bf F}_q$.
\item{2)}  This is not a true statement (the way you said it!)  I
think what you mean is that most of the codes that people actually
use in applications are linear.
\item{3)}  You are missing some exponents here.  Usually we think
of the original message as being divided up into words of length
$k$ so the set of possible message words over the alphabet ${\bf F}_q$
is ${\bf F}_q^k$.  Similarly, if the codewords are of length $n$,
the set of all possible codewords is ${\bf F}_q^n$.
\item{4)}  Careful with the notation.  In coding theory, $n$ is 
always used to refer to the blocklength of the codewords.  $k$
is the dimension of a linear code.
\item{5)}  Again, this statement isn't true the way you say it.  (You
need to say the condition you mention after this earlier!)
The key property of the parity check matrix $H$ is that it should
be the coefficient matrix for a system of homogeneous linear
equations whose space of solutions is the code $C$.  This can be
rephrased as saying $GH = 0$, where $G$ is the generator matrix,
or $cH = 0$ for all codewords $c \in C$.  
\item{6)}  What you are describing here is a simpler form of 
encoding by adding a single parity check bit.  For the $n = 7, k = 4$
Hamming code, for instance, you actually end up adding {\it three}
``parity check bits'' to each message word of length $k = 4$ to get
the corresponding codeword.  These extra bits do error detection 
and correction in an analogous, but more sophisticated way.  And
in fact it is not true in that case that all the codewords have
weight of the same parity.  (There are some of weight 3, some of weight
4 and one of weight 7).  
\item{7)}  It would have been good to explain in more detail where
these sums are coming from.  (They're the result of counting
problems very similar to things we did earlier in the course.)
For instance, the number of words in the Hamming ball of radius
$e$ centered at any word $x$ in ${\bf F}_2^n$ is given by 
this sum since you can add any vector of weight $\le e$ to
$x$ to get a word in this ball.  The sum here is just 
the total number of words of weight $\le e$.  Do you see why?
\item{8)}  It would have been good to say more about the properties
of the Hamming distance here.  In particular, you should mention
that it satisfies ``the usual properties'' of a distance function:
\itemitem{a)}  $d(u,v) \ge 0$ for all $u,v$ and $d(u,v) = 0$ if and only 
if $u = v$.  
\itemitem{b)}  $d(u,v) = d(v,u)$ for all $u,v$. 
\itemitem{c)}  (triangle inequality) $d(u,v) \le d(u,w) + d(w,v)$
for all $u,v,w$.

\finish
\noindent
{\it Molly Freeman, Erin Lord, Azadeh Shoraki, Courtney Walls -- Error Control 
Codes}
\bigskip
Very good account of the beginnings of the mathematics of error control
codes.  You have included enough information about the applications
and enough explicit examples to make this a nice introduction.

I have a few specific comments.
\ssc
\item{1)}  Actually, you mean to say here ``will receive the correct
message or only correctable errors''.  
\item{2)}  Don't want $+$ signs here.  We usually think of the 
symbols in a codeword as the components of a {\it vector}:
$$(C_1,C_2,\ldots,C_n)$$
\item{3)}  It would have been nice to break this up a bit.  The 
$.9999529858$ is the probability that any single received word will 
have an error of weight $\le 1$ (no error at all or a single bit
error -- correctable with the Hamming code).  Then the 
$(.9999529858)^{1000}$ is the probability that the {\it whole message}
gets through with no uncorrectable errors.
\item{4)}  Small point -- you can compute $d(u,v)$ for {\it any}
words $u,v$.  That is you can use it to compare how far apart
codewords are, etc., in addition to measuring the number of bit
errors in a received word.
\item{5)} 
It would have been good to say more about the properties
of the Hamming distance here (and prove them -- they aren't hard!).  
In particular, you should mention
that it satisfies ``the usual properties'' of a distance function:
\itemitem{a)}  $d(u,v) \ge 0$ for all $u,v$ and $d(u,v) = 0$ if and only 
if $u = v$.  
\itemitem{b)}  $d(u,v) = d(v,u)$ for all $u,v$. 
\itemitem{c)}  (triangle inequality) $d(u,v) \le d(u,w) + d(w,v)$
for all $u,v,w$.
\item{6)} The reason linear codes are commonly used is precisely 
that they have generator and parity check matrices that simplify
encoding and decoding.  You could have mentioned that here. 
\item{7)}   What you are describing here is a simpler form of 
encoding by adding a single parity check bit for error detection.  For the $n = 7, k = 4$
Hamming code, for instance, you actually end up adding {\it three}
``parity check bits'' to each message word of length $k = 4$ to get
the corresponding codeword.  These extra bits do error detection 
and correction in an analogous, but more sophisticated way.  And
in fact it is not true in that case that all the codewords have
weight of the same parity.  (There are some of weight 3, some of weight
4 and one of weight 7).  
\item{8)}  Why does $H$ have this form?  Explain!
\item{9)}  You seem to have gleaned this from one of your sources.
Since it gets into ideas (combinatorial designs, blocks, etc.) that 
aren't familiar, it would have been better to leave this out!
\item{10)}  It would be nice to show exactly
why the sum $\sum_{i=0}^3 {23 \choose i}$ works out to 2048.
\item{11)}  I don't know exactly what you mean by ``simplistic''
here.  What is true is that nontrivial perfect codes are {\it extremely 
rare}.  When they do occur, they tend to have very interesting and
intricate properties.  For instance the Golay codes are veritable
goldmines of beautiful combinatorics.  They aren't {\it simple} at all!!!
\finish
\noindent
{\it Nicola Torchia, Andrew Finn, Chanda Nyendwa -- The Matrix-Tree Theorem
and the Cayley Tree Theorem}
\bigskip
This is a {\it very good} paper on the Matrix-Tree Theorem and how it applies
to give another proof of the Cayley Theorem on the number of labeled trees
on $n$ vertices.  I especially like that you looked for a topic of your
own and worked very hard to understand the rather terse account of 
the Matrix-Tree Theorem in Godsil's book.  (Note: it's a graduate
level textbook; that's pretty much typical of the way mathematics
is written at that advanced a level.  The reader has to do a lot
to fill in the details!)  I hope this was a good learning experience
for you.  The resulting paper certainly came out well.

The only major problem I have is with 
the ``proof'' of the formula for the characteristic polynomial
of the $n \times n$ all $1$s matrix $J$.  Your induction argument
is unfortunately not correct, because you didn't actually use the 
induction hypothesis to deduce the next case.  You essentially 
just asserted the statement for $n = k + 1$ without actually proving
it(!)  See comment 4 below for a complete proof of the formula here.

\ssc
\item{1)}  These assertions are true for the complete graph $K_n$ 
but not for general graphs.  Since you are describing the Laplacian
matrix in general here, this is out of place.
\item{2)}  A relatively minor quibble on organization.  This 
discussion would probably make more sense if you introduced
it after the statement of the Matrix-Tree theorem, but before
its proof.  If someone who didn't know the statement of the theorem
read this, they wouldn't know why you were introducing all these
matrices!
\item{3)}  Terminology:  ``spanning trees'' (A spanning tree of a
graph is a subgraph that is a tree and that uses all the vertices
of the whole graph.)
\item{4)}  As noted above, what you have written is not a proof of the formula
you need for the characteristic polynomial of $J = $ $\ell\times \ell$
all $1$s matrix.  Here's one way to show that 
$\det(J - \lambda I) = (-1)^\ell(\lambda^\ell - \ell \lambda^{\ell-1})$, which
is what you need.  (This implies that
when $\ell = n-1$ and $\lambda = n$, then
$$\det(n I - J) = n^{n-1} - (n-1) n^{n-2} = n^{n - 2}.)$$
So we must show that for the $\ell\times\ell$ all 1's matrix $J$, 
$$\det(J - \lambda I) = (-1)^\ell(\lambda^\ell - \ell \lambda^{\ell-1})$$
We'll do this in a kind of {\it indirect} way, by identifying what
the {\it eigenvalues} of $J$ are.  First note that $J$ is singular
for all $\ell \ge 2$.  $\lambda = 0$ is an eigenvalue since
$\ker(J) \ne \{0\}$.  In fact, note that $\dim\ker(J) = \ell - 1$
since the $\ell - 1$ vectors
$$(1,-1,0,\ldots,0)^t, (1,0,-1,0,\ldots,0)^t, \ldots, (1,0,\ldots,0,-1)^t$$
are a basis for $\ker(J)$.  By general facts about eigenvalues, this implies
that $\lambda = 0$ is a root of $\det(J - \lambda I)$ of multiplicity
{\it at least $\ell - 1$} so $\lambda^{\ell - 1}$ divides $\det(J - \lambda I)$.
On the other hand, $\lambda = \ell$ is also an eigenvalue of $J$, 
since 
$$J(1,1,\ldots,1)^t = (\ell,\ell,\ldots,\ell) = \ell(1,1,\ldots,1)^t$$
Hence $\lambda - \ell$ also divides $\det(J - \lambda I)$.  But
then 
$$\det(J - \lambda I) = \pm \lambda^{\ell-1}(\lambda - \ell)
= \pm (\lambda^\ell - \ell\lambda^{\ell - 1})$$
as claimed, since the total degree of the characteristic polynomial
of an $\ell\times\ell$ matrix is exactly $\ell$ .
This completes the proof.
\finish

\noindent
{\it Darren Andrade, Matthew Fanning, Jean-Paul Le Fave -- Latin Squares}
\bigskip
Very nice, polished paper on Latin squares and connections with algebra
and geometry.  You did a very good job putting everything together
and organizing the presentation.  It's OK that you didn't go deeper
into the connection with experimental designs because the paper was
plenty long already. But of course, that's an interesting practical
application of these ideas that might be fun to explore in more detail
some time.

\ssc
\item{1)}  This sounds somewhat funny (and ``PC'' too!)  In Euler's
time, of course, officers would never have been female!
\item{2)}  Your discussion of the Klein 4-group table as an example
of a Latin square and the theorem 2.1 below make it seem like
some special properties are necessary to get a Latin square
in this way.  But in fact the proof of theorem 2.1 adapts to 
{\it any finite group at all}.  The group tables for all finite groups
give examples, and this is one algebraic way to show that $n\times n$
Latin squares exist for all $n$.  (The reasoning is exactly
the same as what you do in your proof.  Say two elements 
in one row of a group table are equal:  $g * h = g * h'$.
Since $g$ has an inverse in the group this implies $h = h'$.
Similarly, if two entries in one column are equal we have
$g * h = g' * h$.  But $h$ has an inverse in the group, so 
$g = g'$.)
\item{3)}  This would be another interesting topic to 
pursue if you ever get the chance.  There is a standard
construction of fields of order $p^n$ where $p$ is any 
prime and $n \ge 1$.  They were first studied by the 
French mathematician \'Evariste Galois, so they are
sometimes called Galois fields.  They are extensively 
used in areas such as error-control coding theory and 
cryptography, besides being a beautiful topic in algebra.
\item{4)}  I know you didn't have much space here to 
describe the connection between finite projective planes
and mutually orthogonal Latin squares, but it would have
been nice to say a bit more about {\it exactly where} the projective
plane comes from when $n$ is a prime or
a power of a prime.  One way to say this is that we
can do a finite version of usual Cartesian coordinate
geometry.  Say $n = p$ is prime for simplicity,
so we have that ${\bf Z}_p$ is a field.  The construction works
like this.
You can think of the set of ordered pairs
${\bf Z}_p^2$ geometrically as
an ``affine plane'' over the field ${\bf Z}_p$ (just
like ${\bf R}^2$ gives the usual Euclidean plane, in
coordinate form).  In this plane, you have lines given
by equations $y = mx + b$, or $x = c$ (where $m,b,c \in {\bf Z}_p$).  Say two 
lines are parallel if they have the same ``slope'' $m$
or are both ``vertical''.
Then the projective plane comes by 
adjoining $p+1$ additional ``points at infinity'', one
corresponding to each parallel class of lines in the affine 
plane.   A smaller example called the {\it Fano plane}
(order $2$) would also have been good to present in 
detail.  The plane of order three in your diagram 
has a lot of ``lines'' and its not clear exactly which
points are in some of them.
\finish

\noindent
{\it Ingrid Gliottone, Mackenzie Kielman, Lisa Melanson, Elisabeth Charnley -- 
Edge Coloring of Graphs}

\bigskip 
Very good paper, for the most part, on edge coloring of graphs.
The last section on applications to the timetabling problem
is somewhat weaker than the rest (see comment 4 below).  
The proofs for the problems from Bryant are fine.  
The presentation of K\"onig's
theorem for bipartite graphs and the Vizing Theorem for
general graphs are also both good.  

\ssc
\item{1)} It's true that the general idea of graph coloring problems
probably can be traced back to the four-color map problem and 
related questions.  But be careful here.  In the corresponding graphs
there, the vertices represent the different countries, and the 
edges represent common boundaries between the countries.  The
coloring problems there are {\it vertex coloring}, not {\it edge
coloring} problems.  There are important differences between these
two types of problems.
\item{2)}  I think the $Y$ here is supposed to be a $\bigcup$ union
symbol.  Is this a printer problem?
\item{3)}  Careful how you say this here.  Saying a graph is Hamiltonian means that
there is a Hamilton cycle (a cycle that contains all the vertices
of the graph).  It's true that as you travel the Hamilton cycle,
you visit each vertex exactly once.  
\item{4)}  Not exactly.  Usually you would set up a {\it bipartite}
graph with ``left'' vertices corresponding to the classrooms (say),
and ``right'' vertices corresponding to the classes.  An edge
from a left vertex to a right vertex means that the corresponding 
classroom is where the corresponding class will meet.  But then
to avoid scheduling two classes in the same room at the same time,
the edges would be colored according to the different time periods
available.  K\"onig's Theorem applies in this case and says that
the edge coloring is always possible with $d = $ maximum vertex
degree distinct colors.  So if your bipartite graph is maximum
vertex degree $d$, then you need $d$ different time periods.
It might be possible to reduce this, of course, by rearranging
the edges (moving classes to different rooms). You essentially 
say something like this
in the next paragraph.  But the set-up isn't described exactly 
correctly here.

\finish
\noindent
{\it Michelle Humberd, Amy Jarboe, Bridget King, Elizabeth Vom Scheidt -- 
Edge Coloring in Graph Theory}

\bigskip
Your paper on edge coloring problems in graph theory is good on
the whole, but it's also rather uneven.  The first section on 
Vizing's Theorem and other general results is quite a bit
more polished than the middle section on timetabling problems.
This is partly a matter of writing style and following usual
procedures for citing your sources (see comment 3 below).
But there are also several things in that section that
seem like you have {\it not completely digested} what you found
in your sources (see comment 4), or at least not digested them
enough to be able to clearly explain them in your own words. 
The final section of solutions to problems from Bryant is 
quite good again, though.  Writing papers ``by committee''
can lead to some labor-saving if you split up topics.  But
it's still a really good idea to go through everything together
after you have a first draft so that things that seem clear
to the individuals who have worked on particular aspects
of the project are also clearly enough explained so that people who 
haven't been as actively involved in that part of the project
can follow.

\ssc
\item{1)}  This additional result is a nice complement to Vizing's
Theorem.  It would have been nice, though, to include an example
showing what can ``go wrong'' if you {\it do have} one of these cycles.  
(For instance the complete graph $K_3$ has $d = 2$, and a cycle
of degree 2 vertices -- namely the whole graph.  Note 
that $\chi_e(K_3) = 3$.  A bigger example might have been nice too!)
\item{2)}  The transition between the first section of the paper
(general results on edge-colorings) and the second section (on the timetabling
problem) is rather abrupt.  It would have been good to put in a sentence
or two to explain that you are now moving to an application of the
other results. 
\item{3)}  In a paper like this, you shouldn't just say ``Theorem 6.1''
or ``Lemma 6.3''
like this without identifying the book, article, etc. where the theorem
comes from(!)  What you did is not totally useless to help a reader
identify your sources.  Along the same lines, you should {\it always}
include a bibliography at the end of the paper where you list 
all the sources you consulted.  Then in the text, when you refer to 
a result from one of them, you can put in a ``pointer'' to one
of the bibliography items.
\item{4)}  This argument is somewhat garbled.  You're following 
an argument from the chapter on edge-coloring in Bondy and Murty's
book, but you have omitted things, and you have also not explained
a lot of the notation.  For instance, what does $G[E_i \cup E_j]$
mean?  Need to explain that this is their notation for 
an ``induced'' subgraph formed by a collection of edges in 
a larger graph.
\item{5)}  See comment 3 above!  Also, it would be good to 
point out that the fact about matchings that you are using 
here is essentially equivalent to problem 6 from the chapter
in Bryant's book.  It's OK that you didn't submit a solution
for that, given that your paper contains a bunch of additional
topics beyond the topic description, though.  

\finish

\noindent
{\it Meghan Frazier and Erin Wall -- An Exploration of Edge-Coloring}

\bigskip
Generally good paper on edge-coloring problems in graph theory. 
I mostly like the choice of what to include. The main 
exception is that it would have been good to go into more details
on the proof of K\"onig's theorem (the statement that a bipartite
graph with maximum vertex degree $d$ can be edge-colored with 
$d$ colors), and also on the proof of the lemma for Vizing's theorem.
Your solutions for two of the problems are also unnecessarily complicated.
See comment 6 below.

\ssc
\item{1)}  Good example.  But you could say more about
exactly what you are doing to ``chase'' colors back through
the graph when you start reversing the colors on the edges
starting at vertex $c$.
\item{2)}  You almost have the general idea of the proof of 
K\"onig's theorem (see above).  Why didn't you include the 
whole thing?  That would have been a nice addition.
\item{3)}  You should include the proof of this lemma.  It's
the major portion of the proof of Vizing's Theorem(!)
\item{4)}  In your example in fact, $\chi_e(G) = 1$, since
there is only one edge.  
\item{5)}  I don't think it's quite correct to call the process
you are describing here an {\it algorithm}.  You haven't
specified how to do things precisely enough for that.  I'm also
not sure whether what you have done covers all possible cases
that might arise.  The best way to prove this is to use
the previous problem in Bryant (number 2 in Chapter 7).  
That problem says that if you have a graph $G$ which can 
be edge-colored with $d$ colors, and in which 
all vertices except one have degree $d$, then there must 
be a vertex of degree 0.  To apply that to problem 3, 
let $v$ be the vertex whose removal (together
with all edges incident at $v$) disconnects $G$ into 
two pieces $G_1$ and $G_1$.  Say $v$ is connected to 
$k$ vertices in $G_1$ and $G_2$.  Suppose we {\it only}
remove the edges from $v$ to vertices in $G_2$, leaving
the connections to $G_1$:
\vglue 1.0truein
\item{} The resulting graph $H$ has all vertices of degree equal to $d$
except $v$, which has degree $k$.  If we assume that $G$
can be edge-colored with $d$ colors, then so can $H$.
But then by the previous problem, $H$ must have a vertex
of degree $0$.  That is a contradiction, so the original
graph $G$ cannot be edge-colored with $d$ colors. 
\item{6)}  The Hall's theorem portions of your solutions
for problems 5 and 6 are not actually necessary!  You can see
the results you want for both simply by applying K\"onig's
theorem to the appropriate bipartite graph.  For problem
5, set up the bipartite graph $G$ with one vertex set the boys,
the other the girls, and edges between friendly pairs.
The statement of the problem implies that the degrees
of all vertices are $d$.  Then K\"onig's theorem
says you can edge-color $G$ using $d$ colors.  Taking the 
edges of each color gives one of the matchings into ``friendly pairs''.
The idea for 6 is almost exactly the same.  The bipartite
graph there has maximum vertex degree $d$ again.  So
it can be edge-colored with $d$ colors.  The edges
of each color give one of the $(0,1)$-matrices you want.

\finish

\noindent
{\it Packy Loughran and Lukasz Jaroszewicz -- Max-Flow Min-Cut Theorem}
\bigskip
This is a reasonably good paper on the Max-Flow Min-Cut theorem.
The history was interesting -- didn't know that before.  The main
comment I have is that when you base your presentation primarily
on one source like the Ford-Fulkerson book, it's still necessary 
to explain the notation, especially when it's a bit different from
what other presentations use (see comments 3 and 4).  You should also 
still include a short bibliography listing your source(s).  

\ssc
\item{1)}  ``Path'' is probably not a good choice of words here.
There are paths through the network involved, but the thing that
is optimized is the total network {\it flow}, and that can
involve multiple paths from the source vertex to the sink vertex.
\item{2)}  Careful.  It is not necessarily the case that the 
maximum flow through the network uses the full capacity on 
every edge.  Due to ``bottlenecks'' at subsequent points, it
might not use the full capacity.
\item{3)}  Ford and Fulkerson's definition of a cut is not
exactly what other people do for this concept.  Also, the notation
$(X,\tilde X)$ is not explained so it's not very clear what 
you mean here.  The idea is that $(X,\tilde X)$ represents
a {\it set of arcs (edges)} in the network -- all edges joining
some $x \in X$ to some $\tilde x \in \tilde X$.  Most other
books that discuss the Max-Flow Min-Cut theorem don't set up 
the cut arcs quite this way.  They would describe the cut
by giving a specific set of arcs.  So it would have been good
to explain this in more detail and maybe even do a preliminary
example at this point, just to nail the idea down.  
\item{4)}  Careful, you're asserting the statement to be 
proved!  (You want to assume the flow is maximal and show
there is some cut with $f(X,\tilde X) = c(X,\tilde X)$.
Then the Lemma implies that the cut is of minimal capacity --
all cuts have capacity at least that large.)
\item{5)}  You have left out one of the steps of the proof
here.  Namely, it is necessary to show why $t$ cannot be
an element of $X$.  This is the argument on the top of page 12
in Ford and Fulkerson's book.  The proof is not really complete
without that.
\item{6)}  General comment on the examples.  These are OK, but
it would have been much more interesting to find (or create!)
examples where the minimum capacity cut was not an ``obvious''
one.  By ``obvious'' I mean things like cuts using all the
edges out of $s$ or all the edges going into $t$.
(In Ford and Fulkerson's notation that would be $X = \{s\}$
or $\tilde X = \{t\}$.)  The theorem is much more interesting
and valuable in cases where there's some internal ``bottleneck''
in the ``middle'' of the network between $s$ and $t$ that
gives the minimum capacity cut.  

\finish
\bye



