The following Question was posed here several years ago:
There are 25 students in a class who sit in five rows of five. Each week they sit in a different order.
After a number of weeks every student has sat next to every other student, next meaning side by side, one behind the other, or sitting diagonally together. What is the fewest number of weeks in which this can happen?
Several users were able to determine good explicit seating charts for this problem, eventually finding a solution in $5$ weeks. However, there is a sharp contrast between the ad hoc methods used in that Question and the more human-understandable methods used for the 16-student version posted at Puzzling SE (which can be done in $3$ weeks).
Extending the problem in the obvious way to $n^2$ students sitting in a $n\times n$ grid, there is a simple lower bound: every week there are a fixed number of "meetings", and we need $\binom{n^2}{2}$ in total. Indeed, that fixed number is $(2n-1)(2n-2)$, so the lower bound is about $\frac{1}{8}n^2$ weeks. The solutions for $n\leq 5$ as well as some related theory (see below) suggest that this lower bound might be close to the true answer.
Questions: How accurate is the simple bound? In particular, is there any (explicit or asymptotic) upper bound on the solution that improves on the one-meeting-each-week $O(n^4)$? Even for the $n=5$ case, can some "aesthetic" solution be found, in particular one that suggests heuristics for good constructions in general?
Further Context
When I encountered the problem, I realized that it was a lightly disguised form of the well-known graph covering problem:
- Let $H_n=P_n\boxtimes P_n$ be the graph on the $n^2$ desks that describes which students sit next to each other; i.e. so the inner desks have degree 8, the edge desks have degree 5, and the corner desks have degree 3. These are sometimes called king's graphs.
- Each week the desks are "labelled" by the students who sit in them, which we may think of as a copy of $H_n$ inside $K_{n^2}$, the complete graph on the set of students.
- The condition that all students sit next to each other in some week is therefore requiring that every edge is in at least one copy of $H_n$ corresponding to the seating arrangements.
We are therefore looking for the minimum number of copies of $H_n$ required to cover all edges in $K_{n^2}$. This is sometimes known as the covering problem for $H_n$, which I will denote $C(H_n, K_{n^2})$. A truly amazing result due to Caro and Yuster (citation) is that for large $N$, the analogous "simple bound" is exact(!) for every graph(!!) with $e$ edges and vertices whose degrees have no mutual common factor, i.e. $$ C(H, K_N) = \left\lceil\frac{N(N-1)}{2\|H\|}\right\rceil $$ (Indeed, their paper gives a stronger formula that handles degrees which do have a common factor, but $\gcd(H_n)=1$ so I've simplified it here.)
Unfortunately, but not too surprisingly due to its generality, this result isn't technically strong enough to solve the problem. "Large $N$" for them means "highly exponential" in the number of edges of $H$, but our $N$ is on the same order as the number of edges of $H_n$ (since $\|H_n\|\approx 4n^2$). In a followup paper (citation) with Noga Alon, they provide an explicit bound for this constant as well as an $O(n^{2.5})$ algorithm for "computing $C(H,G)$" by reducing to a maximum matching — but I haven't looked carefully to see if this reduction is assuming that large $N$.
Of course, since our problem involves specific well-structured graphs, I'm not discouraged yet. I do think it is noteworthy that the Caro–Yuster formula gives precisely the simple lower bound $\binom{n^2}{2}\big/\|H_n\|$. But I have a thoroughly unfounded suspicion that in this "$N\approx \|H\|$" regime, some log factors may be lurking.