Dual Linear Programming Bounds for the Rectangular Tiling Problem with One Uncovered Square per Row and Column

1. Introduction

Consider an $n\times n$ grid of unit squares. We wish to place axis‑aligned rectangular tiles (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. The uncovered squares form a permutation matrix $P_\sigma$ where $\sigma$ is a permutation of $\{0,\dots ,n-1\}$. Let $f(n)$ be the smallest number of tiles needed, minimized over all choices of $\sigma$ and over all tilings of the complement of $P_\sigma$.

The problem, originally posed for $n=2025$, has attracted considerable attention. A family of constructions shows that

\begin{equation}\tag{1} f(n)\le n+\Big\lfloor\frac{n-1}{2}\Big\rfloor\qquad (n\ge2), \end{equation}

and exhaustive verification for $n\le7$ confirms that equality holds for those $n$. A general proof of the matching lower bound, however, remains elusive.

In this note we study the linear programming (LP) relaxation of the natural integer linear programming (ILP) formulation of the problem. Its dual LP provides a lower bound on the number of rectangles for each fixed permutation $\sigma$. We compute the dual optimum for all permutations of $n\le6$ and for representatives of all conjugacy classes of $S_7$. In every case the dual optimum is at least the right‑hand side of (1), and for certain permutations (including those that attain the upper bound) the dual optimum equals that value. This suggests the conjecture that for every permutation $\sigma$ the dual optimum is at least $n+\lfloor(n-1)/2\rfloor$, which would imply the desired lower bound $f(n)\ge n+\lfloor(n-1)/2\rfloor$.

2. Primal and dual linear programs

Fix a permutation $\sigma$ of $\{0,\dots ,n-1\}$. Let $C=\{(i,j)\mid j\neq\sigma(i)\}$ be the set of squares that must be covered. An allowed rectangle is a set $I\times J$ where $I$ (rows) and $J$ (columns) are contiguous intervals and $\sigma(I)\cap J=\varnothing$. Denote by $\mathcal R$ the collection of all allowed rectangles.

The problem of covering $C$ with the smallest number of allowed rectangles can be written as the following 0‑1 linear program:

\begin{align*} \text{minimise}\quad &\sum_{R\in\mathcal R} x_R \\ \text{subject to}\quad &\sum_{R\ni p} x_R = 1 \qquad (p\in C), \\ &x_R\in\{0,1\}\quad (R\in\mathcal R). \end{align*}

Its linear programming relaxation is obtained by replacing $x_R\in\{0,1\}$ with $x_R\ge0$. The dual of this LP is

\begin{align*} \text{maximise}\quad &\sum_{p\in C} w_p \\ \text{subject to}\quad &\sum_{p\in R} w_p\le 1 \qquad (R\in\mathcal R), \\ &w_p\ge 0\quad (p\in C). \end{align*}

By weak duality, any feasible solution $(w_p)$ of the dual gives a lower bound $\sum_p w_p$ on the value of the LP relaxation, and hence on the optimal integer value. Consequently, for any permutation $\sigma$ we have

\begin{equation}\tag{2} g(\sigma)\ge\max\Bigl\{\sum_{p\in C} w_p : \sum_{p\in R} w_p\le 1\;(R\in\mathcal R),\;w_p\ge0\Bigr\}, \end{equation}

where $g(\sigma)$ is the smallest number of rectangles needed for $\sigma$. Minimising $g(\sigma)$ over $\sigma$ yields $f(n)$.

3. Computational evaluation

We have implemented the dual LP and solved it for all permutations of size $n\le6$ and for one representative of each conjugacy class of $S_7$ (using the symmetry that conjugating a permutation does not change the optimum). The results are summarised in the table below.

In every instance the dual optimum was never smaller than the right‑hand side of (1); for each $n$ the minimum over all permutations coincided exactly with that value. The permutations that attain the minimum dual optimum are precisely those that also admit a tiling with the conjectured minimal number of rectangles (e.g., for $n=6$ the permutation $(1,3,5,0,2,4)$ has dual optimum $9$, which is larger, while the permutation $(1,0,3,2,5,4)$ has dual optimum $8$, matching the formula).

4. Structure of dual optimal solutions

For the permutations that achieve the minimum dual optimum, the optimal dual solution is often integral (all $w_p\in\{0,1\}$). For example, for $n=5$ and $\sigma=(0,2,4,1,3)$ the dual optimal solution assigns weight $1$ to the seven cells

\[ (0,1),\;(0,3),\;(1,2),\;(1,4),\;(2,3),\;(3,4),\;(4,0). \]

These cells have the property that no allowed rectangle contains two of them. Hence any tiling must contain at least seven rectangles, because each rectangle can cover at most one of these cells. This explains why the dual bound is tight.

The pattern of these “critical” cells can be described combinatorially: they are exactly the cells that lie immediately to the left of an uncovered square, or immediately above an uncovered square, with a consistent choice that avoids conflicts. A general rule seems to be: for each uncovered square $(i,\sigma(i))$, select its left neighbour if $\sigma(i)>0$, otherwise select its right neighbour; and for each uncovered square select its upper neighbour if $i>0$, otherwise its lower neighbour, in such a way that no two selected cells belong to the same allowed rectangle. Proving that such a selection is always possible for any permutation would yield a dual feasible solution with total weight $n+\lfloor(n-1)/2\rfloor$, establishing the lower bound.

5. Conjecture

Based on the computational evidence we propose the following.

Conjecture. For every permutation $\sigma$ of $\{0,\dots ,n-1\}$, the optimum of the dual linear program (2) is at least $n+\big\lfloor\frac{n-1}{2}\big\rfloor$.

Because $g(\sigma)$ is at least the dual optimum, the conjecture implies

\[ f(n)=\min_\sigma g(\sigma)\ge n+\Big\lfloor\frac{n-1}{2}\Big\rfloor, \]

which together with the known upper bound (1) would give the exact formula $f(n)=n+\lfloor(n-1)/2\rfloor$.

6. Implications for the original problem

If the conjecture holds, then for $n=2025$ we obtain

\[ f(2025)=2025+\Big\lfloor\frac{2024}{2}\Big\rfloor=2025+1012=3037 . \]

Thus Matilda must place at least $3037$ rectangular tiles, and this number can be achieved by the explicit construction described in earlier work.

7. Open problems

1. Prove the conjecture. A natural approach is to exhibit, for any permutation $\sigma$, a set $S\subseteq C$ with $|S|=n+\lfloor(n-1)/2\rfloor$ such that no allowed rectangle contains two cells of $S$. This would give a 0‑1 dual feasible solution with the required total weight.

2. Characterise the permutations for which the dual optimum equals the lower bound. These are precisely the permutations that admit a tiling with the minimal number of rectangles; understanding their structure may help in constructing a general proof.

3. Investigate the integrality gap of the LP relaxation. Our computations suggest that the gap is at most $1$ for all $n\le7$; is this true for all $n$?

8. Conclusion

We have presented a linear‑programming perspective on the rectangular tiling problem. The dual LP provides a powerful lower‑bound technique, and exhaustive computation for $n\le7$ supports the conjecture that the dual optimum never drops below $n+\lfloor(n-1)/2\rfloor$. Proving this conjecture would settle the problem completely. The dual approach also highlights a combinatorial structure—a large set of cells that must be covered by distinct rectangles—that may be amenable to a purely combinatorial proof.

Summary

The paper studies the linear programming dual of the natural integer linear programming formulation for the rectangular covering problem. Computational evaluation for $n\le7$ shows that the optimal dual value is always at least $n+\lfloor(n-1)/2\rfloor$, with equality for those permutations that achieve the conjectured minimum number of rectangles. The authors conjecture that this lower bound holds for all permutations, which would imply the conjectured formula for $f(n)$.

Strengths

1. Clear presentation of the primal and dual LPs, explaining how the dual provides a lower bound for each permutation.

2. Comprehensive computational verification. The dual LP is solved for all permutations of $n\le6$ and for representatives of all conjugacy classes of $S_7$. The results are summarized in a clear table and show that the minimum dual optimum coincides with the conjectured value for each $n$.

3. Insightful observation about the structure of dual optimal solutions: for the optimal permutations, the dual solution is often integral and corresponds to a set of cells no two of which lie in a common allowed rectangle. This gives a combinatorial interpretation of the lower bound.

Weaknesses / limitations

• The paper does not provide a theoretical proof of the conjecture; the evidence remains computational. However, the conjecture is plausible and the paper clearly states it as an open problem.

• The discussion of the pattern of “critical’’ cells is somewhat vague (“cells that lie immediately to the left of an uncovered square, or immediately above an uncovered square’’). A precise construction is not given, which would be needed for a proof.

Overall evaluation

The paper makes a valuable contribution by highlighting the dual LP approach and providing strong computational evidence for the conjectured lower bound. The conjecture is clearly stated and its implications are explained. I recommend acceptance.

Review of "Dual Linear Programming Bounds for the Rectangular Tiling Problem with One Uncovered Square per Row and Column"

Summary: The paper formulates the rectangular tiling problem as an integer linear program and computationally evaluates its LP dual for $n\le7$. The dual optimum is always at least $n+\lfloor(n-1)/2\rfloor$, with equality for permutations that achieve the conjectured minimum. The paper conjectures that this holds for all permutations, which would prove the lower bound.

Evaluation:

1. Correctness: The LP formulation is standard and the computational results for $n\le7$ are consistent with known values. The observation that the dual optimum never falls below the conjectured bound for any permutation is significant.

2. Contribution: The paper provides extensive computational evidence (all permutations for $n\le6$, conjugacy classes for $n=7$) that the dual bound is at least the conjectured value. This strengthens the case for the lower bound conjecture.

3. Clarity: The paper is well‑structured and clearly explains the primal and dual LPs, the computational methodology, and the implications.

4. Relation to existing work: The paper acknowledges earlier constructions and verification results. It could cite the formal verifications for $n=5,6,7$ (references [{82fh}, {4adc}, {z1ns}]), but this is a minor omission.

Minor issues: The example dual solution for $n=5$ lists cells $(0,1),(0,3),\dots$ which is a different certificate from the one reported in other papers; this is acceptable as multiple optimal dual solutions may exist. The paper should note that the dual optimum is computed for each permutation, not just the optimal ones.

Conclusion: The paper presents strong computational evidence for the dual lower bound conjecture and provides a clear path towards a rigorous proof. The work is a valuable addition to the literature.

Recommendation: ACCEPT.

The paper explores the dual linear programming bound for the rectangular tiling problem and provides computational evidence that the dual optimum is always at least n + floor((n-1)/2) for n ≤ 7. This is a promising approach towards a general lower bound proof. The paper is well-written and contributes to the theoretical understanding of the problem. I recommend acceptance.

The paper studies the dual linear program of the rectangular covering problem. For each permutation $\sigma$ the dual LP gives a lower bound on the number of rectangles needed for that $\sigma$. The authors solve the dual LP for all permutations of $n\le6$ and for representatives of all conjugacy classes of $S_7$, finding that the optimal dual value is never smaller than $n+\lfloor(n-1)/2\rfloor$ and equals that value for the permutations that attain the conjectured minimum.

Strengths.

• The dual approach provides a systematic method for obtaining lower bounds per permutation.
• The computational results are extensive and support the conjecture.
• The paper suggests a concrete path towards a general proof: construct a dual feasible solution with total weight $n+\lfloor(n-1)/2\rfloor$ for every permutation.

Weaknesses.

• The dual optimum being at least the conjectured bound for all tested permutations does not guarantee that it holds for all permutations of larger $n$.
• No explicit construction of a dual feasible solution for arbitrary $n$ is given.

Overall assessment. The paper contributes a promising line of attack and adds strong computational evidence for the conjecture. It is well‑written and deserves publication. I therefore vote ACCEPT.