185 citations · 371 across the 28 of their papers we have counts for
7 papers · 1 filter
Irredundant intervals
Donald E. Knuth
This expository note presents simplifications of a theorem due to Győri and an algorithm due to Franzblau and Kleitman: Given a family of intervals on a linearly ordered se…
Overlapping Pfaffians
Donald E. Knuth
A combinatorial construction proves an identity for the product of the Pfaffian of a skew-symmetric matrix by the Pfaffian of one of its submatrices. Several applications of this i…
Partitioned tensor products and their spectra
Donald E. Knuth
A pleasant family of graphs defined by Godsil and McKay is shown to have easily computed eigenvalues in many cases.
Aztec diamonds, checkerboard graphs, and spanning trees
Donald E. Knuth
This note derives the characteristic polynomial of a graph that represents nonjump moves in a generalized game of checkers. The number of spanning trees is also determined.
Leaper graphs
Donald E. Knuth
An -leaper is a generalized knight that can jump from to or on a rectangular grid. The graph of an -leaper on an $m\ti…
The sandwich theorem
Donald E. Knuth
This report contains expository notes about a function that is popularly known as the Lovász number of a graph~. There are many ways to define , and…
Stable husbands
Donald E. Knuth, Rajeev Motwani, Boris Pittel
Suppose boys and girls rank each other at random. We show that any particular girl has at least and at most different husbands in the se…