Jacqueline Markot, Gerardina Bueti, Matthew Surabian – Error Control Codes

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:

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.

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 = ( \begin{matrix}1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{matrix} )

Some Specific Comments

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 F_{q}.

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.

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 F_{q} is F_{q}^{k}. Similarly, if the codewords are of length n, the set of all possible codewords is F_{q}^{n}.

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.

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 ∈ C.

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 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).

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 F_{2}^{n} is given by this sum since you can add any vector of weight ≤ e to x to get a word in this ball. The sum here is just the total number of words of weight ≤ e. Do you see why?

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:

a) d(u, v) ≥ 0 for all u, v and d(u, v) = 0 if and only if u = v.

b) d(u, v) = d(v, u) for all u, v.

c) (triangle inequality) d(u, v) ≤ d(u, w) + d(w, v) for all u, v, w.

Grade:

Molly Freeman, Erin Lord, Azadeh Shoraki, Courtney Walls – Error Control Codes

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.

Some Specific Comments

1) Actually, you mean to say here “will receive the correct message or only correctable errors”.

2) Don’t want + signs here. We usually think of the symbols in a codeword as the

components of a vector:

(C_{1}, C_{2}, …, C_{n})

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 ≤ 1 (no error at all or a single bit error – correctable with the Hamming code). Then the (.9999529858)^{1000} is the probability that the whole message gets through with no uncorrectable errors.

4) Small point – you can compute d(u, v) for 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.

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:

a) d(u, v) ≥ 0 for all u, v and d(u, v) = 0 if and only if u = v.

b) d(u, v) = d(v, u) for all u, v.

c) (triangle inequality) d(u, v) ≤ d(u, w) + d(w, v) for all u, v, w.

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.

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 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).

8) Why does H have this form? Explain!

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!

10) It would be nice to show exactly why the sum ∑_{i=0}^{3} \binom{23}{i} works out to 2048.

11) I don’t know exactly what you mean by “simplistic” here. What is true is that nontrivial perfect codes are 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 simple at all!!!

Grade:

Nicola Torchia, Andrew Finn, Chanda Nyendwa – The Matrix-Tree Theorem and the Cayley Tree Theorem

This is a 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 × n all 1s 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.

Some Specific Comments

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.

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!

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.)

4) As noted above, what you have written is not a proof of the formula you need for the characteristic polynomial of J = ℓ × ℓ all 1s matrix. Here’s one way to show that det(J − λI) = (−1)^{ℓ}(λ^{ℓ} − ℓλ^{ℓ−1}), which is what you need. (This implies that when ℓ = n − 1 and λ = n, then

det(nI − J) = n^{n−1} − (n − 1)n^{n−2} = n^{n−2}.)

So we must show that for the ℓ × ℓ all 1’s matrix J,

det(J − λI) = (−1)^{ℓ}(λ^{ℓ} − ℓλ^{ℓ−1})

We’ll do this in a kind of indirect way, by identifying what the eigenvalues of J are. First note that J is singular for all ℓ ≥ 2. λ = 0 is an eigenvalue since ker(J) ≠ {0}. In fact, note that dim ker(J) = ℓ − 1 since the ℓ − 1 vectors

(1, −1, 0, …, 0)^{t}, (1, 0, −1, 0, …, 0)^{t}, …, (1, 0, …, 0, −1)^{t}

are a basis for ker(J). By general facts about eigenvalues, this implies that λ = 0 is a root of det(J − λI) of multiplicity at least ℓ − 1 so λ^{ℓ−1} divides det(J − λI). On the other hand, λ = ℓ is also an eigenvalue of J, since

J(1, 1, …, 1)^{t} = (ℓ, ℓ, …, ℓ) = ℓ(1, 1, …, 1)^{t}

Hence λ − ℓ also divides det(J − λI). But then

det(J − λI) = ±λ^{ℓ−1}(λ − ℓ) = ±(λ^{ℓ} − ℓλ^{ℓ−1})

as claimed, since the total degree of the characteristic polynomial of an ℓ × ℓ matrix is exactly ℓ . This completes the proof.

Grade:

Darren Andrade, Matthew Fanning, Jean-Paul Le Fave – Latin Squares

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.

Some Specific Comments

1) This sounds somewhat funny (and “PC” too!) In Euler’s time, of course, officers would never have been female!

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 any finite group at all. The group tables for all finite groups give examples, and this is one algebraic way to show that n × 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′.)

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 ≥ 1. They were first studied by the French mathematician Évariste 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.

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 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 Z_{p} is a field. The construction works like this. You can think of the set of ordered pairs Z_{p}^{2} geometrically as an “affine plane” over the field Z_{p} (just like 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 ∈ 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 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.

Grade:

Ingrid Gliottone, Mackenzie Kielman, Lisa Melanson, Elisabeth Charnley – Edge Coloring of Graphs

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önig’s theorem for bipartite graphs and the Vizing Theorem for general graphs are also both good.

Some Specific Comments

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 vertex coloring, not edge coloring problems. There are important differences between these two types of problems.

2) I think the Y here is supposed to be a ⋃ union symbol. Is this a printer problem?

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.

4) Not exactly. Usually you would set up a 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önig’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.

Grade:

Michelle Humberd, Amy Jarboe, Bridget King, Elizabeth Vom Scheidt – Edge Coloring in Graph Theory

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 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.

Some Specific Comments

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 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 χ_{e}(K_{3}) = 3. A bigger example might have been nice too!)

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.

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 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.

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} ∪ 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.

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.

Grade:

Meghan Frazier and Erin Wall – An Exploration of Edge-Coloring

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önig’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.

Some Specific Comments

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.

2) You almost have the general idea of the proof of König’s theorem (see above). Why didn’t you include the whole thing? That would have been a nice addition.

3) You should include the proof of this lemma. It’s the major portion of the proof of Vizing’s Theorem(!)

4) In your example in fact, χ_{e}(G) = 1, since there is only one edge.

5) I don’t think it’s quite correct to call the process you are describing here an 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 only remove the edges from v to vertices in G_{2}, leaving the connections to G_{1}:

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.

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önig’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önig’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.

Grade:

Packy Loughran and Lukasz Jaroszewicz – Max-Flow Min-Cut Theorem

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).

Some Specific Comments

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 flow, and that can involve multiple paths from the source vertex to the sink vertex.

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.

3) Ford and Fulkerson’s definition of a cut is not exactly what other people do for this concept. Also, the notation (X, X̃) is not explained so it’s not very clear what you mean here. The idea is that (X, X̃) represents a set of arcs (edges) in the network – all edges joining some x ∈ X to some x̃ ∈ 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.

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, X̃) = c(X, X̃). Then the Lemma implies that the cut is of minimal capacity – all cuts have capacity at least that large.)

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.

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 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.

Grade: