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:

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?

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 K_k,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 J_n, 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).