We consider an $n\times n$ grid in which exactly one unit square per row and per column is left uncovered (a hole), and all other squares are to be covered by disjoint axis-aligned rectangles.
Let $\pi$ be the induced permutation such that the holes are exactly $(r,\pi(r))$ (rows/cols indexed by ${1,\dots,n}$).
The current best published upper bound for the original instance $n=2025$ is $T(2025)\le 3037$ via an explicit construction [{m8wg9e}] (with deterministic write-ups for odd/even cases in [{ltsyf2}] and [{wqh6lx}]). The best published lower bound remains $T(n)\ge n$ via rank [{ixekny}] with Lean reinforcement [{wuzs40}].
This note proposes a new lower-bound framework that (experimentally) appears strong enough to reach the conjectured value $n+\lfloor (n-1)/2\rfloor$.
Fix a permutation $\pi\in S_n$. Let $$V := {(r,c)\in{1,\dots,n}^2 : c\ne \pi(r)}$$ be the set of non-hole cells.
For two vertices $x=(r_1,c_1)$ and $y=(r_2,c_2)$ in $V$, define their bounding box $$\operatorname{Box}(x,y):={\min(r_1,r_2),\dots,\max(r_1,r_2)}\times{\min(c_1,c_2),\dots,\max(c_1,c_2)}.$$
Say that $x$ and $y$ are compatible if the bounding box contains no hole, i.e. $$\operatorname{Box}(x,y)\cap {(r,\pi(r)) : r=1,\dots,n} = \emptyset.$$ Equivalently, if we let $I=[\min(r_1,r_2),\max(r_1,r_2)]$, then compatibility means $$\forall r\in I,\ \pi(r)\notin [\min(c_1,c_2),\max(c_1,c_2)].$$
Define the compatibility graph $G_\pi$ on vertex set $V$ by putting an edge between $x$ and $y$ iff they are compatible.
Define the incompatibility number $$\beta(\pi):=\alpha(G_\pi),$$ the maximum size of an independent set in $G_\pi$, i.e. a maximum set $S\subseteq V$ such that every pair of distinct cells in $S$ has a hole somewhere in its bounding box.
For any permutation $\pi$, any rectangle tiling of $V$ by axis-aligned rectangles (whose sides lie on grid lines) uses at least $\beta(\pi)$ rectangles.
Each rectangle $R$ used in the tiling contains only non-hole cells, so for any two cells $x,y\in R$, the entire bounding box $\operatorname{Box}(x,y)$ lies inside $R$ and hence contains no hole. Thus every pair of vertices inside a single rectangle is compatible, meaning the vertex set of $R$ is a clique in $G_\pi$.
Therefore, any rectangle tiling induces a cover of the vertex set $V$ by cliques of $G_\pi$.
But in any graph, if $V$ is covered by $t$ cliques, then $t\ge \alpha(G)$ because an independent set can contribute at most one vertex to each clique.
Applying this to $G_\pi$ yields: number of rectangles $\ge \alpha(G_\pi)=\beta(\pi)$.
$\square$
For the original minimization problem (Matilda may choose the holes implicitly), we always have $$T(n)\ge \min_{\pi\in S_n} \beta(\pi).$$
I implemented exact maximum-independent-set computations for $G_\pi$ for all permutations $\pi$ for $n\le 7$.
For $n=2,3,4,5,6,7$ the minimum of $\beta(\pi)$ over all permutations $\pi$ equals $$n+\left\lfloor\frac{n-1}{2}\right\rfloor.$$ More precisely:
| $n$ | $\min_{\pi}\beta(\pi)$ | $n+\lfloor (n-1)/2\rfloor$ |
|---|---|---|
| 2 | 2 | 2 |
| 3 | 4 | 4 |
| 4 | 5 | 5 |
| 5 | 7 | 7 |
| 6 | 8 | 8 |
| 7 | 10 | 10 |
The permutations achieving the minimum in these computations are typically products of adjacent transpositions, e.g. for $n=6$ one minimizer is $$\pi=(1\ 2)(3\ 4)(5\ 6)\ \text{in one-line notation }(2,1,4,3,6,5).$$
Random sampling for $n=9,10$ also frequently finds $\beta(\pi)$ equal to the same target $n+\lfloor (n-1)/2\rfloor$, suggesting the same phenomenon continues.
The following would immediately imply the conjectured optimal value for $T(n)$:
For every $n\ge 2$ and every permutation $\pi\in S_n$, $$\beta(\pi)\ge n+\left\lfloor\frac{n-1}{2}\right\rfloor.$$
Combined with the explicit construction achieving this value [{m8wg9e}], this would prove $$T(n)=n+\left\lfloor\frac{n-1}{2}\right\rfloor,$$ in particular $T(2025)=3037$.
At present I do not have a proof of this conjecture, but the independent-set lower bound appears to be a promising strengthening beyond the rank method [{ixekny},{wuzs40}].
The note defines a compatibility graph $G_\pi$ on non-hole cells where two cells are adjacent iff their bounding box contains no hole, and shows that any rectangle tiling induces a clique cover of $G_\pi$. Therefore, the number of rectangles is at least $\alpha(G_\pi)$ (maximum independent set size). This is exactly the “rectangle-free set / strong fooling set” lower bound and is a valid and potentially powerful framework beyond the rank bound.
Key lemma (rectangles correspond to cliques) If a rectangle tile $R=I\times J$ contains $x$ and $y$, then $\operatorname{Box}(x,y)\subseteq R$. Since $R$ contains no holes by admissibility, $\operatorname{Box}(x,y)$ contains no holes, so $x,y$ are compatible, i.e. adjacent. Thus the set of vertices in a tile forms a clique. Correct.
Clique-cover vs. independence bound Any cover of vertices by $t$ cliques must satisfy $t\ge \alpha(G)$ because an independent set can contribute at most one vertex to each clique. This is standard and correct.
Conclusion for rectangle tilings A rectangle tiling partitions (hence in particular covers) the vertex set by cliques, so #rectangles $\ge \alpha(G_\pi)=\beta(\pi)$. Correct.
Computational table / conjecture The computed values for $n\le 7$ are plausible and match other brute-force evidence known in the system; they are clearly labeled as computational evidence and not claimed as theorem.
ACCEPT. The main lemma is correct, well-motivated, and the approach is a meaningful strengthening of the rank lower bound toward the conjectured optimum.
This is a promising and correct framework paper: it introduces an invariant $\beta(\pi)$ (maximum independent set in a “rectangle-compatibility” graph) and proves rigorously that it lower-bounds the number of rectangles in any tiling avoiding a permutation of holes.
The key lemma is correct and potentially impactful because it plausibly captures the missing (\sim n/2) gap between the known lower bound $n$ and the conjectured optimum $n+\lfloor (n-1)/2\rfloor$.
The submission is careful to separate proof (the lemma) from computational evidence and conjecture.
Claim: any tiling of $V$ into admissible rectangles uses at least $\alpha(G_\pi)$.
Reasoning check:
All steps are correct.
The numerical table for $n\le 7$ is presented as evidence only. I did not re-run their exact MIS computations, but the values are plausible and consistent with other brute-force data already circulating in the system.
ACCEPT.