The first sentence on page 33 of Donald Knuth's The Art of Computer Programming (TAOCP) Vol. 4a reads:

Furthermore, a hypergraph is equivalent to a bipartite graph with vertex set $V \cup E$ and with the edge $v - e$ whenever $v$ is incident with $e$.

This is true when $V$ and $E$ are disjoint - which holds for non-pathological examples. But, using the von Neumann definition of an ordinal (where $0 = \emptyset$ and $n = \{0,...,n-1\}$ for all positive integers $n$), a counterexample to this sentence can be constructed.

Let $0 = \emptyset$ and $1 = \{0\}$ and $2 = \{0, 1\}$. Let $V = \{0, 1, 2\}$ and $E = \big\{ \{0\}, \{0,1\} \big\}$. Then we have the unusual situation that $E \subseteq V$. So $V \cup E = V$. The graph resulting from this hypergraph is the complete graph on $V = V \cup E = \{0, 1, 2\}$, which is not bipartite.

A while ago, I sent this to the e-mail address indicated for submitting errors in TAOCP. So far I haven't heard back, which can have several reasons:

  1. What I perceive as a counterexample above is not a counterexample because it contains an error (which one?).
  2. The counterexample is so weird it doesn't really count as a counterexample.
  3. The counterexample, or a similar one, has already been submitted by somebody else.
  4. The e-mail address is only checked rarely, if at all.

I am grateful for any input on this!

  • 1
    $\begingroup$ This is not a counterexample, but being deliberately obtuse. It's obvious the union is meant to be disjoint union. $\endgroup$ Feb 14 at 11:55
  • 3
    $\begingroup$ [and...] All texts necessarily assume some shared context between the reader and author. If a reader does not understand the assumed context, that does not mean that the text "isn't mathematically valid". That readers generally do understand such texts is perhaps evidence that most of us, even the ordinary ones, must indeed be spiritually gifted in some useful way that is interesting to ponder. $\endgroup$
    – Neal Young
    Feb 14 at 14:35
  • 2
    $\begingroup$ Since the text would become perfectly correct if a dot were placed over the $\cup$ sign, which is clearly the intended reading, this is, at worst, a trivial typo. Not an error that would warrant an email exchange. $\endgroup$ Feb 14 at 14:50
  • 1
    $\begingroup$ @DominicvanderZypen Maybe calling it an error might be off-putting to some. If you think the text specifying that the union is a disjoint one will be helpful to readers, then maybe just say that. $\endgroup$ Feb 15 at 11:38
  • 1
    $\begingroup$ Another point: Notice that Knuth welcomes feedback also to small errors, like typos etc. and eagerly corrects these if he agrees that it is an error. However, he processes emails in bulk, so it may well be that you will have to wait for some weeks, or even months until you get an answer. Delay does not imply anything about your request, but is simply caused by his way of working on TAOCP. $\endgroup$ Feb 20 at 17:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.