This thesis investigates three fundamentally related combinatorial
objects: regular bipartite graphs, Latin rectangles and
(0,1)-matrices with all line sums equal. The links between these
objects are exploited to give some strong
results on problems which had seemed intractable when considered
in isolation. A central question, phrased in three ways,
is the following:
Items (1) to (3) will be referred to below as the maximising problem.
The most general previous result was due to Brègman,
who solved the case when k divides n. We essentially settle the
complementary case (that is, when n-k divides n) which relates to
a conjecture of Godsil and McKay. We also make
substantial progress on the general case, which is an open question
listed in Minc's survey article on permanents.
In fact that catalogue contains two problems (numbers 4 and 12) which we
partly solve and five conjectures (numbers 12, 21, 22, 25 and 26) which we
disprove. (Conjectures 25 and 26 were previously known to fail, but
were easily patched to exclude the known counterexamples. We identify
more serious flaws.)
The method of attack on the maximising problem is via a certain integral
involving rook polynomials. These polynomials are studied in some
depth, including their connections with Laguerre polynomials. An
important step is to relate properties of the roots of the rook
polynomials to the number of short cycles in an associated bipartite
graph. On this issue, we ask the following question. If G is a
k-regular bipartite graph on 2n vertices (n>2k) such that G
maximises the number of 4-cycles among all such graphs, does G
always contain a copy of Kk,k? It is shown how an affirmative
answer would completely characterize G. The maximising problem for
n-k << n could then be resolved using a result from Godsil and McKay.
Chapter 3 was the subject of the B.H.Neumann award winning talk at the
1996 meeting of the Australian Mathematical Society. In that talk the
long standing Holens-Dokovic conjecture on the ratio of
subpermanent sums was shown to fail, by converting it to a problem on
the ratio of perfect matchings to near perfect matchings in a
graph. As a result the problem known as `monotonicity of the
permanent' is answered in the negative. This question asked whether
for every doubly stochastic matrix A of order n, the permanent is
a monotone function on the interval joining A to Jn, the matrix
in which every entry is 1/n. Despite the disproof of the general
case of the Holens-Dokovic conjecture, several specialised
cases are proved.
In the final chapter, the asymptotic distribution of subsquares in
Latin rectangles is considered. We find that almost all Latin squares
contain a large number of intercalates (order 2 subsquares). We also
show that N∞ squares (Latin squares without proper
subsquares) are very rare and then briefly explore a method of
creating such squares. The smallest order for which existence of an
N∞ square is unknown is raised from 24 to
256. This last result has been improved in recent work by the author
(as yet unpublished).
- Which k-regular bipartite graphs on 2n vertices contain
the most perfect matchings?
- Which (n-k)× n Latin rectangles have the most extensions to
(n-k+1) × n Latin rectangles?
- Which square (0,1)-matrices of order n, with precisely k ones
in each row and column, achieve the maximum permanent?