# 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}} \def\SE#1#2#3{\sum_{#1=#2}^{#3}} \def\PE#1#2#3{\prod_{#1=#2}^{#3}}$

Observations attributed to Leen Droogendijk are designated by "(LD)".

## Mathematical and Notational Errors

• p130 L3.3.33: At the end of the case $k\ne -1$, the sentence beginning "Since $g$ is a formal power series" is valid only for $k\ge0$. The sentence should be "Since $g$ is a formal power series, $g^{k+1}$ is a formal Laurent series, and by the definition the derivative of any formal Laurent series has residue $0$. Hence the coefficient of $x^{-1}$ is $0$, as desired." (Fanxin Wu)
• p133 X3.3.21: In part (b), the factor "$i^{\FL{m/i}}$" should be "$i^{\FL{m/(i-1)}}$".
• p248 X5.4.18: "$n(k-2)$" should be "$n(k-1)$". (Allan Bickle)
• 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)
• p262 X6.1.29: "$y\delta(G)$" should be "$2\delta(G)$" (Jozsi Balogh)
• 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$. (LD)
• 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. (LD)
• p459 X10.2.20: The given lower bound ignores a lower-order term in the exponent. (LD)
• 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).
• p474 X10.3.15c: The final theorem in the paper of Gyárfás and Simonyi states "Any Gallai coloring of $K_n$ has a color with largest degree at least $2n/5$". This is true, but it is weaker than the statement of the Ramsey number. When $m$ is even, setting $n$ to be the smallest value that forces a rainbow triangle or monochromatic $K_{1,m}$ in their formula only guarantees a color with degree at least $m-1$. The correct answer for $m\ge3$ is $(5m-3)/2$ when $m$ is odd, $5m/2-3$ when $m$ is even. The case $m=4$ seems to require an ad hoc argument. (LD)
• p482 proof at page top: In the fourth paragraph, "The reduced graph $R$ with vertex set $\VEC v1n$" should be "The reduced graph $R$ with vertex set $\VEC v1k$. (LD)
• p491 X11.1.29: The $t$ to be used in the special case for $r=2$ is the smallest $t$ such that the inequality of part (c) is satisfied. (LD)
• p492 X11.1.34: The needed condition $n\ge|V(F)|$ was omitted from the problem statement. When $n \lt |V(F)|$, the only $F$-saturated $n$-vertex graph is $K_n$, which may have more edges than the claimed bound. (LD)
• p492 X11.1.42: Part (b) should request showing that there are asymptotically at least $\FR14(1-2\epsilon)(d-\epsilon)^4n^4$ such $4$-cycles. (LD)
• p495 L11.2.10 - T11.2.11: In the lemma, it is better to allow $i\ne j$, and in the proof of the theorem, the definition of dominant element should restrict to sets $x$ not containing $i$. (LD)
• p497 T11.2.14: In the last paragraph, "all sets above $|\partial A|$" should be "all sets above $\partial A$". (Stephen Hartke)
• p495 T11.2.18: "immediately following some $a_1$" should be "immediately following some $a_i$". (LD)
• p505 L11.2.34: "Since lg is strictly convex" should be "Since $-$lg is strictly convex". (LD)
• p506 D11.2.36: "When $Y$ is a random variable and $E$ is the event $Y = y$, taking the weighted average of these distributions over the distribution of $Y$" should be "When Y is a random variable, taking the expectation of these entropy values over the events of the form $Y=y$". (LD)
• p509 L11.2.44 proof: The equality in the middle of the displayed formula should be "$\le$". (LD)
• p512 X11.2.32: "size at most 2" should be "size 1 or 2". If the conjecture holds for families containing the empty set, then it holds in general. (LD)
• p513 X11.2.40: In the Comment, "$\PE j1n$" should be "$\PE j1d$". (LD)
• p539 X11.3.44b: The matroid must be loopless. (LD)
• p540 X11.3.59c: "Without using other results, use part (a) directly" should just be "Use part (a)". Part (a) can be proved simply, without using the Matroid Intersection Theorem, but then the Matroid Intersection Theorem is needed to restate (a) in a way that leads to (c).
• p548 T12.1.21: "$k\gt\alpha(G)$" should be "$k\gt\alpha(D)$". (LD)
• p566 X12.2.16: The notation "${\bf 2}^{[n]}$" is left over from more advanced material and is not used in this book. All instances of "${\bf 2}^{[k]}$" or "${\bf 2}^{[n]}$" should be "${\bf 2}^{k}$" or "${\bf 2}^{n}$", respectively. See also p570 E12.3.6, p571 before C12.3.8, and p590 E12.4.17. (LD)
• p577 T12.3.29: For consistency, "$A_x$" should be "$A$". (LD)
• p585 before D12.4.2: "$[a_x,b_x]$" should be "$[a_z,b_z]$". (LD)
• p589 E12.4.12: "when viewed in all of ${\bf 2}^P$" should be "in the subset lattice"
• p589 E12.4.13: "Example 12.4.13" should be "Example 12.2.13". (LD)
• p595 before T12.4.34: "${\bf P}(AB)$" should be "${\bf P}(A\cap B)$" (LD)
• p595 T12.4.34: The denominators should be $2^n$, and the inequality should be "$\ge$". (LD)
• p601 D12.4.43: "$\VEC H1k$" and "$H_i$" should be "$\VEC G1k$" and "$G_i$". (LD)
• p605 X12.4.16: In part (c), "$M_{n+1}$" should be "$M_n$".
• p606 X12.4.20: It should be indicated that the parts of partitions are listed in nonincreasing order, and again in X12.4.21 zeros are appended. (LD)
• p607 X12.4.34: "on a distributive lattice" should be "on a finite distributive lattice". (LD)
• p631 after D13.2.17: "$z(m,n;3,2)$" should be "$z(m,n;2,3)$", since no two circles have three common points. (Michael Pelsmajer)
• p631 T13.2.19 proof: $\CH yt$ is a convex function of $y$ only for $y > t-1$, but that is where we need it. When the number of edges is maximized, every vertex in $x$ has degree at least $t-1$. (Michael Pelsmajer)
• p697 T14.3.29: At the end of the proof, "${\rm e}^{-(d-1)^2}/4$" should be "${\rm e}^{-(d-1)^2/4}$"
• p766 X15.2.34c: "$\varnothing$" should be "$\{0\}$". (Stephen Hartke)
• p790 T16.1.20: It is not true that assigning each vertex the triple of its heights in a 3-dimensional realizer produces a barycentric representation, even after projecting to the plane $x+y+z=1$ and normalizing to make all coordinates nonnegative. There seems to be no easy way to obtain a barycentric representation directly. However, projecting the embedding given by the realizer for both the vertices and the edges into that plane (or $x+y+z=0$) does give a straight-line embedding of the subdivision graph. See page 129 of Trotter's 1992 book Combinatorics and Partially Ordered Sets: Dimension Theory. (Michael Pelsmajer, Stefan Felsner)
• 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$. (LD)
• p843 X10.2.32: "$(x)+d(y)$" should be "$d(x)+d(y)$". (LD)
• p844 X11.1.8: The coordinates are indexed by $[n]$, not by vertex names. Hence the phrasing should be "if $v_iv_j\notin E(G)$ and $x_i,x_j\ne 0$, then $f(x')\ge f(x)$ for some $x'$ such that $x'_ix'_j=0$." (LD)
• p844 X11.1.39: The suggestion to show $\alpha'(G)\gt n-\delta(G)$ is irrelevant, and the augmenting path will have length at most $5$. (LD)

## 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)
• p349 R8.2.15: "Dirac [1952b]" should be "Dirac [1952a]", as in T8.2.17. (Allan Bickle)
• p565 X12.2.8: The citation to West [1980] is incorrect! That paper gives a symmetric chain decomposition for $L(4,n)$. The result for $L(3,n)$ is due to Lindstrom [1980] (European J. Combinatorics 1, 61-63).

• p26 T1.2.3(5): When explaining the Summation Identity using lattice paths, the term $\CH kr$ counts the paths to $(r+1,n-4)$ in which the height of the last horizontal step is $k-r$. (Silpian D.)
• p65 X2.1.61: Further and more general references include M. Desjarlais and R. Molina, Counting spanning trees in grid graphs, Congressus Numerantium, 145 (2000) 177-185; F. J. Faase, On the number of specific spanning subgraphs of the graphs $G\times P_{n}$, Ars Combinatoria, 49 (1998) 129-154; and P. Raff, Spanning Trees in Grid Graphs, (2008), https://arxiv.org/abs/0809.2551. See sequence A001353 of OEIS. (Allan Bickle)
• 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 are fairly long for ($\D$) exercises.
• 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.
• p317 E7.3.3 and p330 X7.3.23: Tutte actually wrote "it is tempting to conjecture", which is perhaps not quite conjecturing. A paper by Brinkmann, Goedgebeur, and McKay (see https://arxiv.org/pdf/2101.00943.pdf)
(1) points out that the graph found by Georges is the first of an infinite family found also by A.K. Kelmans in Cubic bipartite cyclic 4-connected graphs without hamiltonian circuits, Russian Mathematical Surveys, 43 (1988), 205, and
(2) shows that 50 is the smallest order of a counterexample to Tutte's "conjecture". (Allan Bickle)
• p330 X7.3.16: The analysis of $m$-by-$n$ boards in general is by A. Schwenk in Which rectangular chessboards have a knight's tour?, Math. Mag. (1991), 325-332. (Allan Bickle)
• p335: A more recent book with substantial material on graph coloring is G. Chartrand and P. Zhang, Chromatic Graph Theory, CRC Press, 2009. (Allan Bickle)
• p338 P8.1.12: The term "colouring number'' was used in this way by P. Erdős and A. Hajnal as early as On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61-99, where they comment that P8.1.12 is "well known". (Allan Bickle)
• p344 X8.1.40: Finck [1968] also characterized the extremal graphs. (Allan Bickle)
• p357ff Section 8.3: A brief presentation of the history of edge-coloring appears in B. Toft and R. Wilson, Discrete Mathematics Letters 6 (2021), 38-46.
• p353 X8.2.7 and p375 X8.3.42: Dirac [1960] showed that $n$-vertex graphs with more than $2n-3$ edges contain a $K_4$-subdivision. In Dirac [1964], he showed that the $n$-vertex graphs with $2n-3$ edges having no $K_4$-subdivision are the $2$-trees. (Allan Bickle)
• p418 X9.3.15: The fact that the Lederberg-Bosák-Barnette graph is the smallest example was proved by D.A. Holton and B.D. McKay in The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices, J. Combinatorial Theory (B) 45 (1988), 305-319.
• 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$.
• p490 X11.1.21: In fact, there are exactly two extremal graphs.
• p490 X11.1.22: Add "(Hint: Use induction on $n$ and prove the statement more generally for multigraphs.)"
• p511 X11.2.13: Maybe this should be a (+) problem, since the construction is not given.
• p539 X11.3.51: A better exercise would be to prove the following:
(a) The intersection of two closed sets is closed.
(b) If $X$ and $Y$ are closed sets with $Y\esub X$ and $r(Y)=r(X)-1$, then $M$ has a hyperplane $H$ such that $Y=X\cap H$.
(c) The closed sets are the intersections of hyperplanes, with a closed set of rank $r(M)-k$ being the intersection of $k$ hyperplanes.
(d) The union of two closed sets need not be a closed set.
• p566 X12.2.18: This exercise is here because it shows that the chains in E12.2.12 are the same whether generated from the top down or the bottom up.
• p567 X12.2.24: For consistency with Chapter 6, the term defect should have been used here instead of deficiency, and strong Hall property should have been strong Hall condition for $Y$. (LD) Note also that the matching joining the copies of $Y$ can be any matching. Part (a) should have given the hint to use the König-Egerváry Theorem. This exercise is in fact a stronger result than the Anderson-Griggs result at T12.2.26, using a supplementary exercise given below.
• p567 X12.2.25: It is clearer to change the word "consecutive" to "adjacent". Also, the reference to E12.2.34 should probably be to P3.1.15. (LD)
• p583 X12.3.16: "putting $Y$ over $X$" should be "putting $Y$ over $X$ (see Definition 12.3.17)".
• p607 X12.4.39: The definitions of semimodular and modular lattices used in this exercise are different from those given in R12.4.33. They are in fact equivalent. Nevertheless, the exercise just asks for a relationship for lattices under the definition given in the exercise. (LD)
• p622 X13.1.2: This is harder than a typical "(-)" exercise.
• 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)
• p792 T16.1.26: An engaging article about the early history of the crossing number problems for complete graphs and complete bipartite graphs is L.W. Beineke and R. Wilson, "The early history of the brick factory problem," The Mathematical Intelligencer 32 (2010), 41-48. The conjectured optimal drawing seems to be due to the British artist Anthony Hill in the late 1950s.
• 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".
• p312 X7.2.8: "proved" should be "prove". (Allan Bickle)
• p459 X10.2.14,20: Elsewhere in the book, a roman "e" is used for the base of the natural logarithm.
• p490 X11.1.25: This exercise should have been placed immediately after X11.1.27.
• p495 T11.2.11: Although the first "$\ge$" in the display at the bottom of the page is not wrong, the argument given earlier is that in fact equality holds. (LD)
• p536 X11.3.3: "$G$ graphs" should be "graphs $G$". (LD)
• p537 X11.3.28: "tranversal" should be "transversal". (LD)
• 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)
• p566 X12.2.21: "yields chain partition" should be "yields a chain partition" (LD)
• p568 X12.2.33: The close parenthesis is missing at the end of the hint. (LD)
• p583 X12.3.15: "non-cut vertices" should be "non-cut-vertices". (Stephen Hartke)
• p608 X12.4.47: "postively" should be "positively". (LD)
• p608 X12.4.48: "$Q$" should be declared to be a poset. (LD)
• 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)
• p925: "W.H. Wiedemann" should be "D.H. Wiedemann"

## 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 2 - Recurrence Relations

• Prove $\SE l0n (-1)^l\CH nl\CH {2l}m=(-1)^n2^{2n-m}\CH n{m-n}$ by showing that both sides satisfy the same recurrence.

### 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 7 - Connectivity and Cycles

• For vertices $x,y,z$ in a graph $G$, is it true that $\lambda'(x,y)\ge k$ and $\lambda'(y,z)\ge k$ together imply $\lambda'(x,z)\ge k$? Is it true that $\lambda(x,y)\ge k$ and $\lambda(y,z)\ge k$ imply $\lambda(x,z)\ge k$?

### 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$. (LD) (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.)
• A 2-tree is a chordal graph obtained from $K_2$ by iteratively adding a simplicial vertex with two neighbors. For $n\ge3$, prove that the maximum number of edges in an $n$-vertex graph containing no $K_4$-subdivision is $2n-3$, and show that every such graph is a $2$-tree. (Dirac [1960, 1964]) (Comment: This result is also a corollary of the fact that a maximal $k$-degenerate graph is a $k$-tree if and only it it contains no subdivision of $K_{k+2}$, proved in A. Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 (2012), 659-676. The extremal graphs avoiding a $K_5$-subdivision have $3n-6$ edges (Mader 1998) and were characterized as the 3-sums'' of planar graphs in W. Mader, Graphs with $3n-6$ edges not containing a subdivision of $K_{5}$, Combinatorica 25 (2005), 425-438.)

### Chapter 10 - Ramsey Theory

• Let $H_{r,s}$ be the graph $K_{1,r}+K_{1,s}$. Prove $R(H_{r,s},H_{r,s})=\max\{2r+1,r+2s,r+s+3\}$ (Rosta) (Comment: The lower bound is in X10.2.36; just prove the upper bound here. (Hint: Consider the degree-sum of a graph not containing $H_{r,s}$.)

### Chapter 12 - Posets

• Given an $X,Y$-bigraph $G$, prove that the Strong Hall Condition for $Y$ (Exercise 12.2.24) is implied by the normalized matching condition for the $2$-level poset whose cover graph is $G$ and implies Hall's Condition for a matching in $G$ covering $X$.
Comment: By this exercise, the condition in X12.2.24 applies more generally than the condition in T12.2.26, so X12.2.24 provides a stronger result than T12.2.26.
• 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)

### Chapter 13 - Designs

• Let $\VEC A1m$ be $k$-sets such that $\C{A_i\cap A_j}\le \lambda$ for all distinct $i$ and $j$ in $[m]$. Prove $\C{\bigcup A_i}\ge\FR{k^2m}{\lambda m+k-\lambda}$. Express this as a bound on the size of a family of $k$-subsets of $[n]$ that pairwise share at most $\lambda$ elements. (Johnson [1962])