Maximising the permanent of (0,1)-matrices and the number of extensions of Latin rectangles

B. D. McKay and I. M. Wanless Department of Computer Science Australian National University Canberra ACT 0200 Australia bdm@cs.anu.edu.au / imw@cs.anu.edu.au

Submitted: February 18, 1997; Accepted: March 15, 1997; Received in final form: February 8, 1998. AMS Classifications 15A15, 05C70, 05B15.

Let k ≥ 2, m ≥ 5 and n = mk be integers. By finding bounds for certain rook polynomials, we identify the k × n Latin rectangles with the most extensions to (k + 1) × 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.

§1. The problem

Let k and n be positive integers with k ≤ n. A k × n Latin rectangle is a k × n matrix of entries from {1, 2, …, n} such that no entry is duplicated within any row or any column. We use L(k, n) for the set of k × n Latin rectangles. For R ∈ L(k, n) define E(R) to be the number of R′ ∈ 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 extensions of R. We call R_{1} ∈ L(k, n) a maximising rectangle if E(R_{1}) ≥ E(R) for every R ∈ L(k, n). We define M_{k,n} = E(R_{1}) for a maximising R_{1}. Similarly we call R_{2} ∈ L(k, n) a minimising rectangle if E(R_{2}) ≤ E(R) for every R ∈ 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 ∈ 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}, …, u_{n}} and {v_{1}, v_{2}, …, 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 \overline{G} to denote the complement within K_{n,n} of G. Note that G(R) is k-regular, \overline{G(R)} is (n − k)-regular and E(R) is the number of perfect matchings in \overline{G(R)}. Finding a maximising k ×n Latin rectangle 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 Λ_{n}^{k} 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) ∈ Λ_{n}^{k} defined by

(A(R))_{ij} = \{ \begin{matrix}1, & if u_{i} is adjacent to v_{j} in G(R); \\ 0, & otherwise. \end{matrix}

We call A(R) the biadjacency matrix of G(R). Note that E(R) is the permanent of \overline{A(R)}, the biadjacency matrix of \overline{G(R)}. Hence the question of finding a maximising k × n Latin rectangle 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 (Theorem 10) is that if m ≥ 5 then every maximising R ∈ L(k, mk) has G(R) isomorphic to m copies of K_{k,k}. This partially answers problems 4 and 12 of Minc [12].

§2. What is known

The literature on bounds for permanents is quite extensive. Minc [11], [12] and Schrijver [13] 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} ≥ n!(1 − k/n)^{n},  (1)

and the Brègman bound,

M_{k,n} ≤ ((n − k)!)^{n/(n−k)}.  (2)

Brègman proved (2) in [3], which also contains the following theorem.

Theorem 1. Let k, m ≥ 2 be integers and R ∈ L((m − 1)k, mk) be maximising. Then \overline{G(R)} consists of m copies of K_{k,k}.

We note the following corollary.

Corollary 1. R ∈ L(k, 2k) is maximising if and only if G(R) is disconnected.

There has been substantial effort towards enumerating Latin squares (n × n Latin rectangles), often by counting the extensions of Latin rectangles. The best asymptotic estimates to date are contained in [7], which employs similar tools to the present paper.

Let R ∈ 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 ρ(R, x) by

ρ(R, x) = ρ(G(R), x) = ∑_{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 [8], while the second is due to Joni and Rota [9].

Theorem 2. For any R ∈ L(k, n) where k ≥ 2, the roots of ρ(G(R), x) are real and lie in the open interval (0, 4k − 4). For R ∈ L(1, n), ρ(G(R), x) = (x − 1)^{n}.

Theorem 3. The number of extensions of R ∈ L(k, n) is given by E(R) = I_{0}^{∞}(ρ(R, x)), where the linear operator I_{a}^{b}(·) is defined by

I_{a}^{b}(f(x)) = ∫_{a}^{b} e^{−x}f(x) dx.

The integral defined in Theorem 3 is the fundamental tool in this paper, as it was in [7]. We use I(·) as shorthand for I_{0}^{∞}(·).

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 ρ(G, x) = ∏_{i} ρ(C_{i}, x). Secondly, for an arbitrary integer a,

ρ(K_{a,a}) = L_{a}(x) = (−1)^{a}a! ∑_{i=0}^{a} \binom{a}{i}\frac{(−x)^{i}}{i!} .  (3)

That is, the rook polynomial of a complete bipartite graph is a Laguerre polynomial, normalised to be monic.

§3. The k = 2 case

Every R ∈ L(1, n) satisfies E(R) = n! ∑_{i=0}^{n}(−1)^{i}/i!, that being the number of derangements of {1, 2, …, n}. Hence, the smallest case for which the question of identifying maximising rectangles is interesting is the case k = 2.

Let U_{n,t} denote the set of (0, 1)-matrices of order n containing exactly t zeroes (without restriction on row or column sums). In [4] the matrices maximising the permanent in U_{n,t} are identified for t ≤ 2n. When t = 2n the answer turns out to be an element of Λ_{n}^{n−2}, except in the case n = 5. The maximising rectangles in L(2, n) are thereby found for all n ≠ 5. In Theorem 4 (below) we present a new way of obtaining this result.

Every component of G(R) for R ∈ 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) = ρ(C_{2i}, x) for each i ≥ 2. By extension we define p_{0} = 2 and p_{1} = x − 2 so that p_{i}(4x^{2}) = 2T_{2i}(x) for each i ≥ 0, where T_{n}(x) is the n^{th} Chebyshev polynomial of the first kind. This leads [14] to

p_{a}p_{b} = p_{a+b} + p_{a−b} for 0 ≤ b ≤ a.  (4)

Formula (4) is the key to the next two theorems, because it shows us when it is profitable to split long cycles.

Theorem 4. When 2 ≤ n ≤ 4 or n ≥ 8 the maximising R ∈ L(2, n) are those which maximise the number of components in G(R). For 5 ≤ n ≤ 7 the maximising 2 × n rectangles are those R for which

G(R) ≅ \{ \begin{matrix}C_{10} & for n = 5, \\ C_{6} + C_{6} & for n = 6, \\ C_{10} + C_{4} or C_{6} + 2C_{4} & for n = 7. \end{matrix}

Here + denotes disjoint union and rG is shorthand for \underbrace{G + G + … + G}_{r times}.

Proof: The theorem is easily established for n ≤ 7 so we assume n ≥ 8. Let R ∈ L(k, n) be maximising and suppose G(R) consists of c cycles C_{2a_{1}}, C_{2a_{2}}, …, C_{2a_{c}}. Clearly n = ∑ a_{i} and ρ(G(R), x) = ∏ 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} ≤ 5. 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 (4)

ρ(G(R′), x) = p_{2}p_{a_{1}−2} ∏_{i≥2} p_{a_{i}} = ρ(G(R), x) + p_{a_{1}−4} ∏_{i≥2} p_{a_{i}}.

Now

E(R′) = I(ρ(G(R′), x)) = E(R) + I(p_{a_{1}−4} ∏_{i≥2} p_{a_{i}}).  (5)

Our assumptions that n > 6 and a_{1} > 5 mean that I(p_{a_{1}−4} ∏_{i≥2} p_{a_{i}}) > 0 by (1) because it is the number of extensions of some rectangle in L(2, n − 4). Thus (5) breaches our choice of R, proving that a_{1} ≤ 5.

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(p_{1} ∏_{i≥2} p_{a_{i}}). If a_{2} ≥ 3 then

I(p_{1} ∏_{i≥2} p_{a_{i}}) = I(p_{a_{2}+1} ∏_{i≥3} p_{a_{i}}) + I(p_{a_{2}−1} ∏_{i≥3} p_{a_{i}})

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 Latin rectangles. Thus we may assume that a_{i} = 2 for i ≥ 2. Now

I(p_{1}p_{2}^{c−1}) = I(p_{3}p_{2}^{c−2}) + I(p_{1}p_{2}^{c−2})

which by induction yields that I(p_{1}p_{2}^{c−1}) is zero when c = 2 and positive for c ≥ 3. As n ≥ 8 it follows that there must be at least c ≥ 3 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(p_{0} ∏_{i≥2} p_{a_{i}}) = E(R) + 2I( ∏_{i≥2} p_{a_{i}}) > 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 ≥ 8) replacing 2C_{6} by 3C_{4} will increase the number of extensions. Consider

I(p_{2}^{3} ∏_{i≥3} p_{a_{i}}) − I(p_{3}^{2} ∏_{i≥3} p_{a_{i}}) = 3I(p_{2} ∏_{i≥3} p_{a_{i}}) − 2I( ∏_{i≥3} p_{a_{i}}).

This is clearly positive since for any ν ≥ 2, appending a C_{4} to an element of L(2, ν) always increases the number of extensions. To see this note the injection which takes

( \begin{matrix}α_{1} & α_{2} & α_{3} & … & α_{ν} \\ β_{1} & β_{2} & β_{3} & … & β_{ν} \\ e_{1} & e_{2} & e_{3} & … & e_{ν} \end{matrix} ) to ( \begin{matrix}α_{1} & α_{2} & α_{3} & … & α_{ν} & ν + 1 & ν + 2 \\ β_{1} & β_{2} & β_{3} & … & β_{ν} & ν + 2 & ν + 1 \\ ν + 1 & ν + 2 & e_{3} & … & e_{ν} & e_{1} & e_{2} \end{matrix} ) .

(3 similar injections are obtained by swapping e_{1} ↔ e_{2} and/or ν_{1} ↔ ν_{2} in the image.) ⊙

Theorem 5. The minimising R ∈ L(2, n) are precisely those for which

G(R) ≅ \{ \begin{matrix}C_{2n} & for n ≤ 4, \\ C_{2ν+2} + C_{2ν} & for odd n = 2ν + 1 ≥ 5, \\ C_{12} or C_{8} + C_{4} or 3C_{4} & for n = 6, \\ C_{2n} or C_{2ν+2} + C_{2ν−2} & for even n = 2ν ≥ 8. \end{matrix}

Proof: Similar to Theorem 4. Equation (4) tells us when replacing two cycles by a single cycle reduces E(R). We omit the details. ⊙

Having completely solved the k = 2 case, we may assume for the remainder of the paper that k ≥ 3.

§4. Previously conjectured answers

Define S_{m,k} ∈ L(k, mk) to be such that G(S_{m,k}) ≅ mK_{k,k}. In [7] the following conjecture was made.

Conjecture 1. If R ∈ L(k, mk) is maximising then G(R) ≅ 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 Corollary 1 that the conjecture is true for all k when m = 2. We also know by Theorem 4 that there exists a counterexample when k = 2 and m = 3. Specifically,

E(S_{3,2}) = E ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 4 & 3 & 6 & 5 \end{matrix} ) = 80 < 82 = E ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & 1 & 5 & 6 & 4 \end{matrix} ) .

The only other case where we know Conjecture 1 fails is for k = m = 3. It is an easy matter to check that

E(S_{3,3}) = 12096 < 12108 = E ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & 3 & 4 & 1 & 6 & 7 & 8 & 9 & 5 \\ 3 & 4 & 1 & 2 & 7 & 9 & 6 & 5 & 8 \end{matrix} ) .

Curiously, in both the above examples S_{m,k} is in fact 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 Λ_{n}^{k} which maximise the permanent was made by Merriell [10]. 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 × 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} = \overline{I_{r}} denote the complement of the order r identity matrix, I_{r}. Merriell’s conjectures can then be stated as:

Conjecture 2. Suppose k ≤ n ≤ 2k and that either k ≥ 5 or n is even. The maximum permanent in Λ_{n}^{k} is achieved by a matrix with block structure

( \begin{matrix}A & J \\ J & B \end{matrix} )

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.

Conjecture 3. Let n = tk + r for integers k ≥ 5, t ≥ 1 and r ≥ 0. Then the maximum permanent in Λ_{n}^{k} is achieved by

\{ \begin{matrix}(t − r)J_{k} + rD_{k+1} & when r ≤ min\{t, k − 3\}, \\ (t − 1)J_{k} + X_{k,r} & when r = k − 2 or r = k − 1, \end{matrix}

where

X_{k,k−2} = ( \begin{matrix}J & I_{k−1} \\ I_{k−1} & J \end{matrix} ) and X_{k,k−1} = ( \begin{matrix}J & Z_{k−1} \\ I_{k} & J \end{matrix} ) .

Conjecture 3 was shown to fail for n = 14, k = 5 in [16], and it follows that the conjecture fails for n = 9 + 5t, k = 5 for every positive integer t. Also Conjecture 2 is known [2] 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 Λ_{n}^{k} worthless. The primary issue is whether the pattern holds for sufficiently large k and n.

In fact there is a serious flaw in Conjecture 2. For any positive integer a, it implies that there are maximising rectangles R ∈ L(2, 4a + 2) and R_{1}, R_{2} ∈ L(2, 2a + 1) such that G(R) ≅ G(R_{1}) + G(R_{2}), which contradicts Theorem 4 for all a ≥ 2. A similar observation applied to Theorem 10 will furnish another infinite family of counterexamples to Conjecture 2. Conjecture 3 remains unresolved for k ≥ 6.

The question of finding the maximum permanent in Λ_{n}^{k} when k does not divide n is problem 4 in [11] and [12]. Problem 12 of [12] asks whether this maximum permanent is achieved by a circulant. A circulant is a square matrix which is a linear combination of powers of the permutation matrix corresponding to the full cycle (123 … n). It is well known that in the cases covered by Theorem 1, 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 ∈ 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 1 to 3. For example, despite failing when (m, k) = (3, 2) or (3, 3), we see that Conjecture 1 is true for (3, 4), (4, 3), (5, 3) and probably also for (3, 5) and (4, 4). Note also, by Theorem 4, that the conjecture holds for (m, 2) whenever m > 3.

In the light of Table 1 we propose the following research problem.

Research problem. When are the following statements true of maximising R in L(k, n)?

(a) G(R) is unique up to isomorphism.

(b) G(R) contains exactly ⌊n/k⌋ components (that being the greatest possible number of components). Similarly, \overline{G(R)} contains ⌊n/(n − k)⌋ components.

(c) \overline{G(R)} ≅ G(R′) for a maximising R′ ∈ L(n − k, n).

(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.

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, [15].

the electronic journal of combinatorics 5 (1998), #R11 8

Table 1 (part 1): A(R) for maximising R ∈ L(k, n).

n\k  3  4  5  6  7
7  Figure 1  \overline{J_{3} ⊕ D_{4}}  \overline{2J_{2} ⊕ D_{3}}  D_{7}  J_{7}
(148)  (54)  (8)  [1]  [0]
8  2D_{4}  2J_{4}  \overline{2D_{4}}  \overline{4J_{2}}  D_{8}
[1313]  [576]  [81]  [16]  [1]
9  D_{4} ⊕ \overline{J_{2} ⊕ D_{3}}  Figure 2  \overline{J_{4} ⊕ D_{5}}  \overline{3J_{3}}  \overline{3J_{2} ⊕ D_{3}}
(12108)  (2916)  (1056)  [216]  (16)
10  2J_{3} ⊕ D_{4}  2D_{5}  2J_{5}  \overline{J_{4} ⊕ \overline{2D_{3}}} \overline{2J_{3} ⊕ D_{4}}
(127044)  [32826]  [14400]  (1968)  (324)
11  2J_{3} ⊕ \overline{J_{2} ⊕ D_{3}}  D_{5} ⊕ \overline{3J_{2}}  J_{5} ⊕ D_{6}  \overline{J_{5} ⊕ D_{6}}  \overline{D_{5} ⊕ \overline{2D_{3}}}
(1448640)  (373208)  (86400)  (31800)  (3608)
12  4J_{3}  3J_{4}  2D_{6}^{∗}  2J_{6}  \overline{2D6}^{∗}
[17927568]  [4783104]  [1181737]  [518400] [70225]
13  3J_{3} ⊕ D_{4}  2J_{4} ⊕ D_{5}^{∗} D_{6} ⊕ \overline{2J_{2} ⊕ D_{3}} ^{∗}
(238673088)  (65641536)  (15950816)
14  3J_{3} ⊕ \overline{J_{2} ⊕ D_{3}}  2J_{4} ⊕ \overline{3J_{2}} ^{∗}  2(\overline{2J_{2} ⊕ D_{3}})^{∗}  2J_{7}
(3410776944)  (961491456) (241119120)  [25401600]
15  5J_{3}  2J_{4} ⊕ \overline{J_{3} ⊕ D_{4}} ^{∗}  3J_{5}^{∗}
[52097831424] (14992781184) [3891456000]
16 4J_{3} ⊕ D_{4}^{∗} 4J_{4}^{∗}
(846230552208) [248341303296]

Key (also see notes on next page)

\overline{A} = complement of A
J_{r} = r × r block of 1s
D_{r} = \overline{I_{r}}, where I_{r} is the order r identity
⊕ = direct sum
rA = \underbrace{A ⊕ A ⊕ … ⊕ A}_{r times}

Table 1 (part 2): A(R) for maximising R ∈ L(k, n).

n\k  8  9  10  11  12
10  \overline{5J_{2}}  D_{10}  J_{10}  −  −
[32]  [1]  [0]
11  \overline{J_{3} ⊕ 2D_{4}}  \overline{4J_{2} ⊕ D_{3}}  D_{11}  J_{11}  −
(486)  (32)  [1]  [0]
12  \overline{3J_{4}}  \overline{4J_{3}}  \overline{6J_{2}}  D_{12}  J_{12}
[13824]  [1296]  [64]  [1]  [0]
13  \overline{J_{5} ⊕ \overline{2D_{4}}} ^{∗}  \overline{2J_{4} ⊕ D_{5}} ^{∗}  \overline{3J_{3} ⊕ D_{4}}  \overline{5J_{2} ⊕ D_{3}}  D_{13}
(157560)  (25344)  (1944)  (64)  [1]
14  \overline{J_{5} ⊕ \overline{Figure 2}}^{∗} \overline{2J_{4} ⊕ \overline{2D_{3}}} ^{∗}  \overline{2J_{3} ⊕ 2D_{4}}  \overline{7J_{2}}
(349920)†  (47232)  (2916)  [128]
15  \overline{3J_{5}}  \overline{J_{4} ⊕ D_{5} ⊕ \overline{2D_{3}}} ^{∗}  \overline{5J_{3}}
[1728000]  (86592)  [7776]
16  2J_{8}  \overline{4J_{4}}
[1625702400]  [331776]

\underline{Notes:}

• The table shows A(R) for maximising R ∈ L(k, n). To maximise the permanent in Λ_{n}^{n−k} use the complement, \overline{A(R)}.

• In each case M_{k,n} is given below A(R). Values of M_{k,n} which exceed those predicted by Conjecture 2 are listed in bold.

• The sole value of M_{k,n} which breaches Conjecture 3 is marked with a †. Note that this value exceeds that of the counterexample provided in [16].

• Values of M_{k,n} which are achieved by circulant matrices are given in [brackets], whereas other values appear in (parentheses).

• The results were found by computer enumeration of graphs, except for those which follow from Theorem 1, and the case n = 15, k = 3 which follows from Theorem 10.

• Some of the results presented here were previously known from [10].

• 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).

( \begin{matrix}0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \end{matrix} ) or ( \begin{matrix}0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \end{matrix} )

Figure 1: A(R) for maximising R ∈ L(3, 7).

( \begin{matrix}0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix} )

Figure 2: A(R) for maximising R ∈ L(4, 9).

There are only two cases where both G(R) and \overline{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 Theorem 4.

§5. 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 ∈ L(k, n) and suppose v is a vertex of G(R). Imitating [6] 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 η_{v,r} be the number of closed walks of length r in T (R, v) starting at v and define

w_{r}(R) = \frac{1}{2} ∑_{v} η_{v,2r}.

The following properties of w_{r}(R) are known ([6], [7])

(a) w_{r}(R) = ∑_{i} λ_{i}^{r} where {λ_{1}, λ_{2}, …, λ_{n}} are the roots of ρ(R, x).

(b) Let s be the number of 4-cycles in G(R). Then

\begin{aligned}w_{1} & = nk, \\ w_{2} & = nk(2k − 1), \\ w_{3} & = nk(5k^{2} − 6k + 2), \\ w_{4} & = nk(14k^{3} − 28k^{2} + 20k − 5) − 4s, \\ w_{5} & = nk(42k^{4} − 120k^{3} + 135k^{2} − 70k + 14) − 40(k − 1)s. \end{aligned}  (6)

(c) The rook polynomial ρ(R, x) is given by the power series

ρ(R, x) = x^{n} exp ( − ∑_{r=1}^{∞} \frac{w_{r}(R)}{rx^{r}})  (7)

which is convergent provided x lies above the greatest root of ρ(R, x).

Theorem 6. Suppose S = S_{m,k} and R ∈ L(k, mk). Let λ_{S} and λ_{R} be the largest roots of ρ(S, x) and ρ(R, x) respectively. Then λ_{R} ≥ λ_{S} and w_{r}(R) ≥ w_{r}(S) for all r.

Proof: Let v be a vertex in G(A) for some A ∈ L(k, mk). Consider a vertex u of T (A, v) which is a distance d ≥ 1 from the root. Let P be the set of vertices in the path corresponding to u and e_{u} ∈ 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}) \ 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 − |N(e_{u}) ∩ P | ≥ 1 + k − ⌈\frac{d}{2}⌉ .  (8)

Now in G(S) every component is complete which means that the bound (8) 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 η_{v_{S},r} ≤ η_{v_{R},r} for every r which means that w_{r}(S) ≤ w_{r}(R).

Now since the r^{th} moment of the roots of ρ(R, x) dominates the r^{th} moment of the roots of ρ(S, x) we conclude that λ_{R} ≥ λ_{S}, otherwise taking r sufficiently large yields a contradiction. ⊙

The original reasoning behind Conjecture 1 is embodied in the following result.

Theorem 7. Suppose R ∈ L(k, mk) is not isomorphic to S = S_{m,k}. Then for x ≥ 4k − 4, ρ(S, x) − ρ(R, x) ≥ ρ(S, x)(2(k − 1)^{2}x^{−4} + 15(k − 1)^{3}x^{−5}).

Proof: By applying (7) and Theorem 6 we see that for x ≥ 4k − 4,

\frac{ρ(R, x)}{ρ(S, x)} = exp ( − ∑_{r≥1} \frac{w_{r}(R) − w_{r}(S)}{rx^{r}}) ≤ exp ( − \frac{w_{4}(R) − w_{4}(S)}{4x^{4}} − \frac{w_{5}(R) − w_{5}(S)}{5x^{5}}).

Next we use (6), which shows that ρ(R, x) ≤ ρ(S, x) exp ( − (s − t)(x^{−4} + 8(k − 1)x^{−5})) where s, t are the number of 4-cycles in G(S) and G(R) respectively. If we can show that s − t ≥ 2(k − 1)^{2} then by applying Taylor’s Theorem to exp(·) we will get

\frac{ρ(R, x)}{ρ(S, x)} ≤ 1 − \frac{2(k − 1)^{2}}{x^{4}} − \frac{16(k − 1)^{3}}{x^{5}} + (\frac{2(k − 1)^{2}}{x^{4}} + \frac{16(k − 1)^{3}}{x^{5}} )^{2}.  (9)

Since (2(k − 1)^{2}x^{−4} + 16(k − 1)^{3}x^{−5})^{2} ≤ (k − 1)^{3}x^{−5} for x ≥ 4(k − 1), the theorem is proved once we have (9).

It remains to show s−t ≥ 2(k−1)^{2}. Let v be a vertex in G(A) for some A ∈ 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}, …, v_{l} for some l ≥ k − 1. Let the degree of v_{i} in B_{v} be d_{i}, and relabel if necessary so that d_{i} ≥ d_{i+1} for each i. Call f_{v} the number of 4-cycles in G(A) which involve v. We have

f_{v} = ∑_{i=1}^{l} \binom{d_{i}}{2}.  (10)

Note that since G(A) is k-regular bipartite, we must have ∑_{i=1}^{l} d_{i} = k(k − 1) and d_{i} ≤ k for each i. With these restrictions it is easily calculated that f_{v} ≤ (k − 1)\binom{k}{2} by noting that \binom{a+1}{2} + \binom{b−1}{2} > \binom{a}{2} + \binom{b}{2} provided a ≥ 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 = \frac{1}{2}n(k − 1)\binom{k}{2} > 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 ≤ \frac{1}{2}n(k − 1)\binom{k}{2} − 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)\binom{k}{2} − (2k − 3) then we immediately have that t ≤ \frac{1}{2}n(k − 1)\binom{k}{2} − k(2k − 3) which is sufficient for k ≥ 2. Hence, (10) tells us the only remaining possibility is that l = k and d_{1} = d_{2} = … = d_{k−2} = k, d_{k−1} = k − a and d_{k} = a for some a ≤ 2. 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. ⊙

§6. Between the roots

We study the behaviour of the rook polynomial below its largest root.

Theorem 8. Let w ≈ 0.27846 satisfy w + log(w) + 1 = 0. Let β = 4(k − 1) and suppose λ_{n} < β is the largest root of ρ(R, x) for a rectangle R ∈ L(k, n). Then

(a) |ρ(R, x)| ≤ (β − x)^{n}w^{−ϕn} for all k < x < λ_{n}, where ϕ = w(β − k)/((w + 1)(β − x)).

(b) ρ(R, x) ≤ (x − k)^{n−2}(β − x)^{2} ≤ (x − k)^{n} whenever (β + kw)/(1 + w) ≤ x ≤ λ_{n}

(c) |ρ(R, x)| ≤ x^{n}w^{−φn} for all 0 < x ≤ k, where φ = kwx^{−1}/(w + 1).

(d) |ρ(R, x)| ≤ (k − x)^{n} for all x ≤ kw/(1 + w).

Proof: We prove only (a) and (b); the proofs of (c) and (d) being similar. Let {λ_{i}}_{i=1}^{n} be the roots of ρ(R, x), labelled in non-decreasing order. Suppose x is in the interval (k, λ_{n}) and choose a so that λ_{a} ≤ x < λ_{a+1}. We consider moving the λ_{i} in order to maximise r(x) = ∏ |x−λ_{i}|, while preserving ∑ λ_{i} = nk. First we move λ_{a+1}, λ_{a+2}, …, λ_{n} so that they coincide at (λ_{a+1} + λ_{a+2} + … + λ_{n})/(n − a), and move λ_{1}, λ_{2}, …, λ_{a} so they are all equal to (λ_{1} + λ_{2} + … + λ_{a})/a. The arithmetic/geometric mean inequality ensures that r(x) will not be decreased by this process. Next we move λ_{a+1}, λ_{a+2}, …, λ_{n} to β, and at the same time move the lower group of roots λ_{1}, λ_{2}, …, λ_{a} to α, where α = (nk − (n − a)β)/a. This further adjustment clearly does not decrease r(x). Now we have r(x, a) = (x − α)^{a}(β − x)^{n−a}. If we define θ by

θ = \frac{∂}{∂a} log(r) = log (\frac{x − α}{β − x}) − \frac{n(β − k)}{a(x − α)}

then

\frac{∂θ}{∂a} = −\frac{n^{2}(β − x)^{2}}{a^{3}(x − α)^{2}} ≤ 0.

From this we conclude that for x fixed, r has a single maximum when θ = 0 at

a = \frac{w(β − k)n}{(w + 1)(β − x)}.  (11)

Substituting (11) into r(x, a) = (x − α)^{a}(β − x)^{n−a} yields (a). Note that we can do better when x ≥ (β + kw)/(1 + w), meaning that the maximum (11) occurs above the greatest feasible value of a. In this case r(x, a) increases monotonically with a. By choice a ≤ n−1, and note that if a = n − 1 then ρ(R, x) is negative. Part (b) of the theorem follows. ⊙

Theorem 9. |ρ(R, x)| ≤ (x^{2} − 2kx + 2k^{2} − k)^{n/2} for all R ∈ L(k, n) and x ≥ 0.

Proof: Suppose ρ(R, x) = ∏(x − λ_{i}). A standard inequality of means gives

|ρ(R, x)|^{1/n} ≤ (\frac{1}{n} ∑(x − λ_{i})^{2})^{1/2} .  (12)

The required bound follows from (12) and knowledge of the first two moments, (6). ⊙ §7. The ‘large’ cases

We present two simple lemmas which will help identify maximising k × mk rectangles for large m and k.

Lemma 1. Let τ = \frac{3}{2}n and m ≥ 5. Then I_{τ}^{∞}(ρ(R, x)) ≤ \frac{13}{3}e^{−τ} (τ − k)^{n} for R ∈ L(k, n).

Proof: Suppose ρ(R, x) = ∏_{i}(x − λ_{i}). By the arithmetic/geometric mean inequality we have ρ(R, x) ≤ (\frac{1}{n} ∑(x − λ_{i}))^{n} = (x − k)^{n} provided x ≥ max\{λ_{i}\}. Hence

I_{τ}^{∞}(ρ(R, x)) ≤ ∫_{τ}^{∞} e^{−x}(x − k)^{n} dx = e^{−τ} ∑_{i=0}^{n} \frac{n!(τ − k)^{i}}{i!} ≤ e^{−τ} ∑_{i=0}^{n} n^{n−i}(τ − k)^{i}.

Since τ = \frac{3}{2}n > n + k we see immediately that,

I_{τ}^{∞}(ρ(R, x)) ≤ e^{−τ} (τ − k)^{n} ∑_{i=0}^{∞} (\frac{n}{τ − k} )^{i} = e^{−τ} (τ − k)^{n+1}/(τ − n − k).

Finally, (τ − k)/(τ − n − k) = 3 + 4/(m − 2) ≤ 13/3 for m ≥ 5. ⊙

Lemma 2. Suppose that R ∈ L(k, n) where n = mk. Define m′ = min{m, 6}. Then |I_{0}^{4k}(ρ(R, x))| ≤ 4ke^{(2−m′)k}(\frac{1}{2}m′k)^{n}.

Proof: It was proved in [7] that

|I_{0}^{4k}(ρ(R, x))| ≤ 2^{−n}e^{2k} ∫_{2k}^{6k} e^{−x}x^{n} dx.  (13)

Since \frac{d}{dx}(e^{−x}x^{n}) = e^{−x}x^{n−1}(n − x) we can bound the integrand in (13) by its value at x = m′k, giving

∫_{2k}^{6k} e^{−x}x^{n} dx ≤ 4ke^{−m′k}(m′k)^{n}.
⊙

In what follows we suppose S = S_{m,k} and R ∈ L(k, n) do not have isomorphic graphs. Then by combining Lemma 1, Lemma 2 and (1),

\begin{aligned}I_{4k}^{τ}(ρ(S, x)) & = I_{0}^{∞}(ρ(S, x)) − I_{0}^{4k}(ρ(S, x)) − I_{τ}^{∞}(ρ(S, x)) \\ & ≥ n! (\frac{m − 1}{m})^{n} − \frac{4k(\frac{1}{2}m′k)^{n}}{e^{(m′−2)k}} − \frac{13}{3}e^{−τ} (τ − k)^{n}. \end{aligned}  (14)

Now 2(k − 1)^{2}x^{−4} is a decreasing function of x for x > 0, so by Theorem 7,

I_{4k}^{∞}(ρ(S, x) − ρ(R, x)) ≥ I_{4k}^{τ}(ρ(S, x) − ρ(R, x)) ≥ (\frac{2(k − 1)^{2}}{τ^{4}} ) I_{4k}^{τ}(ρ(S, x)).  (15)

Also Lemma 2 tells us that

|I_{0}^{4k}(ρ(S, x) − ρ(R, x))| ≤ |I_{0}^{4k}(ρ(S, x))| + |I_{0}^{4k}(ρ(R, x))| ≤ \frac{8k(\frac{1}{2}m′k)^{n}}{e^{(m′−2)k}} .

Combining with (14) and (15) we see that if

n! (\frac{m − 1}{m})^{n} − \frac{4k(\frac{1}{2}m′k)^{n}}{e^{(m′−2)k}} − \frac{13}{3}e^{−τ} (τ − k)^{n} − \frac{4k(\frac{1}{2}m′k)^{n}τ^{4}}{e^{(m′−2)k}(k − 1)^{2}} > 0  (16)

then I_{4k}^{∞}(ρ(S, x) − ρ(R, x)) + I_{0}^{4k}(ρ(S, x) − ρ(R, x)) > 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 ≥ 10. It is a simple matter to establish that (16) holds for 5 ≤ m ≤ 10 and k = q_{m}. We use this as a basis for induction.

In the notation of [1] we use Γ and ψ to denote the gamma and digamma functions respectively. Note that Γ(n + 1) = n! and ψ(x) = \frac{d}{dx} log Γ(x). Suppose that we make the following definitions

\begin{matrix}f_{1} = Γ(n + 1) (\frac{m−1}{m})^{n} & f_{2} = 4k(\frac{1}{2}m′k)^{n}e^{(2−m′)k} \\ f_{3} = \frac{13}{3}e^{−τ} (τ − k)^{n} & f_{4} = 4k(\frac{1}{2}m′k)^{n}e^{(2−m′)k}τ^{4}(k − 1)^{−2} \end{matrix}

with the aim of showing that f_{1} dominates the inequality (16). 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 ≥ 5, provided k ≥ q_{m}. However, first we must show that (16) holds for k = 3 and m ≥ 10. To that end, we fix m′ = 6 and observe that

\frac{1}{kf_{1}} \frac{∂f_{1}}{∂m} = ψ(n + 1) + log (\frac{m − 1}{m}) + \frac{1}{m − 1} > log(k) + log(m − 1) + \frac{1}{m − 1}  (17)

because ψ(n + 1) > log n for n > 0. Meanwhile,

\frac{1}{kf_{4}} \frac{∂f_{4}}{∂m} = log(k) + log(3) + \frac{4}{n}

and log(m − 1) > log(3) + 1 for m ≥ 10 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 ≥ 10 because f_{4}/f_{2} = (3mk/2)^{4}(k − 1)^{−2} trivially increases with m. In addition,

\frac{1}{kf_{3}} \frac{∂f_{3}}{∂m} = log(k) + log(\frac{3}{2}m − 1) − \frac{1}{2} + \frac{2}{3m − 2}.  (18)

Now 2/(3m − 2) < 1/(m − 1) for positive m and log(\frac{3}{2}m − 1) − \frac{1}{2} < log(m − 1) for all m > (\sqrt{e} − 1)/(\sqrt{e} − 3/2) ≈ 4.362. Hence by (17) we see that log(f_{1}/f_{3}) increases with m in the required range. Since (16) holds when k = 3 and m = 10 we conclude that it must hold for k = 3 and m ≥ 10.

Next we fix m ≥ 5 and show that (16) holds for all k ≥ q_{m}, using the knowledge that it holds when k = q_{m}. We have,

\frac{1}{mf_{1}} \frac{∂f_{1}}{∂k} = ψ(n + 1) + log (\frac{m − 1}{m}) > log(k) + log(m − 1).

By comparison,

\frac{1}{mf_{4}} \frac{∂f_{4}}{∂k} = log(k) + log(\frac{1}{2}m′) + 1 + \frac{2k^{2} + k − 5}{mk(k − 1)} − \frac{m′}{m} .

Now (2k^{2} + k − 5)/(k^{2} − k) is a decreasing function for k ≥ (5 + \sqrt{10})/3 ≈ 2.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{∂}{∂k} log(f_{1}) > \frac{∂}{∂k} log(f_{4}) for m ≥ 5 and k ≥ 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 ≥ 2, so f_{1}/f_{2} must also increase with k in the required range. It remains to use the same approximation used on (18) to show that

\frac{1}{mf_{3}} \frac{∂f_{3}}{∂k} = log(k) + log(\frac{3}{2}m − 1) − \frac{1}{2} < log(k) + log(m − 1) < \frac{1}{mf_{1}} \frac{∂f_{1}}{∂k} .

We conclude that f_{1}/f_{2}, f_{1}/f_{3} and f_{1}/f_{4} are increasing functions of k, provided m ≥ 5 and k ≥ q_{m}. Therefore inequality (16) holds for all m ≥ 5 and k ≥ q_{m}. We are left with only finitely many cases to check; namely k = 3, 4, …, (q_{m} − 1) for m = 5, 6, 7, 8, 9. These cases will be checked in the final section.

§8. The ‘small’ cases

We turn our attention to the cases left unresolved by the preceding section, namely 3 ≤ k ≤ q_{m} − 1 for 5 ≤ m ≤ 9. Since ρ(S, x) ≥ 0 for λ_{S} ≤ x ≤ λ_{R} we see from Theorem 7 that

I_{λ_{S}}^{4k−4}(ρ(S, x)) ≥ I_{λ_{R}}^{4k−4}(ρ(R, x))

and hence

E(S) − E(R) ≥ I_{4k−4}^{∞}(ρ(S, x) − ρ(R, x)) − I_{0}^{λ_{R}}(ρ(R, x)) + I_{0}^{λ_{S}}(ρ(S, x)).  (19)

Notice that by Theorem 7,

I_{4k−4}^{∞}(ρ(S, x) − ρ(R, x)) ≥ I_{4k−4}^{∞}(ρ(S, x)(2(k − 1)^{2}x^{−4} + 15(k − 1)^{3}x^{−5})).  (20)

Now for specific values of m and k, the bound in (20) can be explicitly calculated, as can I_{0}^{λ_{S}}(ρ(S, x)), because we know that ρ(S, x) = (L_{k})^{m} where L_{k} is defined by (3). Hence the only term in (19) we need to work on is I_{0}^{λ_{R}}(ρ(R, x)). We use Theorem 8 and Theorem 9. Define the cutoffs and functions

\begin{matrix}c_{5} = 4k − 4, & f_{5} = e^{−x}(x − k)^{n−2}(c_{5} − x)^{2}, \\ c_{4} = \frac{c_{5} + kw}{1 + w} , & f_{4} = e^{−x}(c_{5} − x)^{n}w^{−(w/(w+1))n(c_{5}−k)/(c_{5}−x)}, \\ c_{3} = min\{3k, c_{4}\}, & f_{3} = e^{−x}(x^{2} − 2kx + 2k^{2} − k)^{n/2}, \\ c_{2} = k − 1, & f_{2} = e^{−x}x^{n}w^{−c_{1}n/x}, \\ c_{1} = \frac{kw}{1 + w} , & f_{1} = e^{−x}(k − x)^{n}. \end{matrix}

so that

I_{0}^{λ_{R}}(ρ(R, x)) ≤ ∑_{i=1}^{5} ∫_{c_{i−1}}^{c_{i}} f_{i} dx  (21)

where we assume c_{0} = 0. Note that f_{5} is positive between λ_{R} and c_{5}. We consider the last integral in (21) first. We have,

\frac{df_{5}}{dx} = e^{−x}(x − k)^{n−3}(c_{5} − x)(x^{2} − (n + k + c_{5})x + c_{5}(n + k − 2) + 2k).  (22)

Notice that the discriminant Δ = (n + k − c_{5})^{2} + 8(c_{5} − k) of the quadratic term in (22) satisfies (n+k −c_{5})^{2} < Δ < (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} = \frac{1}{2}(n + k + c_{5}) − \frac{1}{2}((n + k − c_{5})^{2} + 8(c_{5} − k))^{1/2}.

This certainly means that

∫_{c_{4}}^{c_{5}} f_{5} dx ≤ (c_{5} − c_{4})e^{−x_{0}}(x_{0} − k)^{n−2}(c_{5} − x_{0})^{2}.

We bound the other four integrals in (21) 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^{n}w^{c/l} where a, b, c and w are independent of x. Then

\frac{l^{2}}{f} \frac{d^{2}f}{dx^{2}} = (\frac{ca ln(w)}{l} + l + a − an)^{2} + (n − 1)a^{2} − 2al ≥ (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 ∈ [c_{2}, c_{3}]. We claim that in this interval, and for integers k ≥ 3, m ≥ 5 and n = mk it can easily be checked that n − 2(x − k) > \sqrt{n}. Then

\frac{d^{2}f_{3}}{dx^{2}} = \frac{f_{3}}{(x^{2} − 2kx + 2k^{2} − k)^{2}} ((n(x−k)−(x−k)^{2}−(k^{2}−k))^{2}+n((k^{2}−k)−(x−k)^{2})) (23)

which is clearly positive unless we assume (x−k)^{2} ≥ k^{2} −k ≥ 6. Since x−k ≥ c_{2} −k = −1 it follows that x > k and hence n(x − k) − (x − k)^{2} − (k^{2} − k) ≥ (n − 2(x − k))(x − k) > 0. But now

n(x − k) − (x − k)^{2} − (k^{2} − k) > \sqrt{n}(x − k) > 0

which means that (23) 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 (21) we can subdivide each interval into σ subintervals each of width δ_{i} = (c_{i} − c_{i−1})/σ, giving,

I_{0}^{λ_{R}}(ρ(R, x)) ≤ (c_{5} − c_{4})f_{5}(x_{0}) + ∑_{i=1}^{4} ∑_{j=1}^{σ} \frac{δ_{i}}{2} (f_{i}(c_{i−1} + (j − 1)δ_{i}) + f_{i}(c_{i−1} + jδ_{i})). (24)

Taking σ = 10 the bound in (24) was computed for m = 5, 6, 7, 8, 9 and k = 3, 4, …, q_{m}−1. Together with (20) this allowed confirmation that E(S) > E(R) in each of these cases, except when m = 5 and k ≥ 12. For this subcase (20) becomes too slow to compute for large k, but it is sufficient to use (24) as a substitute for Lemma 2 in the derivation of (16). Specifically, if B is the bound computed in (24) and

n!(4/5)^{n} − B − \frac{13}{3}e^{−τ} (τ − k)^{n} − \frac{Bτ^{4}}{(k − 1)^{2}} > 0  (25)

then E(S) > E(R). It can quickly be confirmed that (25) holds for k = 12, 13, …, 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.

Theorem 10. Let m ≥ 5, k ≥ 2 and n = mk be integers. If R ∈ L(k, n) is maximising then G(R) ≅ 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

( \begin{matrix}Z_{k} & J_{k} & J_{k} & ⋯ & J_{k} \\ J_{k} & Z_{k} & J_{k} & ⋯ & J_{k} \\ J_{k} & J_{k} & Z_{k} & ⋯ & J_{k} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ J_{k} & J_{k} & J_{k} & ⋯ & Z_{k} \end{matrix} )  (26)

where Z_{k}, J_{k} are k × k blocks of zeroes and ones respectively.

Corollary 2. For integers m ≥ 5, k ≥ 2 and n = mk

M_{k,n} = ∫_{0}^{∞} e^{−x}(L_{k}(x))^{m} dx.

Also note that [5] cites an inclusion-exclusion formula of Kaplansky for the permanent of (26). However, to find M_{k,n} it is just as easy to calculate the integral in Corollary 2.

In closing, we observe that it is quite possible that Theorem 10 can be extended to show that Conjecture 1 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 §4. 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 Conjecture 1 is bolstered by the observation that |L_{k}(x)| ≤ k!e^{x/2} for x ≥ 0 (c.f. inequality 22.14.12 of [1]) and hence

∫_{0}^{4k−4} e^{−x}ρ(S_{m,k}) dx ≤ (k!)^{m} ∫_{0}^{4k−4} e^{(m−2)x/2} dx ≤ \frac{2(k!)^{m}}{m − 2} e^{2k(m−2)}.  (27)

This means by (1) that for fixed m ≥ 3 and n = mk → ∞ the initial segment of the integral I(S_{m,k}) is asymptotically insignificant compared to E(S_{m,k}), because

\frac{2(k!)^{m}}{m − 2} e^{2k(m−2)}/(n!(1 − k/n)^{n}) = O(k^{(m−1)/2})(\frac{e^{2m−4}}{(m − 1)^{m}} )^{k} = o(1).

If I_{0}^{4k−4}(R) could be similarly handled for other R ∈ L(k, n) then Theorem 7 would suffice.

§9. References

[1] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions, Dover publications, New York, 1965.

[2] V. I. Bolshakov, The spectrum of the permanent on Λ_{n}^{k}, Proceedings of the All-Union Seminar on Discrete Mathematics and its Applications (Russian) ed. O. B. Lupanov, Moskov. Gos. Univ., Moscow, 1986, 65-73.

[3] L. M. Brègman, Some properties of nonnegative matrices and their permanents, Soviet Math. Dokl. 14:945-949 (1973).

[4] R. A. Brualdi, J. L. Goldwasser and T. S. Michael, Maximum permanents of matrices of zeroes and ones, J. Comb. Th. A 47:207-245 (1988).

[5] 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, Adv. in Appl. Math. 2:121-137 (1981).

[6] C. D. Godsil, Matchings and walks in graphs, J. Graph Th. 5:285-297 (1981).

[7] C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, J. Comb. Th. B 48:19-44 (1990).

[8] O. J. Heilmann and E. H. Lieb, Theory of monomer-dimer systems, Comm. Math. Physics 25:190-232 (1972).

[9] S. A. Joni and G.-C. Rota, A vector space analog of permutations with restricted position, J. Comb. Th. A 29:59-73 (1980).

[10] D. Merriell, The maximum permanent in Λ_{n}^{k}, Linear and Multilinear Algebra 9:81-91 (1980).

[11] H. Minc, Permanents, Encyclopedia Math. Appl., Addison-Wesley, Reading, Mass., 1978.

[12] H. Minc, Theory of permanents 1978-1981, Linear and Multilinear Algebra 12:227-263, (1983).

[13] A. Schrijver, Bounds on permanents, and the number of 1-factors and 1-factorizations of bipartite graphs, London Math. Soc. Lecture Note Ser. 82:107-134 (1983).

[14] I. M. Wanless, The Holens-–Doković Conjecture on permanents fails, (submitted for publication).

[15] I. M. Wanless, Maximising the permanent and complementary permanent of (0,1)- matrices with constant line sum, (submitted for publication).

[16] N. Zagaglia-Salvi, Permanents and determinants of circulant (0, 1)-matrices, Matematiche (Catania) 39:213-219 (1984).