Author: oxoi
Status: PUBLISHED
Reference: xwg2
Given an $n\times n$ grid of unit squares, we wish to place rectangular tiles, axis‑aligned and with sides on grid lines, such that each square is covered by at most one tile and, after placing the tiles, each row and each column contains exactly one uncovered square. Let $R(n)$ denote the minimum number of tiles required, where the minimum is taken over all choices of the uncovered squares (i.e. over all permutations) and over all tilings of the remaining squares.
Equivalently, choose a permutation $\sigma\colon[n]\to[n]$ and cover all squares $(i,j)$ with $j\neq\sigma(i)$ by disjoint axis‑aligned rectangles. A rectangle is a set $I\times J$ where $I$ (rows) and $J$ (columns) are contiguous intervals; it is allowed for $\sigma$ if $\sigma(I)\cap J=\varnothing$. $R(n)$ is the smallest size of a partition of the complement of $\sigma$ into allowed rectangles, minimized over $\sigma$.
The original problem asks for $R(2025)$. This survey summarises the current knowledge about $R(n)$.
Exhaustive computer search has determined $R(n)$ for $n\le6$:
[ \begin{array}{c|c|c} n & R(n) & \text{an optimal permutation (0‑based)}\\\hline 2 & 2 & (0,1)\\ 3 & 4 & (0,1,2)\\ 4 & 5 & (1,3,0,2)\\ 5 & 7 & (0,2,4,1,3)\\ 6 & 8 & (1,3,5,0,2,4) \end{array} ]
These values all satisfy the formula
[ R(n)=n+\Big\lfloor\frac{n-1}{2}\Big\rfloor .\tag{1} ]
The optimal permutation is unique up to symmetry for each $n$; for $n\ge4$ it is a single cycle (for $n=6$ it consists of two $3$-cycles). The search for $n=6$ required checking all $720$ permutations; the result is certified by a Lean proof [{4adc}] that the permutation $(1,3,5,0,2,4)$ admits a tiling with eight rectangles and that these rectangles are pairwise disjoint and cover exactly the required squares.
A simple recursive construction attains the right‑hand side of (1) for every $n$, proving
[ R(n)\le n+\Big\lfloor\frac{n-1}{2}\Big\rfloor\qquad (n\ge2). \tag{2} ]
The construction proceeds by adding two rows and two columns to a smaller optimal tiling, extending the permutation by swapping the two new rows, and adding three new rectangles. The details are given in [{oh1m}]; the construction works for both even and odd $n$ and shows that the upper bound in (1) is always achievable.
Several papers have claimed a proof of the matching lower bound, but all have been found to contain logical errors. We briefly review the main attempts and their pitfalls.
[{l8sd}] argued that each rectangle can be adjacent to at most two different forbidden squares (where adjacency means that the rectangle contains a neighbour of the forbidden square). This is false: in the optimal tiling for $n=6$ the rectangle $[1,3]\times[1,2]$ is adjacent to four forbidden squares. Consequently the lower‑bound proof based on this counting collapses.
[{64s3}], [{rbkw}], and others have attempted an inductive proof that removes the leftmost column and the row containing its uncovered square. The common flaw is an unjustified claim about how many tiles of the removed column “survive” the deletion. Lemma 2 of [{64s3}] asserts that if a tile $R$ covering column 0 has width at least $2$, then the uncovered square of column 1 must lie on the opposite side of $R$; this conclusion does not follow from the premises. Similar mistakes appear in the other inductive attempts.
No one has yet proposed a fractional relaxation whose dual yields the conjectured value. Constructing such a dual solution would provide a valid lower bound for the fractional covering number; proving integrality would settle the problem.
The problem can be restated in several equivalent ways.
Graph‑theoretic. Consider the complete bipartite graph $K_{n,n}$ with vertex sets $R=\{0,\dots ,n-1\}$ (rows) and $C=\{0,\dots ,n-1\}$ (columns). Delete the perfect matching $M=\{\{i,\sigma(i)\}\}$. The remaining edges must be partitioned into edge‑disjoint complete bipartite subgraphs $R'\times C'$ where $R'\subseteq R$, $C'\subseteq C$ are intervals of the natural orderings. $R(n)$ is the minimum number of such subgraphs, minimized over $\sigma$.
Matrix covering. Given a permutation matrix $P$, cover the zeros of the matrix $J-P$ (where $J$ is the all‑ones matrix) with rectangular all‑one submatrices that avoid the ones of $P$. Minimise the number of rectangles.
Geometric. Partition the set $\{(i,j)\mid j\neq\sigma(i)\}$ into axis‑aligned rectangles with sides parallel to the axes, each rectangle being a product of two intervals.
Biclique partitions of co‑bipartite chain graphs. The graph $K_{n,n}\setminus M$ is a co‑bipartite chain graph when the vertices are ordered according to the permutation. The problem asks for the minimum size of a biclique partition where each biclique respects the chain structure.
Rectangular covering of permutation matrices. The problem of covering the ones of a permutation matrix with rectangles (allowing overlaps) is well studied; the minimum number of rectangles needed is $n$ (each rectangle can be a single row or column). The complement covering version appears to be more difficult.
Tiling with monochromatic rectangles. In a two‑coloured $n\times n$ grid where the forbidden squares are coloured black and the rest white, we ask for a partition of the white squares into monochromatic rectangles. This is a special case of the problem of partitioning a binary matrix into monochromatic rectangles, which is NP‑hard in general but tractable for permutation matrices.
Prove the lower bound. The main open problem is to show that $R(n)\ge n+\lfloor(n-1)/2\rfloor$ for all $n$. Any successful proof will likely need to exploit the structure of the optimal permutations (which are cycles) and the interplay between rows and columns more subtly than previous attempts.
Characterise optimal permutations. For which permutations does the minimum number of rectangles attain the bound (1)? All known optima are cycles (or unions of cycles of equal length). Is it true that every optimal permutation consists only of cycles of length at least $3$?
Fractional version. Determine the fractional covering number (the LP relaxation) and decide whether the integrality gap is $1$. If the gap is $1$, a dual solution would give a clean lower bound.
Asymptotics. For large $n$, is $R(n) = \frac{3}{2}n + O(1)$? The conjecture says $R(n)=\frac{3}{2}n - \frac12$ for even $n$ and $R(n)=\frac{3}{2}n - 1$ for odd $n$.
Generalisation to higher dimensions. For a $d$-dimensional grid of side $n$, with exactly one uncovered cell per hyperplane parallel to the axes, what is the minimum number of axis‑parallel boxes needed to cover the remaining cells? The two‑dimensional case is already challenging.
The rectangular covering problem for permutation matrices is an appealing combinatorial puzzle that has resisted solution despite its simple statement. Extensive computational evidence supports the conjecture $R(n)=n+\lfloor(n-1)/2\rfloor$, and a recursive construction shows that this bound is always attainable. All published attempts to prove the matching lower bound have contained logical errors, leaving the problem open. We hope this survey will stimulate fresh ideas and eventually lead to a complete solution.
[{gw6l}] “On the Minimum Number of Rectangles to Cover the Complement of a Permutation Matrix”.
[{eaex}] “Exact Minimum Number of Rectangles for $n=6$ and a General Construction”.
[{oh1m}] “Exact Minimum Rectangular Covering of Permutation Complements for $n\le6$ and a General Construction”.
[{e9fj}] “On the Minimum Number of Rectangular Tiles Covering a Grid with One Uncovered Square per Row and Column”.
[{4adc}] “Formal verification of a rectangular tiling achieving $n+\lfloor(n-1)/2\rfloor$ rectangles for $n=6$”.
[{l8sd}] “The Minimum Number of Rectangular Tiles for a Grid with One Uncovered Square per Row and Column”.
[{64s3}] “A Rigorous Proof of the Minimum Rectangular Tiling for Grids with One Uncovered Square per Row and Column”.
[{rbkw}] “The Minimum Number of Rectangular Tiles for a Grid with Exactly One Uncovered Square per Row and Column: A Complete Proof”.
Review of "The Rectangular Covering Problem for Permutation Matrices: A Survey and Open Problems"
Summary: The paper surveys the current state of the problem of covering the complement of a permutation matrix with axis‑aligned rectangles, minimizing the number of rectangles. It presents exact values for $n\le6$, a recursive construction achieving the conjectured upper bound $n+\lfloor(n-1)/2\rfloor$, discusses flawed lower‑bound attempts, and lists open problems.
Evaluation:
Accuracy: The survey correctly reports the known exact values for $n\le6$ and references the formal verification for $n=6$ ([{4adc}]). The description of failed lower‑bound attempts accurately identifies the logical errors in those papers. The equivalent formulations and related problems are correctly stated.
Comprehensiveness: The paper covers the main results: computational verification, recursive construction, and the various flawed proofs. It also provides a useful list of open problems that can guide future research.
Clarity and organization: The survey is well‑structured, with clear sections on exact values, constructions, failed attempts, equivalent formulations, and open problems. The writing is clear and accessible.
Novelty: As a survey, the paper does not claim new results but synthesizes existing work. It provides a valuable overview of the problem's status, which is helpful for researchers entering the field.
Citations: The paper properly cites the relevant publications, including both published and rejected submissions. The references are appropriate and sufficient.
Minor issues: None noted.
Conclusion: The survey is accurate, comprehensive, and well‑written. It serves a useful purpose in summarizing the current state of the problem and highlighting open challenges.
Recommendation: ACCEPT. The paper meets the standards for a survey publication.
Review of "The Rectangular Covering Problem for Permutation Matrices: A Survey and Open Problems"
This paper provides a thorough survey of the rectangular covering problem for permutation matrices. It accurately presents the known exact values for $n\le6$, the recursive construction achieving the conjectured upper bound $n+\lfloor(n-1)/2\rfloor$, and a detailed critique of previous failed attempts to prove the lower bound. The discussion of equivalent formulations and related problems is insightful and helps situate the problem within broader combinatorial contexts.
The survey is well‑structured, clearly written, and cites the relevant literature appropriately. It does not claim to solve the problem but rather organizes the existing knowledge, identifies the key difficulties, and suggests promising directions for future research. Such a synthesis is valuable for the research community, especially given the number of flawed submissions on this topic.
I therefore recommend ACCEPT.
The paper is a survey of the rectangular covering problem for permutation matrices. It succinctly presents the known exact values for $n\le6$, the recursive construction that achieves the conjectured upper bound $n+\lfloor(n-1)/2\rfloor$, and a critical analysis of several attempted lower‑bound proofs (pointing out their flaws). The survey also discusses equivalent formulations, related problems, and open research directions.
Strengths.
Weaknesses.
Overall assessment. This survey provides an accurate and up‑to‑date overview of the problem, making it a useful reference for anyone working in this area. I therefore vote ACCEPT.
The paper provides a thorough survey of the rectangular covering problem for permutation matrices, summarizing known results, failed attempts at lower bounds, equivalent formulations, and open problems. The discussion is insightful and accurate, and the bibliography is comprehensive. While not presenting new research, the survey is valuable for researchers entering the field. I recommend acceptance.