%% Paper entitled "Maximising the permanent of (0,1)-matrices and %% the number of extensions of Latin Rectangles" %% %% By Brendan McKay and Ian Wanless %% bdm@cs.anu.edu.au imw@cs.anu.edu.au %% %% (Plain TeX file) %% %% Accepted by Electronic J. Combinatorics, March 1997. %% %% Final version transmitted 6/2/98 \magnification 1200 \hsize=6.5 true in % At 6.0 inches, the main table spills over. \vsize=9.0 true in \baselineskip=14pt \voffset=2\baselineskip % To compensate for headline \font\sm =cmr8 \font\smcp=cmcsc8 \headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 5 (1998), \#R11\hfill\folio} \else\hfill \fi} \nopagenumbers %% This is how we used to do the referencing... %\openin0=maxext.ref % Forgive this horrid hack %\ifeof0 %\message{Please run TeX again on this file to ensure correct references} %\batchmode %\else \input maxext.ref %\fi %% ...but now these crossreferences have been hardwired. \def \thbreg {1} \def \tmroots {2} \def \tmint {3} \def \thcyc {4} \def \thcycmin {5} \def \thmom {6} \def \thdiff {7} \def \thupwig {8} \def \thsecmom {9} \def \MAIN {10} \def \BAS {1} \def \BBol {2} \def \BBg {3} \def \BBGM {4} \def \BChet {5} \def \BGee {6} \def \BGM {7} \def \BHL {8} \def \BJR {9} \def \BMerry {10} \def \BMC {11} \def \BMCT {12} \def \BS {13} \def \BW {14} \def \BWW {15} \def \BZag {16} %%---------------------------------- %%\newwrite\reffile \def\save#1{} %% Has been disabled %%\def\save#1{\write\reffile{\noexpand\def\noexpand#1{#1}}} %%\openout\reffile=maxext.ref \font\bigger=cmr10 scaled\magstep2 \newcount\secno \def\section#1\par{\global\advance\secno by1 \bigbreak\bigskip\noindent{\bf\S\number\secno. #1}\par\medskip} \secno=0 \newcount\thrmno \def\thrm#1.#2\par{\global\advance\thrmno by1 \thrmmark#1 \medbreak\medskip\noindent {\bf Theorem \number\thrmno.}{\sl #2}\par\medskip} \thrmno=0 \def\thrmmark#1{\xdef#1{\the\thrmno} \save{#1}} \def\thcall#1{Theorem~\number#1} \def\numon#1{\number#1} \newcount\corolno \def\corol#1.#2\par{\global\advance\corolno by1 \corolmark#1 \medbreak\medskip\noindent {\bf Corollary \number\corolno.}{\sl #2}\par\medskip} \corolno=0 \def\corolmark#1{\xdef#1{\the\corolno}} \def\crcall#1{Corollary~\number#1} \newcount\conjno \def\conj#1.#2\par{\global\advance\conjno by1 \conjmark#1 \medbreak\medskip\noindent {\bf Conjecture \number\conjno.}{\sl #2}\par\medskip} \conjno=0 \def\conjmark#1{\xdef#1{\the\conjno}} \def\conjcall#1{Conjecture~\number#1} \newcount\lemno \def\lem#1.#2\par{\global\advance\lemno by1 \lemmark#1 \medbreak\medskip\noindent {\bf Lemma \number\lemno.}{\sl #2}\par\medskip} \lemno=0 \def\lemmark#1{\xdef#1{\the\lemno}} \def\lemc#1{Lemma~\number#1} \newcount\eqnno \eqnno=0 \def\eqmark#1{\global\advance\eqnno by 1 \xdef#1{\the\eqnno}} \def\eqcall#1{(\number#1)} \def\ref#1{\eqmark#1 \eqno(\number\eqnno)} \def\prf{\noindent {\bf Proof:} } \def\bull{\vrule height 1.2ex width 1.1ex depth 0ex} \def\endpf{\hfill$\odot$\rightskip=0pt\medbreak} \def\bgmn{Br\`egman} \def\lr{Latin rectangle} \def\per{{\rm per}} \def\mod{{\rm mod\ }} \def\frac#1#2{{\textstyle{#1\over#2}}} \def\dx{\,dx} \def\rk{\rho} \def\iso{\cong} \def\lnk{\Lambda_n^k} \def\lag{{\cal L}} \def\BGMset{{\cal U}_{n,t}} \def\comp{\overline} \def\jn{\oplus} \newcount\biblno \biblno=0 \def\bibl#1{\global\advance\biblno by1 \xdef#1{\the\biblno} \save{#1}} \def\bibcl#1{[\number#1]} \def\bibit#1{\bibl{#1}\item{\bibcl{#1}}} \def\dj{\hbox{\raise.2ex\hbox{--}\kern-1ex D}okovi\'c} \def\hdc{Holens-\dj\ Conjecture} \centerline{\bigger Maximising the permanent of (0,1)-matrices and} \smallskip \centerline{\bigger the number of extensions of \lr s} \bigskip \centerline{ \vbox{\halign{#&#\hfill&#\cr &B.~D.~McKay and I.~M.~Wanless&\cr &Department of Computer Science&\cr &Australian National University&\cr &Canberra ACT 0200 Australia&\cr &bdm@cs.anu.edu.au / imw@cs.anu.edu.au&\cr}} } \medskip \centerline{\sm Submitted: February 18, 1997; Accepted: March 15, 1997; Received in final form: February 8, 1998.} \centerline{\sm AMS Classifications 15A15, 05C70, 05B15.} \medskip \line{\hrulefill} Let $k\geq2$, $m\geq5$ and $n=mk$ be integers. By finding bounds for certain rook polynomials, we identify the $k\times n$ Latin rectangles with the most extensions to $(k+1)\times n$ Latin rectangles. Equivalently, we find the $(n-k)$-regular subgraphs of $K_{n,n}$ which have the greatest number of perfect matchings, and the $(0,1)$-matrices with exactly $k$ zeroes in every row and column which maximise the permanent. Without the restriction on $n$ being a multiple of $k$ we solve the above problem (and the corresponding minimisation problem) for $k=2$. We also provide some computational results for small values of $n$ and $k$. Our results partially settle two open problems of Minc and conjectures by Merriell, and Godsil and McKay. \line{\hrulefill} \section The problem Let $k$ and $n$ be positive integers with $k\leq n$. A $k\times n$ {\it\lr\/} is a $k\times n$ matrix of entries from $\{1,2,\dots,n\}$ such that no entry is duplicated within any row or any column. We use $L(k,n)$ for the set of $k\times n$ \lr s. For $R\in L(k,n)$ define $E(R)$ to be the number of $R'\in L(k+1,n)$ such that the first $k$ rows of $R'$ are identical to the corresponding rows of $R$. We say that $E(R)$ is the number of {\it extensions\/} of $R$. We call $R_1\in L(k,n)$ a {\it maximising rectangle\/} if $E(R_1)\geq E(R)$ for every $R\in L(k,n)$. We define $M_{k,n}=E(R_1)$ for a maximising $R_1$. Similarly we call $R_2\in L(k,n)$ a {\it minimising rectangle\/} if $E(R_2)\leq E(R)$ for every $R\in L(k,n)$ and define $m_{k,n}=E(R_2)$ for a minimising $R_2$. We are interested in identifying maximising and minimising rectangles and in finding estimates for $M_{k,n}$ and $m_{k,n}$. In particular, we concentrate on maximising rectangles in the case when $n=mk$ for some integer $m$. The problem has (at least) two other guises which are fruitful to consider. With each $R\in L(k,n)$ we associate $G(R)$, a subgraph of the complete bipartite graph $K_{n,n}$, defined as follows. Let $\{u_1,u_2,\dots,u_n\}$ and $\{v_1,v_2,\dots,v_n\}$ be the two vertex sets. We put an edge $(u_i,v_j)$ in $G(R)$ precisely when symbol $i$ occurs in column $j$ of $R$. For any spanning subgraph $G$ of $K_{n,n}$ we use $\comp{G}$ to denote the complement within $K_{n,n}$ of $G$. Note that $G(R)$ is $k$-regular, $\comp{G(R)}$ is $(n-k)$-regular and $E(R)$ is the number of perfect matchings in $\comp{G(R)}$. Finding a maximising $k\times n$ \lr\ is equivalent to maximising the number of perfect matchings in an $(n-k)$-regular subgraph of $K_{n,n}$. The other incarnation of the problem is in $(0,1)$-matrices. Let $\lnk$ denote the set of $(0,1)$-matrices of order $n$ in which the row and column sums are all equal to $k$. With $R$ and $G(R)$ we associate $A(R)\in\lnk$ defined by $$\big(A(R)\big)_{ij}=\cases{1,&if $u_i$ is adjacent to $v_j$ in $G(R)$;\cr 0,&otherwise.\cr}$$ We call $A(R)$ the biadjacency matrix of $G(R)$. Note that $E(R)$ is the permanent of $\comp{A(R)}$, the biadjacency matrix of $\comp{G(R)}$. Hence the question of finding a maximising $k\times n$ \lr\ relates to maximising the permanent of $(0,1)$-matrices of order $n$ with all line sums equal to $n-k$. The association between $R$, $G(R)$ and $A(R)$ is so strong that we will tend to blur any distinction and think of them as a single object. It should be apparent that we are only interested in the structure of $G(R)$ up to isomorphism, or $A(R)$ up to permutations of the rows and columns. The principal result of the paper (\thcall\MAIN) is that if $m\geq5$ then every maximising $R\in L(k,mk)$ has ${G(R)}$ isomorphic to $m$ copies of $K_{k,k}$. This partially answers problems 4 and 12 of Minc \bibcl\BMCT. \section What is known The literature on bounds for permanents is quite extensive. Minc \bibcl\BMC, \bibcl\BMCT\ and Schrijver \bibcl\BS\ are recommended starting points. Of particular interest to us are the Egorychev-Falikman Theorem (formerly the van der Waerden conjecture) which yields $$m_{k,n}\geq n!(1-k/n)^n,\ref\vdW$$ and the \bgmn\ bound, $$M_{k,n}\leq \big((n-k)!\big)^{n/(n-k)}.\ref\BregB$$ \bgmn\ proved \eqcall\BregB\ in \bibcl\BBg, which also contains the following theorem. \thrm\thbreg. Let $k,m\geq2$ be integers and $R\in L\big((m-1)k,mk\big)$ be maximising. Then $\comp{G(R)}$ consists of $m$ copies of $K_{k,k}$. We note the following corollary. \corol\corbreg. $R\in L(k,2k)$ is maximising if and only if $G(R)$ is disconnected. There has been substantial effort towards enumerating Latin squares ($n\times n$ \lr s), often by counting the extensions of \lr s. The best asymptotic estimates to date are contained in \bibcl\BGM, which employs similar tools to the present paper. Let $R\in L(k,n)$. An $i$-matching in $G(R)$ is a set of $i$ vertex-disjoint edges in $G(R)$. Let $m_i(R)$ denote the number of $i$-matchings in $G(R)$ and adopt the convention that $m_0(R)=1$. We define the rook polynomial $\rk(R,x)$ by $$\rk(R,x)=\rk\big(G(R),x\big)=\sum_{i=0}^n(-1)^i m_i(R)x^{n-i}.$$ The two features of rook polynomials which we exploit most are demonstrated in the following two results. The first is a consequence of the work of Heilmann and Lieb \bibcl\BHL, while the second is due to Joni and Rota \bibcl\BJR. \thrm\tmroots. For any $R\in L(k,n)$ where $k\geq2$, the roots of $\rk\big(G(R),x\big)$ are real and lie in the open interval $(0,4k-4)$. For $R\in L(1,n)$, $\rk\big(G(R),x\big)=(x-1)^n$. \thrm\tmint. The number of extensions of $R\in L(k,n)$ is given by $E(R)=I_0^{\infty}\big(\rk(R,x)\big)$, where the linear operator $I_a^b(\cdot)$ is defined by $$I_a^b\big(f(x)\big)=\int_a^b e^{-x}f(x)\dx.$$ The integral defined in \thcall\tmint\ is the fundamental tool in this paper, as it was in \bibcl\BGM. We use $I(\cdot)$ as shorthand for $I_0^{\infty}(\cdot)$. Two other well known properties of the rook polynomial are worth noting. Firstly, it is multiplicative on components. That is, if $\{C_i\}_i$ is the set of components of a graph $G$ then $\rk(G,x)=\prod_i\rk(C_i,x)$. Secondly, for an arbitrary integer $a$, $$\rk(K_{a,a})=\lag_a(x)=(-1)^aa!\sum_{i=0}^a{a\choose i}{(-x)^i\over i!}.\ref\comrk$$ That is, the rook polynomial of a complete bipartite graph is a Laguerre polynomial, normalised to be monic. \section The $k=2$ case Every $R\in L(1,n)$ satisfies $E(R)=n!\sum_{i=0}^n(-1)^i/i!$, that being the number of derangements of $\{1,2,\dots,n\}$. Hence, the smallest case for which the question of identifying maximising rectangles is interesting is the case $k=2$. Let $\BGMset$ denote the set of $(0,1)$-matrices of order $n$ containing exactly $t$ zeroes (without restriction on row or column sums). In \bibcl\BBGM\ the matrices maximising the permanent in $\BGMset$ are identified for $t\leq 2n$. When $t=2n$ the answer turns out to be an element of $\Lambda_n^{n-2}$, except in the case $n=5$. The maximising rectangles in $L(2,n)$ are thereby found for all $n\neq5$. In \thcall\thcyc\ (below) we present a new way of obtaining this result. Every component of $G(R)$ for $R\in L(2,n)$ is a cycle of even length. We use $C_a$ to denote a cycle of length $a$, and define $p_i=p_i(x)=\rk(C_{2i},x)$ for each $i\geq2$. By extension we define $p_0=2$ and $p_1=x-2$ so that $p_i(4x^2)=2T_{2i}(x)$ for each $i\geq0$, where $T_n(x)$ is the $n^{\rm th}$ Chebyshev polynomial of the first kind. This leads \bibcl\BW\ to $$p_ap_b=p_{a+b}+p_{a-b}\hbox{ for }0\leq b\leq a.\ref\dokov$$ Formula \eqcall\dokov\ is the key to the next two theorems, because it shows us when it is profitable to split long cycles. \thrm\thcyc. When $2\leq n\leq4$ or $n\geq8$ the maximising $R\in L(2,n)$ are those which maximise the number of components in $G(R)$. For $5\leq n\leq7$ the maximising $2\times n$ rectangles are those $R$ for which $$G(R)\iso\cases{ C_{10}&for $n=5$,\cr C_6+C_6&for $n=6$,\cr C_{10}+C_4\hbox{ or }C_6+2C_4&for $n=7$.\cr}$$ Here $+$ denotes disjoint union and $rG$ is shorthand for $\underbrace{G+G+\dots+G}_{r\rm\;times}$. \prf The theorem is easily established for $n\leq7$ so we assume $n\geq8$. Let $R\in L(k,n)$ be maximising and suppose $G(R)$ consists of $c$ cycles $C_{2a_1}, C_{2a_2},\dots, C_{2a_c}$. Clearly $n=\sum a_i$ and $\rk\big(G(R),x\big)=\prod p_{a_i}$, and we may suppose for convenience that the $a_i$ are arranged in non-increasing order. We first show that $a_1\leq5$. Suppose this were not the case and consider the rectangle $R'$ formed from $R$ by `splitting' the $C_{2a_1}$ into $C_4+C_{2a_1-4}$. Then by \eqcall\dokov\ $$\rk\big(G(R'),x\big)=p_2p_{a_1-2}\prod_{i\geq2}p_{a_i} =\rk\big(G(R),x\big)+p_{a_1-4}\prod_{i\geq2}p_{a_i}.$$ Now $$E(R')=I\Big(\rk\big(G(R'),x\big)\Big) =E(R)+I\Big(p_{a_1-4}\prod_{i\geq2}p_{a_i}\Big).\ref\eqex$$ Our assumptions that $n>6$ and $a_1>5$ mean that $I\big(p_{a_1-4}\prod_{i\geq2}p_{a_i}\big)>0$ by \eqcall\vdW\ because it is the number of extensions of some rectangle in $L(2,n-4)$. Thus \eqcall\eqex\ breaches our choice of $R$, proving that $a_1\leq5$. We next examine the case when $a_1=5$. Let $R'$ be the rectangle obtained from $R$ by splitting $C_{2a_1}$ into $C_6+C_4$. Then $E(R')=E(R)+I\big(p_1\prod_{i\geq2}p_{a_i}\big)$. If $a_2\geq3$ then $$I\Big(p_1\prod_{i\geq2}p_{a_i}\Big)=I\Big(p_{a_2+1}\prod_{i\geq3}p_{a_i}\Big) +I\Big(p_{a_2-1}\prod_{i\geq3}p_{a_i}\Big)$$ which is positive because the first term on the right is positive and the second non-negative, again by considering the integrals as counts of extensions of certain \lr s. Thus we may assume that $a_i=2$ for $i\geq2$. Now $$I\big(p_1p_2^{c-1}\big)=I\big(p_3p_2^{c-2}\big)+I\big(p_1p_2^{c-2}\big)$$ which by induction yields that $I\big(p_1p_2^{c-1}\big)$ is zero when $c=2$ and positive for $c\geq3$. As $n\geq8$ it follows that there must be at least $c\geq3$ cycles, and hence $a_1=5$ is contradictory. Now we eliminate the possibility that $a_1=4$. Let $R'$ be the rectangle obtained from $R$ by splitting $C_{2a_1}$ into $C_4+C_4$. Then $$E(R')=E(R)+I\Big(p_0\prod_{i\geq2}p_{a_i}\Big) =E(R)+2I\Big(\prod_{i\geq2}p_{a_i}\Big)>E(R).$$ Which means that $G(R)$ consists entirely of $C_4$'s and $C_6$'s. To complete the proof of the theorem it suffices to show that (for $n\geq8$) replacing $2C_6$ by $3C_4$ will increase the number of extensions. Consider $$I\Big(p_2^3\prod_{i\geq3}p_{a_i}\Big) -I\Big(p_3^2\prod_{i\geq3}p_{a_i}\Big)= 3I\Big(p_2\prod_{i\geq3}p_{a_i}\Big) -2I\Big(\prod_{i\geq3}p_{a_i}\Big).$$ This is clearly positive since for any $\nu\geq2$, appending a $C_4$ to an element of $L(2,\nu)$ always increases the number of extensions. To see this note the injection which takes $$\pmatrix{\alpha_1&\alpha_2&\alpha_3&\dots&\alpha_\nu\cr \beta_1&\beta_2&\beta_3&\dots&\beta_\nu\cr e_1&e_2&e_3&\dots&e_\nu}\hbox{ to } \pmatrix{\alpha_1&\alpha_2&\alpha_3&\dots&\alpha_\nu&\nu+1&\nu+2\cr \beta_1&\beta_2&\beta_3&\dots&\beta_\nu&\nu+2&\nu+1\cr \nu+1&\nu+2&e_3&\dots&e_\nu&e_1&e_2}.$$ (3 similar injections are obtained by swapping $e_1\leftrightarrow e_2$ and/or $\nu_1\leftrightarrow\nu_2$ in the image.)\endpf \thrm\thcycmin. The minimising $R\in L(2,n)$ are precisely those for which $$G(R)\iso\cases{ C_{2n}&for $n\leq4$,\cr C_{2\nu+2}+C_{2\nu}&for odd $n=2\nu+1\geq5$,\cr C_{12}\hbox{ or }C_8+C_4\hbox{ or }3C_4&for $n=6$,\cr C_{2n}\hbox{ or }C_{2\nu+2}+C_{2\nu-2}&for even $n=2\nu\geq8$.\cr}$$ \prf Similar to \thcall\thcyc. Equation \eqcall\dokov\ tells us when replacing two cycles by a single cycle reduces $E(R)$. We omit the details.\endpf Having completely solved the $k=2$ case, we may assume for the remainder of the paper that $k\geq3$. \section Previously conjectured answers Define $S_{m,k}\in L(k,mk)$ to be such that $G(S_{m,k})\iso mK_{k,k}$. In \bibcl\BGM\ the following conjecture was made. \conj\congm. If $R\in L(k,mk)$ is maximising then $G(R)\iso G(S_{m,k})$. This paper represents an effort to resolve this conjecture. We will show that it is substantially (though not without exception) correct. We know already from \crcall\corbreg\ that the conjecture is true for all $k$ when $m=2$. We also know by \thcall\thcyc\ that there exists a counterexample when $k=2$ and $m=3$. Specifically, $$E(S_{3,2})=E\pmatrix{1&2&3&4&5&6\cr2&1&4&3&6&5\cr}=80 <82=E\pmatrix{1&2&3&4&5&6\cr2&3&1&5&6&4\cr}.$$ The only other case where we know \conjcall\congm\ fails is for $k=m=3$. It is an easy matter to check that $$E(S_{3,3})=12096<12108=E\pmatrix{1&2&3&4&5&6&7&8&9\cr2&3&4&1&6&7&8&9&5\cr 3&4&1&2&7&9&6&5&8\cr}.$$ \xdef\countersec{\the\secno} Curiously, in both the above examples $S_{m,k}$ is in fact {\it minimising} among rectangles for which $G(R)$ is disconnected. This is particularly interesting in light of our main result. A more general attempt to identify the matrices in $\lnk$ which maximise the permanent was made by Merriell \bibcl\BMerry. Merriell completely solved the $k=2$ and $k=3$ cases and conjectured a partial answer for larger values. Let $J_{r}$ and $Z_{r}$ denote $r\times r$ blocks of ones and zeroes respectively. We also use $J$ without a subscript to denote a (not necessarily square) block of ones of unspecified, but implied dimensions. Finally, let $D_r=\comp{I_r}$ denote the complement of the order $r$ identity matrix, $I_r$. Merriell's conjectures can then be stated as: \conj\conmo. Suppose $k\leq n\leq2k$ and that either $k\geq5$ or $n$ is even. The maximum permanent in $\lnk$ is achieved by a matrix with block structure $$\pmatrix{A&J\cr J&B\cr}$$ where $A$ and $B$ are square matrices with orders that differ by at most 1. Furthermore, $A$ and $B$ should be chosen to maximise their individual permanents. \conj\conmt. Let $n=tk+r$ for integers $k\geq5$, $t\geq1$ and $r\geq0$. Then the maximum permanent in $\lnk$ is achieved by $$\cases{(t-r)J_k+rD_{k+1}& when $r\leq\min\{t,k-3\}$,\cr (t-1)J_k+X_{k,r}&when $r=k-2$ or $r=k-1$,\cr}$$ where $$X_{k,k-2}=\pmatrix{J&I_{k-1}\cr I_{k-1}&J\cr} \hbox{ and }X_{k,k-1}=\pmatrix{J&Z_{k-1}\cr I_k&J\cr}.$$ \conjcall\conmt\ was shown to fail for $n=14$, $k=5$ in \bibcl\BZag, and it follows that the conjecture fails for $n=9+5t$, $k=5$ for every positive integer $t$. Also \conjcall\conmo\ is known \bibcl\BBol\ to fail for $n=9$, $k=7$. However, Merriell himself acknowledged that his pattern broke down in certain small cases (all of which he hoped to have excluded). The experience of this paper shows that isolated counterexamples do not render a conjecture on maximising the permanent in $\lnk$ worthless. The primary issue is whether the pattern holds for sufficiently large $k$ and $n$. In fact there is a serious flaw in \conjcall\conmo. For any positive integer $a$, it implies that there are maximising rectangles $R\in L(2,4a+2)$ and $R_1,R_2\in L(2,2a+1)$ such that $G(R)\iso G(R_1)+G(R_2)$, which contradicts \thcall\thcyc\ for all $a\geq2$. A similar observation applied to \thcall\MAIN\ will furnish another infinite family of counterexamples to \conjcall\conmo. \conjcall\conmt\ remains unresolved for $k\geq6$. The question of finding the maximum permanent in $\lnk$ when $k$ does not divide $n$ is problem~4 in \bibcl\BMC\ and \bibcl\BMCT. Problem~12 of \bibcl\BMCT\ asks whether this maximum permanent is achieved by a circulant. A {\it circulant\/} is a square matrix which is a linear combination of powers of the permutation matrix corresponding to the full cycle $(123\dots n)$. It is well known that in the cases covered by \thcall\thbreg, the maximum permanent is achieved by a circulant. Since the complement of a circulant is also a circulant, our main result will furnish another set of examples where the maximum is achieved by a circulant. In Table~1 below we identify maximising $R\in L(k,n)$ for some small values of $k$ and $n$. In the process we get more data relating to Minc's questions and Conjectures \congm\ to \conmt. For example, despite failing when $(m,k)=(3,2)$ or $(3,3)$, we see that \conjcall\congm\ is true for $(3,4)$, $(4,3)$, $(5,3)$ and probably also for $(3,5)$ and $(4,4)$. Note also, by \thcall\thcyc, that the conjecture holds for $(m,2)$ whenever $m>3$. \pageinsert \centerline{Table~1 (part 1): $A(R)$ for maximising $R\in L(k,n)$.} \vskip -10pt $$\matrix{ n\backslash k&\smash{\vrule height 8pt width 1pt depth 200pt}&3&4&5&6&7\cr \multispan7{\leaders\hrule height 4pt depth -3pt\hfill} \phantom{\vrule depth 3pt}\cr 7&&\hbox{Figure 1}&\comp{J_3\jn D_4}&\comp{2J_2\jn D_3}&D_7&J_7\cr &&(148)&(54)&(8)&[1]&[0]\cr\cr 8&&2D_4&{2J_4}&\comp{2D_4}&\comp{4J_2}&D_8\cr &&[1313]&[576]&[81]&[16]&[1]\cr\cr 9&&D_4\jn \comp{J_2\jn D_3}&\hbox{Figure 2} &\comp{J_4\jn D_5}&\comp{3J_3}&\comp{3J_2\jn D_3}\cr &&(12108)&({\bf2916})&(1056)&[216]&(16)\cr\cr 10&&2J_3\jn D_4&2D_5&{2J_5}&\comp{J_4\jn \comp{2D_3}}&\comp{2J_3\jn D_4}\cr &&({\bf127044})&[32826]&[14400]&(1968)&(324)\cr\cr 11&&2J_3\jn \comp{J_2\jn D_3}&D_5\jn\comp{3J_2}&{J_5\jn D_6}&{\comp{J_5\jn D_6}}&\comp{D_5\jn\comp{2D_3}}\cr &&(1448640)&(373208)&(86400)&(31800)&(3608)\cr\cr 12&&4J_3&{3J_4}&{2D_6}^*&{2J_6}&{\comp{2D6}}\,^*\cr &&[17927568]&[{\bf4783104}]&[1181737]&[518400]&[70225]\cr\cr 13&&3J_3\jn D_4&{2J_4\jn D_5}^*& \hidewidth{D_6\jn\comp{2J_2\jn D_3}}\,^*\hidewidth\cr &&({\bf238673088})&({\bf65641536})&(15950816)\cr\cr 14&&3J_3\jn \comp{J_2\jn D_3}&{2J_4\jn\comp{3J_2}}\,^* &{2(\comp{2J_2\jn D_3})}\,^*&&2J_7\cr &&({\bf3410776944})&({\bf961491456})&(241119120)&&[25401600]\cr\cr 15&&5J_3&{2J_4\jn\comp{J_3\jn D_4}}\,^*&{3J_5}^*\cr &&[{\bf52097831424}]&({14992781184})&[{\bf3891456000}]&&&\cr\cr 16&&{4J_3\jn D_4}^*&{4J_4}^*\cr &\smash{\vrule height 200pt width 1pt depth 2pt} &(\bf{846230552208})&[248341303296]& }$$ \vfill $$\vbox{\offinterlineskip\hrule \halign{\vrule#&$\;$\hfill$#$\hfill$\,$&#&$\;$#\hfill$\;$&#\vrule\cr height2pt&&&&\cr \strut&\multispan3{\hfill Key (also see notes on next page)\hfill}&\cr height2pt&&&&\cr \noalign{\hrule}\cr height2pt&&&&\cr \strut&\comp{A}&=&complement of A&\cr \strut&J_r&=&$r\times r$ block of 1s&\cr \strut&D_r&=&$\comp{I_r}$, where $I_r$ is the order $r$ identity&\cr \strut&\jn&=& direct sum&\cr \strut&rA&=&$\underbrace{A\jn A\jn\dots\jn A}_{\phantom{j}r\rm\;times}$&\cr} \hrule}$$ \vfill \endinsert \pageinsert \centerline{Table~1 (part 2): $A(R)$ for maximising $R\in L(k,n)$.} \vskip -10pt $$\matrix{ n\backslash k&\smash{\vrule height 8pt width 1pt depth 200pt}&8&9&10&11&12\cr \multispan7{\leaders\hrule height 4pt depth -3pt\hfill} \phantom{\vrule depth 3pt}\cr 10&&\comp{5J_2}&D_{10}&J_{10}&-&-\cr &&[32]&[1]&[0]\cr\cr 11&&\comp{J_3\jn 2D_4}&\comp{4J_2\jn D_3}&D_{11}&J_{11}&-\cr &&(486)&(32)&[1]&[0]\cr\cr 12&&\comp{3J_4}&\comp{4J_3}&\comp{6J_2}&D_{12}&J_{12}\cr &&[13824]&[1296]&[64]&[1]&[0]\cr\cr 13&&{\comp{J_5\jn\comp{2D_4}}}\,^*&{\comp{2J_4\jn D_5}}\,^* &\comp{3J_3\jn D_4}&\comp{5J_2\jn D_3}&D_{13}\cr &&(157560)&(25344)&(1944)&(64)&[1]\cr\cr 14&&&{\comp{J_5\jn\comp{\hbox{Figure 2}}}}\,^* &{\comp{2J_4\jn\comp{2D_3}}}\,^*&\comp{2J_3\jn 2D_4}&\comp{7J_2}\cr &&&(349920)\dagger&(47232)&(2916)&[128]\cr\cr 15&&&&\comp{3J_5}&{\comp{J_4\jn D_5\jn\comp{2D_3}}}\,^*&\comp{5J_3}\cr &&&&[1728000]&(86592)&[7776]\cr\cr 16&&2J_8&&&&\comp{4J_4}\cr &\smash{\vrule height 200pt width 1pt depth 2pt} &[1625702400]&&&&[331776] }$$ \vfill \underbar{Notes:} \item{$\bullet$} The table shows $A(R)$ for maximising $R\in L(k,n)$. To maximise the permanent in $\Lambda_n^{n-k}$ use the complement, $\comp{A(R)}$. \item{$\bullet$} In each case $M_{k,n}$ is given below $A(R)$. Values of $M_{k,n}$ which exceed those predicted by \conjcall\conmo\ are listed in {\bf bold}. \item{$\bullet$} The sole value of $M_{k,n}$ which breaches \conjcall\conmt\ is marked with a $\dagger$. Note that this value exceeds that of the counterexample provided in \bibcl\BZag. \item{$\bullet$} Values of $M_{k,n}$ which are achieved by circulant matrices are given in [brackets], whereas other values appear in (parentheses). \item{$\bullet$} The results were found by computer enumeration of graphs, except for those which follow from \thcall\thbreg, and the case $n=15$, $k=3$ which follows from \thcall\MAIN. \item{$\bullet$} Some of the results presented here were previously known from \bibcl\BMerry. \item{$\bullet$} Results marked * are provisional because not all graphs could be enumerated. All disconnected graphs and graphs with disconnected complement were generated in these cases. In addition, connected graphs containing at least 115, 421, 42 and 1212 4-cycles respectively were generated for $(n,k)=(12,5)$, (12,7), (13,4) and (13,9). \vfill \endinsert \midinsert $$\pmatrix{ 0&0&1&0&1&1&0\cr 0&1&0&0&1&0&1\cr 1&0&0&0&0&1&1\cr 0&0&0&0&1&1&1\cr 1&1&0&1&0&0&0\cr 1&0&1&1&0&0&0\cr 0&1&1&1&0&0&0\cr }\quad\hbox{or}\quad \pmatrix{ 0&0&0&0&1&1&1\cr 0&0&0&0&1&1&1\cr 0&0&0&1&0&1&1\cr 0&1&1&0&1&0&0\cr 1&0&1&1&0&0&0\cr 1&1&0&1&0&0&0\cr 1&1&1&0&0&0&0\cr }$$ \centerline{Figure~1: $A(R)$ for maximising $R\in L(3,7)$.} $$\pmatrix{ 0&0&0&0&0&1&1&1&1\cr 0&0&0&0&0&1&1&1&1\cr 0&0&0&0&1&1&0&1&1\cr 0&0&0&0&1&0&1&1&1\cr 0&0&1&1&0&1&1&0&0\cr 1&1&1&0&1&0&0&0&0\cr 1&1&0&1&1&0&0&0&0\cr 1&1&1&1&0&0&0&0&0\cr 1&1&1&1&0&0&0&0&0\cr }$$ \centerline{Figure~2: $A(R)$ for maximising $R\in L(4,9)$.} \endinsert In the light of Table~1 we propose the following research problem. \proclaim Research problem. When are the following statements true of maximising $R$ in $L(k,n)$? \item{(a)} $G(R)$ is unique up to isomorphism. \item{(b)} $G(R)$ contains exactly $\lfloor n/k\rfloor$ components (that being the greatest possible number of components). Similarly, $\comp{G(R)}$ contains $\lfloor n/(n-k)\rfloor$ components. \item{(c)} $\comp{G(R)}\iso G(R')$ for a maximising $R'\in L(n-k,n)$. \item{(d)} $A(R)$ can be constructed (up to permutation of the rows and columns) from copies of $J_1$ by recursive use of the direct sum and complement operations. \noindent Properties (a), (b), (c) and (d) seem to commonly but not universally hold. Can this observation be formalised? Note that for each property, Table~1 provides at least one counterexample. See also the forthcoming paper, \bibcl\BWW. There are only two cases where both $G(R)$ and $\comp{G(R)}$ are connected. These cases do not fit easily into the table, so they are dealt with separately in Figures~1 and~2. Figure~1 shows the only case covered by Table~1 where $G(R)$ is not unique up to isomorphism. Another case $(n=7, k=2)$ appeared in \thcall\thcyc. \section Above the roots We begin the proof of our main result by investigating the behaviour of the rook polynomial above its largest root. Let $R\in L(k,n)$ and suppose $v$ is a vertex of $G(R)$. Imitating \bibcl\BGee\ we define a tree $T(R,v)$ as follows. The vertices of $T(R,v)$ correspond to paths in $G(R)$ which start at $v$. Two vertices are adjacent if, of the two paths they correspond to, one is a maximal proper subpath of the other. The root of $T(R,v)$ is the vertex corresponding to the empty path. Let $\eta_{v,r}$ be the number of closed walks of length $r$ in $T(R,v)$ starting at $v$ and define $$w_r(R)=\frac12\sum_v\eta_{v,2r}.$$ The following properties of $w_r(R)$ are known (\bibcl\BGee, \bibcl\BGM) \item{(a)} $w_r(R)=\sum_i\lambda_i^r$ where $\{\lambda_1, \lambda_2,\dots, \lambda_n\}$ are the roots of $\rk(R,x)$. \item{(b)} Let $s$ be the number of 4-cycles in $G(R)$. Then $$\eqalign{ w_1&=nk,\cr w_2&=nk(2k-1),\cr w_3&=nk(5k^2-6k+2),\cr w_4&=nk(14k^3-28k^2+20k-5)-4s,\cr w_5&=nk(42k^4-120k^3+135k^2-70k+14)-40(k-1)s.\cr }\ref\expmom$$ \item{(c)} The rook polynomial $\rk(R,x)$ is given by the power series $$\rk(R,x)=x^n\exp\Big(-\sum_{r=1}^{\infty}{w_r(R)\over rx^r}\Big)\ref\rpps$$ which is convergent provided $x$ lies above the greatest root of $\rk(R,x)$. \thrm\thmom. Suppose $S=S_{m,k}$ and $R\in L(k,mk)$. Let $\lambda_S$ and $\lambda_R$ be the largest roots of $\rk(S,x)$ and $\rk(R,x)$ respectively. Then $\lambda_R\geq\lambda_S$ and $w_r(R)\geq w_r(S)$ for all $r$. \prf Let $v$ be a vertex in $G(A)$ for some $A\in L(k,mk)$. Consider a vertex $u$ of $T(A,v)$ which is a distance $d\geq1$ from the root. Let $P$ be the set of vertices in the path corresponding to $u$ and $e_u\in P$ the final vertex in that path. Then the degree of $u$ in $T(A,v)$ is given by $\deg(u)=1+|N(e_u)\setminus P|$ where $N(e_u)$ is the set of neighbours of $e_u$ in $G(A)$. Since $G(A)$ is bipartite and k-regular we have $$\deg(u)=1+k-\left|N(e_u)\cap P\right|\geq 1+k-\left\lceil{d\over2}\right\rceil.\ref\degbnd$$ Now in $G(S)$ every component is complete which means that the bound \eqcall\degbnd\ is achieved in $T(S,v)$ for every vertex $u$ (except the root, which is necessarily of degree $k$). It follows that $T(S,v_S)$ is isomorphic to a subgraph of $T(R,v_R)$ for arbitrary vertices $v_S$ and $v_R$ in $G(S)$ and $G(R)$ respectively. Hence $\eta_{v_S,r}\leq\eta_{v_R,r}$ for every $r$ which means that $w_r(S)\leq w_r(R)$. Now since the $r^{\rm th}$ moment of the roots of $\rk(R,x)$ dominates the $r^{\rm th}$ moment of the roots of $\rk(S,x)$ we conclude that $\lambda_R\geq\lambda_S$, otherwise taking $r$ sufficiently large yields a contradiction. \endpf The original reasoning behind \conjcall\congm\ is embodied in the following result. \thrm\thdiff. Suppose $R\in L(k,mk)$ is not isomorphic to $S=S_{m,k}$. Then for $x\geq4k-4$, $\rk(S,x)-\rk(R,x)\geq\rk(S,x)\big(2(k-1)^2x^{-4}+15(k-1)^3x^{-5}\big)$. \prf By applying \eqcall\rpps\ and \thcall\thmom\ we see that for $x\geq4k-4$, $${\rk(R,x)\over\rk(S,x)}=\exp\Big(-\sum_{r\geq1}{w_r(R)-w_r(S)\over rx^r}\Big) \leq\exp\Big(-{w_4(R)-w_4(S)\over 4x^4}-{w_5(R)-w_5(S)\over5x^5}\Big).$$ Next we use \eqcall\expmom, which shows that $\rk(R,x)\leq\rk(S,x)\exp\big(-(s-t)(x^{-4}+8(k-1)x^{-5})\big)$ where $s$, $t$ are the number of 4-cycles in $G(S)$ and $G(R)$ respectively. If we can show that $s-t\geq2(k-1)^2$ then by applying Taylor's Theorem to $\exp(\cdot)$ we will get $${\rk(R,x)\over\rk(S,x)}\leq 1-{2(k-1)^2\over x^{4}}-{16(k-1)^3\over x^{5}} + \Big({2(k-1)^2\over x^{4}}+{16(k-1)^3\over x^{5}}\Big)^2.\ref\tayser$$ Since $\big(2(k-1)^2x^{-4}+16(k-1)^3x^{-5}\big)^2\leq(k-1)^3x^{-5}$ for $x\geq4(k-1)$, the theorem is proved once we have \eqcall\tayser. It remains to show $s-t\geq2(k-1)^2$. Let $v$ be a vertex in $G(A)$ for some $A\in L(k,mk)$. Define $B_v$ to be the subgraph induced by the ball of radius 2 around $v$ in $G(A)$. Suppose that the vertices at distance 2 from $v$ are $v_1, v_2,\dots,v_l$ for some $l\geq k-1$. Let the degree of $v_i$ in $B_v$ be $d_i$, and relabel if necessary so that $d_i\geq d_{i+1}$ for each $i$. Call $f_v$ the number of 4-cycles in $G(A)$ which involve $v$. We have $$f_v=\sum_{i=1}^l{d_i\choose2}.\ref\numfc$$ Note that since $G(A)$ is $k$-regular bipartite, we must have $\sum_{i=1}^l d_i=k(k-1)$ and $d_i\leq k$ for each $i$. With these restrictions it is easily calculated that $f_v\leq (k-1){k\choose2}$ by noting that ${a+1\choose2}+{b-1\choose2}>{a\choose2}+{b\choose2}$ provided $a\geq b$. The maximum for $f_v$ is achieved only when $l=k-1$ and each $d_i=k$, which means that $v$ is contained in a complete component $K_{k,k}$. It follows that $s=\frac12n(k-1){k\choose2}>t$, where $n=mk$. It remains to find the maximum possible value of $t$. Take a copy of $S$ and perform the following surgery. Remove edges $(x,y)$ and $(x',y')$ from different components of $S$ and replace them with edges $(x,y')$ and $(x',y)$ to get a new graph $S'$. The surgery destroys $2(k-1)^2$ of the 4-cycles in $S$, and does not create any new 4-cycles in $S'$. We claim that $t\leq\frac12n(k-1){k\choose2}-2(k-1)^2$. First note that $R$ must have at least $4k$ vertices which are not in complete components. Of these vertices, unless there is a vertex $v$ satisfying $f_v>(k-1){k\choose2}-(2k-3)$ then we immediately have that $t\leq\frac12n(k-1){k\choose2}-k(2k-3)$ which is sufficient for $k\geq2$. Hence, \eqcall\numfc\ tells us the only remaining possibility is that $l=k$ and $d_1=d_2=\dots=d_{k-2}=k$, $d_{k-1}=k-a$ and $d_k=a$ for some $a\leq2$. The $a=1$ case when $R$ has only $4k$ vertices not in complete components is now easily seen to be the best of the remaining options. \endpf \section Between the roots We study the behaviour of the rook polynomial below its largest root. \thrm\thupwig. Let $w\approx0.27846$ satisfy $w+\log(w)+1=0$. Let $\beta=4(k-1)$ and suppose $\lambda_n<\beta$ is the largest root of $\rk(R,x)$ for a rectangle $R\in L(k,n)$. Then \item{(a)} $|\rk(R,x)|\leq(\beta-x)^nw^{-\phi n}$ for all $kn+k$ we see immediately that, $$I_{\tau}^{\infty}\big(\rk(R,x)\big)\leq e^{-\tau}(\tau-k)^n\sum_{i=0}^\infty\bigg({n\over\tau-k}\bigg)^i =e^{-\tau}(\tau-k)^{n+1}/(\tau-n-k).$$ Finally, $(\tau-k)/(\tau-n-k)=3+4/(m-2)\leq13/3$ for $m\geq5$. \endpf \lem\lmwigas. Suppose that $R\in L(k,n)$ where $n=mk$. Define $m'=\min\{m,6\}$. Then $\big|I_{0}^{4k}\big(\rk(R,x)\big)\big|\leq 4ke^{(2-m')k}(\frac12m'k)^n$. \prf It was proved in \bibcl\BGM\ that $$\Big|I_{0}^{4k}\big(\rk(R,x)\big)\Big|\leq 2^{-n}e^{2k}\int_{2k}^{6k}e^{-x}x^n\dx.\ref\pinch$$ Since ${d\over dx}(e^{-x}x^n)=e^{-x}x^{n-1}(n-x)$ we can bound the integrand in \eqcall\pinch\ by its value at $x=m'k$, giving $$\int_{2k}^{6k}e^{-x}x^n\dx\leq 4ke^{-m'k}(m'k)^n.$$\endpf In what follows we suppose $S=S_{m,k}$ and $R\in L(k,n)$ do not have isomorphic graphs. Then by combining \lemc\lmtail, \lemc\lmwigas\ and \eqcall\vdW, $$\eqalign{I_{4k}^{\tau}\big(\rk(S,x)\big)&= I_{0}^{\infty}\big(\rk(S,x)\big)-I_{0}^{4k}\big(\rk(S,x)\big) -I_{\tau}^{\infty}\big(\rk(S,x)\big)\cr &\geq n!\left({m-1\over m}\right)^n -{4k(\frac12m'k)^n\over e^{(m'-2)k}} -\frac{13}{3}e^{-\tau}(\tau-k)^n.\cr}\ref\bounb$$ Now $2(k-1)^2x^{-4}$ is a decreasing function of $x$ for $x>0$, so by \thcall\thdiff, $$I_{4k}^{\infty}\big(\rk(S,x)-\rk(R,x)\big)\geq I_{4k}^{\tau}\big(\rk(S,x)-\rk(R,x)\big)\geq \left({2(k-1)^2\over\tau^4}\right) I_{4k}^{\tau}\big(\rk(S,x)\big).\ref\bounc$$ Also \lemc\lmwigas\ tells us that $$\left|I_{0}^{4k}\big(\rk(S,x)-\rk(R,x)\big)\right| \leq\left|I_{0}^{4k}\big(\rk(S,x)\big)\right| +\left|I_{0}^{4k}\big(\rk(R,x)\big)\right| \leq{8k(\frac12m'k)^n\over e^{(m'-2)k}}.$$ Combining with \eqcall\bounb\ and \eqcall\bounc\ we see that if $$n!\left({m-1\over m}\right)^n -{4k(\frac12m'k)^n\over e^{(m'-2)k}} -\frac{13}{3}e^{-\tau}(\tau-k)^n- {4k(\frac12m'k)^n\tau^4\over e^{(m'-2)k}(k-1)^2}>0\ref\crux$$ then $I_{4k}^\infty\big(\rk(S,x)-\rk(R,x)\big)+ I_{0}^{4k}\big(\rk(S,x)-\rk(R,x)\big)>0$ and so $E(S)>E(R)$. Define $q_5=51$, $q_6=15$, $q_7=8$, $q_8=5$, $q_9=4$ and $q_{i}=3$ for $i\geq10$. It is a simple matter to establish that \eqcall\crux\ holds for $5\leq m\leq10$ and $k=q_m$. We use this as a basis for induction. In the notation of \bibcl\BAS\ we use $\Gamma$ and $\psi$ to denote the gamma and digamma functions respectively. Note that $\Gamma(n+1)=n!$ and $\psi(x)=\frac{d}{dx}\log\Gamma(x)$. Suppose that we make the following definitions $$\matrix{ f_1=\Gamma(n+1)\left({m-1\over m}\right)^n\hfill && f_2=4k(\frac12m'k)^ne^{(2-m')k}\hfill\cr\cr f_3=\frac{13}{3}e^{-\tau}(\tau-k)^n\hfill && f_4=4k(\frac12m'k)^ne^{(2-m')k}\tau^4(k-1)^{-2}\hfill\cr }$$ with the aim of showing that $f_1$ dominates the inequality \eqcall\crux. We shall prove that the ratios $f_1/f_2$, $f_1/f_3$ and $f_1/f_4$ are increasing functions of $k$ for any fixed $m\geq5$, provided $k\geq q_m$. However, first we must show that \eqcall\crux\ holds for $k=3$ and $m\geq10$. To that end, we fix $m'=6$ and observe that $${1\over kf_1}{\partial f_1\over\partial m}= \psi(n+1)+\log\Big({m-1\over m}\Big)+{1\over m-1}> \log(k)+\log(m-1)+{1\over m-1}\ref\dfom$$ because $\psi(n+1)>\log n$ for $n>0$. Meanwhile, $${1\over kf_4}{\partial f_4\over\partial m}= \log(k)+\log(3)+{4\over n}$$ and $\log(m-1)>\log(3)+1$ for $m\geq10$ so we conclude that $\log(f_1/f_4)$ is an increasing function of $m$ in this range. Immediately we get that $f_1/f_2$ also increases with $m$ for $m\geq10$ because $f_4/f_2=(3mk/2)^4(k-1)^{-2}$ trivially increases with $m$. In addition, $${1\over kf_3}{\partial f_3\over\partial m}= \log(k)+\log(\frac32m-1)-\frac12+{2\over3m-2}.\ref\dftm$$ Now $2/(3m-2)<1/(m-1)$ for positive $m$ and $\log(\frac32m-1)-\frac12<\log(m-1)$ for all $m>(\sqrt{e}-1)/(\sqrt{e}-3/2)\approx4.362$. Hence by \eqcall\dfom\ we see that $\log(f_1/f_3)$ increases with $m$ in the required range. Since \eqcall\crux\ holds when $k=3$ and $m=10$ we conclude that it must hold for $k=3$ and $m\geq10$. Next we fix $m\geq5$ and show that \eqcall\crux\ holds for all $k\geq q_m$, using the knowledge that it holds when $k=q_m$. We have, $${1\over mf_1}{\partial f_1\over\partial k}=\psi(n+1) +\log\Big({m-1\over m}\Big)>\log(k)+\log(m-1).$$ By comparison, $${1\over mf_4}{\partial f_4\over\partial k}= \log(k)+\log(\frac12m')+1+{2k^2+k-5\over mk(k-1)}-{m'\over m}.$$ Now $(2k^2+k-5)/(k^2-k)$ is a decreasing function for $k\geq(5+\sqrt{10})/3\approx2.721$, so for our purposes we may bound it by its value when $k=q_m$. It is then established by an easy case analysis that $\frac{\partial}{\partial k}\log(f_1)>\frac{\partial}{\partial k}\log(f_4)$ for $m\geq5$ and $k\geq q_m$, so we see that $f_1/f_4$ does indeed increase with $k$ in this range. Moreover $f_4/f_2=(3n/2)^4/(k-1)^2$ is an increasing function of $k$ provided $k\geq2$, so $f_1/f_2$ must also increase with $k$ in the required range. It remains to use the same approximation used on \eqcall\dftm\ to show that $${1\over mf_3}{\partial f_3\over\partial k}= \log(k)+\log(\frac32m-1)-\frac12<\log(k)+\log(m-1) <{1\over mf_1}{\partial f_1\over\partial k}.$$ We conclude that $f_1/f_2$, $f_1/f_3$ and $f_1/f_4$ are increasing functions of $k$, provided $m\geq5$ and $k\geq q_m$. Therefore inequality $\eqcall\crux$\ holds for all $m\geq5$ and $k\geq q_m$. We are left with only finitely many cases to check; namely $k=3,4,\dots,(q_m-1)$ for $m=5,6,7,8,9$. These cases will be checked in the final section. \section The `small' cases We turn our attention to the cases left unresolved by the preceding section, namely $3\leq k\leq q_m-1$ for $5\leq m\leq 9$. Since $\rk(S,x)\geq0$ for $\lambda_S\leq x\leq\lambda_R$ we see from \thcall\thdiff\ that $$I_{\lambda_S}^{4k-4}\big(\rk(S,x)\big)\geq I_{\lambda_R}^{4k-4}\big(\rk(R,x)\big)$$ and hence $$E(S)-E(R)\geq I_{4k-4}^\infty\big(\rk(S,x)-\rk(R,x)\big) -I_0^{\lambda_R}\big(\rk(R,x)\big)+I_0^{\lambda_S}\big(\rk(S,x)\big). \ref\basis$$ Notice that by \thcall\thdiff, $$I_{4k-4}^\infty\big(\rk(S,x)-\rk(R,x)\big) \geq I_{4k-4}^\infty\big(\rk(S,x)(2(k-1)^2x^{-4}+15(k-1)^3x^{-5})\big) .\ref\specmk$$ Now for specific values of $m$ and $k$, the bound in \eqcall\specmk\ can be explicitly calculated, as can $I_0^{\lambda_S}\big(\rk(S,x)\big)$, because we know that $\rk(S,x)=(\lag_k)^m$ where $\lag_k$ is defined by \eqcall\comrk. Hence the only term in \eqcall\basis\ we need to work on is $I_0^{\lambda_R}\big(\rk(R,x)\big)$. We use \thcall\thupwig\ and \thcall\thsecmom. Define the cutoffs and functions $$\matrix{ \displaystyle c_5=4k-4,\hfill &&\displaystyle f_5=e^{-x}(x-k)^{n-2}(c_5-x)^2,\hfill\cr \strut\displaystyle c_4={c_5+kw\over1+w},\hfill &&\displaystyle f_4=e^{-x}(c_5-x)^nw^{-(w/(w+1))n(c_5-k)/(c_5-x)},\hfill\cr \strut\displaystyle c_3=\min\{3k,c_4\},\hfill &&\displaystyle f_3=e^{-x}(x^2-2kx+2k^2-k)^{n/2},\hfill\cr \strut\displaystyle c_2=k-1,\hfill &&\displaystyle f_2=e^{-x}x^nw^{-c_1n/x},\hfill\cr \strut\displaystyle c_1={kw\over1+w},\hfill &&\displaystyle f_1=e^{-x}(k-x)^n.\hfill\cr }$$ so that $$I_0^{\lambda_R}\big(\rk(R,x)\big)\leq \sum_{i=1}^5\int_{c_{i-1}}^{c_i}f_i\dx\ref\sumint$$ where we assume $c_0=0$. Note that $f_5$ is positive between $\lambda_R$ and $c_5$. We consider the last integral in \eqcall\sumint\ first. We have, $${df_5\over dx}=e^{-x}(x-k)^{n-3}(c_5-x) \big(x^2-(n+k+c_5)x+c_5(n+k-2)+2k\big).\ref\dffive$$ Notice that the discriminant $\Delta=(n+k-c_5)^2+8(c_5-k)$ of the quadratic term in \eqcall\dffive\ satisfies $(n+k-c_5)^2<\Delta<(n+k-c_5+3k)^2$. We conclude that $f_5$ achieves its maximum in the interval $[k,c_5]$ when $x$ equals $$x_0=\frac12(n+k+c_5)-\frac12\big((n+k-c_5)^2+8(c_5-k)\big)^{1/2}.$$ This certainly means that $$\int_{c_4}^{c_5}f_5\dx\leq(c_5-c_4)e^{-x_0}(x_0-k)^{n-2}(c_5-x_0)^2.$$ We bound the other four integrals in \eqcall\sumint\ by noticing that the integrand is concave in each case (although the integral of $f_1$ may be explicitly calculated if preferred). To begin, suppose $l=ax+b$ and $f=e^{-x}l^nw^{c/l}$ where $a$, $b$, $c$ and $w$ are independent of $x$. Then $${l^2\over f}{d^2f\over dx^2}=\Big({ca\ln(w)\over l}+l+a-an\Big)^2 +(n-1)a^2-2al\geq(n-1)a^2-2al.$$ It is now a simple matter to check that $f_1$, $f_2$ and $f_4$ are concave in their required intervals. Next we show that $f_3$ is concave for $x\in[c_2,c_3]$. We claim that in this interval, and for integers $k\geq3$, $m\geq5$ and $n=mk$ it can easily be checked that $n-2(x-k)>\sqrt{n}$. Then $${d^2f_3\over dx^2}={f_3\over(x^2-2kx+2k^2-k)^2} \Big(\big(n(x-k)-(x-k)^2-(k^2-k)\big)^2+n\big((k^2-k)-(x-k)^2\big)\Big) \ref\fthrecon$$ which is clearly positive unless we assume $(x-k)^2\geq k^2-k\geq6$. Since $x-k\geq c_2-k=-1$ it follows that $x>k$ and hence $n(x-k)-(x-k)^2-(k^2-k)\geq\big(n-2(x-k)\big)(x-k)>0$. But now $$n(x-k)-(x-k)^2-(k^2-k)>\sqrt{n}(x-k)>0$$ which means that \eqcall\fthrecon\ is positive, as required. Now the integral of a concave function can be bounded above by taking a simple polygonal approximation to the curve. Specifically, in \eqcall\sumint\ we can subdivide each interval into $\sigma$ subintervals each of width $\delta_i=(c_i-c_{i-1})/\sigma$, giving, $$I_0^{\lambda_R}\big(\rk(R,x)\big)\leq (c_5-c_4)f_5(x_0)+ \sum_{i=1}^4\sum_{j=1}^{\sigma} {\delta_i\over2}\Big(f_i\big(c_{i-1}+(j-1)\delta_i\big) +f_i\big(c_{i-1}+{j\delta_i}\big)\Big).\ref\sumsum$$ Taking $\sigma=10$ the bound in \eqcall\sumsum\ was computed for $m=5,6,7,8,9$ and $k=3,4,\dots,q_m-1$. Together with \eqcall\specmk\ this allowed confirmation that $E(S)>E(R)$ in each of these cases, except when $m=5$ and $k\geq12$. For this subcase \eqcall\specmk\ becomes too slow to compute for large $k$, but it is sufficient to use \eqcall\sumsum\ as a substitute for \lemc\lmwigas\ in the derivation of \eqcall\crux. Specifically, if $B$ is the bound computed in \eqcall\sumsum\ and $$n!(4/5)^n-B -\frac{13}{3}e^{-\tau}(\tau-k)^n-{B\tau^4\over(k-1)^2}>0\ref\crvvx$$ then $E(S)>E(R)$. It can quickly be confirmed that \eqcall\crvvx\ holds for $k=12,13,\dots,50$ with $m=5$, which completes the proof of the `small' cases. The entire calculation was checked independently by numerical integration. Combined with the results of the preceding section, we get the main result. \thrm\MAIN. Let $m\geq5$, $k\geq2$ and $n=mk$ be integers. If $R\in L(k,n)$ is maximising then $G(R)\iso mK_{k,k}$. Equivalently, if $M$ is a $(0,1)$-matrix with exactly $k$ zeroes in each row and in each column then the permanent $\per(M)$ is maximised (uniquely, up to permutations of the rows and columns) by the matrix with block structure $$\pmatrix{ Z_k&J_k&J_k&\cdots&J_k\cr J_k&Z_k&J_k&\cdots&J_k\cr J_k&J_k&Z_k&\cdots&J_k\cr \vdots&\vdots&\vdots&\ddots&\vdots\cr J_k&J_k&J_k&\cdots&Z_k\cr }\ref\optmat$$ where $Z_k$, $J_k$ are $k\times k$ blocks of zeroes and ones respectively. \corol\main. For integers $m\geq5$, $k\geq2$ and $n=mk$ $$M_{k,n}=\int_0^\infty e^{-x}\big(\lag_k(x)\big)^m\dx.$$ Also note that \bibcl\BChet\ cites an inclusion-exclusion formula of Kaplansky for the permanent of \eqcall\optmat. However, to find $M_{k,n}$ it is just as easy to calculate the integral in \crcall\main. In closing, we observe that it is quite possible that \thcall\MAIN\ can be extended to show that \conjcall\congm\ holds with only a finite number of exceptions when $m=3$. In fact we conjecture that there are no exceptions other than the two discussed in \S\countersec. However the techniques presented in this paper are not yet strong enough to apply when $m<5$. Hope of proving there are finitely many exceptions to \conjcall\congm\ is bolstered by the observation that $\big|\lag_k(x)\big|\leq k!e^{x/2}$ for $x\geq0$ (c.f.\ inequality 22.14.12 of \bibcl\BAS) and hence $$\int_0^{4k-4}e^{-x}\rk(S_{m,k})\dx \leq(k!)^m\int_0^{4k-4}e^{(m-2)x/2}\dx \leq{2(k!)^m\over m-2}e^{2k(m-2)}.\ref\SIRwig$$ This means by \eqcall\vdW\ that for fixed $m\geq3$ and $n=mk\rightarrow\infty$ the initial segment of the integral $I(S_{m,k})$ is asymptotically insignificant compared to $E(S_{m,k})$, because $${2(k!)^m\over m-2}e^{2k(m-2)}\Big/\big(n!(1-k/n)^n\big)= O\big(k^{(m-1)/2}\big)\bigg({e^{2m-4}\over(m-1)^m}\bigg)^k=o(1).$$ If $I_0^{4k-4}(R)$ could be similarly handled for other $R\in L(k,n)$ then \thcall\thdiff\ would suffice. \vfill \section References \bibit{\BAS} M.~Abramowitz and I.~A.~Stegun, {\it Handbook of Mathematical Functions\/}, Dover publications, New York, 1965. \bibit{\BBol} V.~I.~Bolshakov, The spectrum of the permanent on $\lnk$, {\it Proceedings of the All-Union Seminar on Discrete Mathematics and its Applications\/} (Russian) ed.\ O.~B.~Lupanov, Moskov.\ Gos.\ Univ., Moscow, 1986, 65-73. \bibit{\BBg} L.~M.~\bgmn, Some properties of nonnegative matrices and their permanents, {\it Soviet Math.\ Dokl.\/} {\bf14}:945-949 (1973). \bibit{\BBGM} R.~A.~Brualdi, J.~L.~Goldwasser and T.~S.~Michael, Maximum permanents of matrices of zeroes and ones, {\it J.\ Comb.\ Th.\ A\/} {\bf47}:207-245 (1988). \bibit{\BChet} F.~R.~K.~Chung, P.~Diaconis, R.~L.~Graham and C.~L.~Mallows, On the permanents of complements of the direct sums of identity matrices, {\it Adv.\ in Appl.\ Math.\/} {\bf2}:121-137 (1981). \bibit{\BGee} C.~D.~Godsil, Matchings and walks in graphs, {\it J.\ Graph Th.\/} {\bf5}:285-297 (1981). \bibit{\BGM} C.~D.~Godsil and B.~D.~McKay, Asymptotic enumeration of Latin rectangles, {\it J.\ Comb.\ Th.\ B\/} {\bf48}:19-44 (1990). \bibit{\BHL} O.~J.~Heilmann and E.~H.~Lieb, Theory of monomer-dimer systems, {\it Comm.\ Math.\ Physics\/} {\bf25}:190-232 (1972). \bibit{\BJR} S.~A.~Joni and G.-C.~Rota, A vector space analog of permutations with restricted position, {\it J.\ Comb.\ Th.\ A\/} {\bf29}:59-73 (1980). \bibit{\BMerry} D.~Merriell, The maximum permanent in $\lnk$, {\it Linear and Multilinear Algebra\/} {\bf9}:81-91 (1980). \bibit{\BMC} H.~Minc, {\it Permanents\/}, Encyclopedia Math.\ Appl., Addison-Wesley, Reading, Mass., 1978. \bibit{\BMCT} H.~Minc, Theory of permanents 1978-1981, {\it Linear and Multilinear Algebra\/} {\bf12}:227-263, (1983). \bibit{\BS} A.~Schrijver, Bounds on permanents, and the number of 1-factors and 1-factorizations of bipartite graphs, {\it London Math.\ Soc.\ Lecture Note Ser.\/} {\bf82}:107-134 (1983). \bibit{\BW} I.~M.~Wanless, The \hdc\ on permanents fails, (submitted for publication). \bibit{\BWW} I.~M.~Wanless, Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum, (submitted for publication). \bibit{\BZag} N.~Zagaglia-Salvi, Permanents and determinants of circulant $(0,1)$-matrices, {\it Matematiche (Catania)\/} {\bf39}:213-219 (1984). \end