# Combinatorial Mathematics - Errata, etc.

This page contains supplementary items for the first edition of Combinatorial Mathematics, by Douglas B. West, published in July 2020 by Cambridge University Press. Sections include mathematical and notational errors, corrections to references, comments and updates, and supplementary problems.

Send contributions of errors, comments, or supplementary problems to dwest@illinois.edu; contributors noted in parentheses. Locating codes: X=Exercise, T=Theorem, L=Lemma, P=Proposition, C=Corollary, E=Example, J=Conjecture, R=Remark. $\def\nul{\emptyset}\def\NN{{\bf N}}\def\ZZ{{\bf Z}}\def\RR{{\bf R}} \def\FL#1{\lfloor{#1}\rfloor}\def\CL#1{\lceil{#1}\rceil} \def\C#1{\left|{#1}\right|} \def\esub{\subseteq} \def\FR#1#2{{{#1}\over{#2}}} \def\st{\colon\,} \def\join{\vee} \def\Sb{\overline{S}} \def\cart{\square} \def\CH#1#2{{#1\choose #2}} \def\XPOL#1#2{\chi_{#1}(#2)} \def\VEC#1#2#3{#1_{#2},\ldots,#1_{#3}} \def\D{{\diamond}}$

## Mathematical and notational errors

• p133 X3.3.21: In part (b), the factor "$i^{\FL{m/i}}$" should be "$i^{\FL{m/(i-1)}}$".
• p235 X5.3.3: Part (c) is ambiguously stated. It was intended to be "For each vertex $v$ in a circuit, the circuit contains a cycle through $v$", without requiring a single cycle through all the vertices (containment is in the sense of Lemma 5.3.8).
• p256 R6.1.4 vs pre-C6.1.6: Before Corollary 6.1.6 the lower bound from Remark 6.1.4 for the number of perfect matchings in a $k$-regular bipartite graph is compared with the lower bound from van der Waerden's Conjecture for the same number over $k$-regular bipartite multigraphs with $n$ vertices in each part. The latter is NOT weaker. The problem is that 6.1.4 does not take $n$ into account, so it is a lower bound over all $n$. In 6.1.4 the leading behavior of the bound is $(k/{\rm e})^k$, while using vdW and incorporating $n$ the leading behavior is $(k/{\rm e})^n$. (Sasha Kostochka)
• p342 X8.1.12: Technically, if $G$ is disconnected, then blocks can also be isolated vertices.
• p441 X10.1.21: In the hint, $\sum_{i=1}^r$ should be $\sum_{j=1}^r$. (Leen Droogendijk)
• p442 X10.1.37: In part (a), "$\CL{n+1}2$" should be "$\CL{(n+1)/2}$". In part (b), all runs with size $k$ and stepping by $k$ have the form $(k-i,2k-i,\ldots,k^2-i)$. This specifies the runs but not their order. The runs were intended to be put in order from $i=0$ to $i=k-1$, as is done in the given example. (Leen Droogendijk)
• p460 X10.2.36: Part (c) is correct as stated, but there is a third lower bound that is stronger when $r$ and $s$ are small: $r+s+2$. The statement in (d) that the formula is an upper bound needs this expression to be included when $2\ge s\ge r-2$. The claimed Ramsey number is obtained in J.W. Grossman, The Ramsey numbers of the union of two stars, Utilitas Math. 16 (1979), 271-279 (also mentioning Rosta's discovery of the result).
• p497 T11.2.14: In the last paragraph, "all sets above $|\partial A|$" should be "all sets above $\partial A$". (Stephen Hartke)
• p766 X15.2.34c: "$\varnothing$" should be "$\{0\}$". (Stephen Hartke)
• p794 T16.1.31: There is a difficulty with points appearing in only two unit pairs, since the circle around such a point generates two copies of the same edge. The best fix is to iteratively delete points lying in at most two unit pairs (this also replaces the argument of the first paragraph). Since $4n^{4/3} > 4(n-1)^{4/3} + 2$, the bound we obtain for the resulting set suffices. (Michael Pelsmajer)
• p798 X16.1.23: The bound should be $4n^{2/3}m^{2/3}+m$, not $4n^{2/3}m^{2/3}$. (Michael Pelsmajer)
• p843 X10.1.19: $S$ in the hint refers to a given multiset of $k$ positive integers with sum $n$. (Leen Droogendijk)

## Bibliographic items

Due to an error in the cross-referencing program, it seems that every citation that appears in the first paragraph of any page has been recorded in the references as being on the preceding page. When looking for where an article is cited, please check the first paragraph of the subsequent page if you can't find it on the page listed.

• p105 X3.1.27: Another bijection relating these sets appears in W. Y. C. Chen, The skew, relative, and classical derangements, Discrete Math. 160 (1996), 235-239. (David Callan)
• p174 X4.1.39: The inclusion-exclusion argument for this formula may appear in Brualdi's book as early as the 1992 edition.
• p249 X5.4.27: The problem of finding the largest $f(n)$ such that some $n$-vertex graph with $n+f(n)$ edges has no two cycles with the same length was originally posed by Erdős in 1975. Shi [1988] proved roughly $f(n)\ge\sqrt{2n-4}$. The CM text mis-states the result of Chen-Lehel-Jacobson-Shreve [1988], which is $f(n)\le O(\sqrt{n\log n})$ (also proved earlier in Lai [1990]). Lai [2020] improved the lower bound to $f(n)\ge 1.55\sqrt n$, and Boros-Caro-Füredi-Yuster [2001] proved $f(n)\le 1.98\sqrt n$. The restriction of the problem to $2$-connected graphs has been solved asymptotically; the number of edges is $n+f_2(n)$ where $f_2(n)\sim \sqrt{n}$. The lower bound is in Boros-Caro-Füredi-Yuster [2001], upper bound in Ma-Yang [2020+]. (Chunhui Lai)

• p114 X3.2.12 and p116 X3.2.33: Unfortunately, these two are the same exercise, in slightly different notation.
• p128 X3.2.28: An excellent exercise; should be marked ($\D$). There should be a hint in the back reminding solvers to be careful about which square root of $(1-2p)^2$ makes sense. With this, the computations in parts (a) and (b) both work out nicely for the relevant values of $p$. (Kevin Milans)
• p150 X3.4.26: This problem is worthy of ($\D$).
• p207-208 X4.3.13,19,20: These ($\D$) exercises are fairly long.
• p228 X5.2.34 and p255 C6.1.5: A proof of C6.1.5 by directly improving a given orientation is requested in X5.2.34.
• p270-1 D6.2.17-T6.2.19: This is wonderful material but should have been marked optional; it is beyond the basic course.
• p273 X6.2.20: There is nice non-inductive proof using augmenting paths.
• p297 X7.1.25: Parts (a) and (b) are suitable exercises separately.
• p419 X9.3.24: This exercise generalizes Exercise 8.1.29.
• p441 X10.1.18: It is better to ignore the ceiling function in the upper bound.
• p460 X10.2.32: One can also ask when $k=3$ to guarantee a monochromatic subgraph with more than half the vertices if $n$ is not divisible by $4$.
• p747 X15.1.33: The 2001 conjecture by Ramamurthi that the hypergraph of facial vertex sets of a planar graph is $2$-choosable was proved (and strengthened) in C. Thomassen, 2-list-coloring planar graphs without monochromatic triangles, J. Combin. Theory Ser. B 98 (2008), no. 6, 1337-1348. (André Kundgen)
• p793 T16.1.28: Eyal Ackerman proved that the lemma holds with $1/29$ instead of $1/64$ in the lower bound if $m > 7n$. (Laszlo Szekely)

## Minor Typos

• pxix: Regarding the result of Grytczuk and Zhu mentioned in the preface, "show that" should be "showing that".
• p459 X10.2.14,20: Elsewhere in the book, a roman "e" is used for the base of the natural logarithm.
• p558 T12.2.15: The "$\FL{n/2}$" in the problem statement changes to "$\CL{n/2}$" at the end of the proof, but it doesn't matter because the binomial coefficients are equal. (Stephen Hartke)
• p583 X12.3.15: "non-cut vertices" should be "non-cut-vertices". (Stephen Hartke)
• p798 X16.1.19: The exercise ends with the label "(Comment:", which inadvertently did not get removed when the material of the comment moved to E16.1.32 on page 794. (Michael Pelsmajer)

## Supplementary Problems

Additional exercises will be listed here as collected. Suggestions welcome.

### Chapter 1 - Combinatorial Arguments

• For $n,a,b\in\NN$ with $n\ge2$, give a combinatorial argument to prove $\CH{n+a}n+\CH{n+b}n\le \CH{n+a+b}n$. Why does the argument fail when $n=1$?

### Chapter 5 - Graphs

• Let $T$ be an $n$-vertex tree whose subtrees with $n-2$ vertices are pairwise isomorphic, where $n\ge6$. Prove that $T$ is a star or a path.

### Chapter 6 - Matchings

• Let $G$ be an $X,Y$-bigraph having a matching that covers $X$. Prove that if $d(y)\ge k$ for all $y\in Y$, then $G$ has at least $k!$ matchings covering $X$. For each $k$, construct an infinite family of examples where there are only $k!$ such matchings. (Kostochka)

### Chapter 8 - Colorings

• The pancake graph $PG_n$ is the graph whose vertices are the permutations of $[n]$, with two permutations adjacent if one is obtained from the other by reversing a prefix. For example, $21435$ and $41235$ are adjacent; the graph is $(n-1)$-regular. Prove that the chromatic number of the pancake graph is subadditive; that is, $\chi(PG_{a+b})\le \chi(PG_a)+\chi(PG_b)$. Conclude that $\chi(PG_n)\le \CL{(2/3)n}$ for $n\in\NN$. (Leen Droogendijk) (Comment: A.H. Ghodraty found explicit proper $4$-colorings for $PG_8$ and $PG_9$, by computer. This makes it possible to prove $\chi(PG_n)\le 4\FL{n/9}+4$. Computing the diameter of the pancake graph is a famous open problem.)

### Chapter 12 - Posets

• Let $A$ and $B$ be families of subsets of $[n]$ such that $|x\cap y|\le k$ for all $x\in A$ and $y\in B$. Prove $|A|\cdot |B|\le 2^n \sum_{0\le i\le k}\CH ni$. (Hint: Use Kleitman's Inequality.) (P. Frankl)