Math 511: Introduction to Combinatorics
Spring, 2019
Notes
Main course page | Syllabus | Presentations | Assignments
My home page
Announcements
- 4/15 after class: Problem session on Ch. 18-19.
Recommended problems: 18C, 19A, 19C, 19E, 18AA, 19AA, 19BB.
You should look at them all. I don't expect you to solve them all— that's why we have a problem session!
- 4/26, 1:10 p.m.: Problem session on Ch. 19, 22.
Recommended problems: 19B, 19D, 19K, 19CC.
You should look at them all. Try to understand each question. You don't have to work on all questions.
Terminology and notation
- I use [n] := {1,2,...,n} for n ≥ 0.
- I prefer N(x) for the neighborhood of a vertex x. They prefer Γ(x).
- P. 5, "path": This is nonstandard. It is usually called a "trail", and a "path" is a walk with no repeated edges or vertices (the book's "simple path"). This is important because I normally use "path" the latter way and I might confuse you (or me).
- P. 5, "polygon": This is usually called a circuit or cycle and denoted by Cn. (Usually, Pn denotes a path.)
- P. 15, "arborescence". Many would call this an "in-arborescence" and the tree with edges directed away from the root an "out-arborescence".
- P. 21, "strong" walk. This is usually called a directed walk.
- Ch. 23: A "combinatorial geometry" is better known nowadays as a "simple matroid". They shorten this to "a geometry", but that is truly bad terminology.
I'll be doing a lot more with matroids (and graphs and affine and projective geometry) next semester.
Corrections to the textbook
- Index.
- Derived design, add p. 219.
- Residual design, add p. 220.
- P. 24: "If k is odd then χ(Pk) = 3." Remember that P denotes a polygon.
- Symmetric chains. The book's definition is not satisfactory to me. There are two properties of the chains in a symmetric chain decomposition: (1) Symmetry. (2) Completeness. They ought not be blended together in one definition.
- Symmetry means that if the chain has an element at level i, then it has an element at level n−i. In other words, it is symmetric about the middle level.
- A complete chain in any poset is a chain in which each element (except the least, of course) covers the previous one.
A symmetric chain decomposition of the power set of S is a decomposition of S into chains that are both symmetric and complete.
- The number-theoretic Möbius inversion theorem 10.4 is an if-and-only-if theorem. The proof is easy via the recursive definition of μ that I showed in class.
- Problem 14C correction. They meant to ask for a one-to-one correspondence, not merely a mapping. The problem doesn't really make sense without the correction.
- Problem 14D correction. The hint should say M1(0) = 0.
- Problem 14K correction. The factor x should be x3. If you compute the n = 1 term of the series, you immediately see their rational function can't be correct.
- P. 224, line 1, should read "t ≥ 6".
I was at Ohio State with Teirlinck (and Ray-Chaudhuri and Wilson) when he found his constructions of simple t-designs for all t ≥ 6. Experts like Wilson were very impressed. I was too naive to properly understand it.
- Problem 19H(2) seems to require that the derived design Dp with respect to every point p be symmetric. I can't say this is a necessary assumption; I only can't see how to avoid it.
- Example 23.2 refers to Problem 19R, which should be 19Q. But you may ignore this.
- Example 23.4 says "1-dimensional (linear) subspaces". Here "(linear)" is supposed to remind you that the subspaces are linear, not affine. It does not mean that "linear" is a synonym for 1-dimensional!
- Hints for Ch. 23: All the hints are lettered too low. Hint 23A is the hint for Problem 23B, etc., up to Hint 23I which goes with Problem 23J. Alas, there is no hint for Problem 23A.
Additions to the textbook
- P. 19, depth-first and breadth-first search. My different explanation in class also explains the names.
- Brooks' Theorem Proof 1: Here is a better outline. We assume G is a minimal counterexample. Let x ∈ V.
- Color G−x in d colors. Note that every color 1, 2, ..., d appears in N(x), no matter which coloring is chosen.
- Label N(x) so xi has color i. Define Hij and Cij. Prove xi and xj are connected in Hij.
- Prove Cij is a simple path from xi to xj.
- Prove Cij ∩ Cik = {xi}.
- Choose two non-neighbors in N(x). For simplicity, call them x1, x2. Let ax1 be the first edge in C12, so a has color 2.
Take x3 ∈ N(x). Reverse colors in C13, forming coloring '. Show a ∈ C12' ∩ C23', violating (4) in the new coloring. Contradiction!
- The Erdos-Ko-Rado Theorem 6.4 is missing part of the proof, which I filled in with the linked lemma.
- The proper name of "Euler's function" φ is Euler's totient function. Many people don't know that.
- The Catalan numbers are often written Cn = binom(2n,n)/(n+1).
- Problem 16A½. Regarding majorization, prove r* majorize s ⇔ s* majorizes r. I'm looking for two proofs: a direct combinatorial proof, and another proof.
- Equivalence of Latin squares that use the same alphabet is known as isotopy.
- Problem 18AA. Prove that in a finite field of odd order q,
- the number of nonzero squares = the number of nonsquares;
- χ(xy) = χ(x)χ(y).
- Organization of Chapter 19 on Designs
Ch. 19 seems at first like a jumble. Here is a way to put its contents in order. There are two main topics.
- Incidence geometry (p. 216). This has one topic:
- "Linear spaces". I wouldn't call these designs; they lack regularity and have an independent source.
- Designs (pp. 216-end). This is devoted to t-designs (which are the main part of combinatorial design theory) and especially 2-designs (the main part of t-design theory). The main aspects of the chapter are:
- Properties. This includes numerical constraints, such as integrality constraints, on possible designs.
- Constructions (the biggest single part of design theory in general). Given parameters that meet the numerical constraints, finding designs with those parameters, and if possible multiple designs (for actual use) is the big problem of design theory.
- Finite geometry.
- Hadamard matrices.
- Difference sets.
- Special cases:
- t = 2 is the main interest and is only loosely a "special case".
- λ = 1 has a geometrical flavor, especially when t = 2.
- Symmetric designs.
- Projective and affine planes: geometry and designs.
- Problem 19AA. What is a t-design with t = λ = 1? What are the possible values of v, k?
- Problem 19BB. What is a t-design with t = k? What are the possible values of v, k, λ?
- Problem 19CC. Apply the Bruck-Ryser-Chowla Theorem 19.12 to the question of projective planes (λ = 1, k = n + 1, v = n2 + n + 1) for the smallest non-prime-powers: n = 6, 10, 12, 14, 15. See how far you can get in deciding what the theorem tells you. Does it rule out any? Note that n = 6, 10 are Example 19.10.
- Problem 19H. I am working on a solution. I've gotten to Part (3). See the PDF file.
- Lemma 23LL. (Prove the lemma for self-study and discussion. Not to be handed in.)
Let α be an atom of a geometric lattice L, and let ρ be any element of L such that ρ ≱ α. Then ρ ∨ α covers ρ.
- Problem 25AA. (For self-study. Not to be handed in.)
(a) Find the analogs of Eqs. (25.1-2) that are derived from ζμ = δ. This is expected for self-study because it will help you understand μ.
(b) How is your formula related to Eqs. (25.1-2)? We'll discuss this in class after you have a chance to think about it.
Main course page | Syllabus | Presentations | Assignments
My home page