# P2724: Largest expected cover time on the four by five grid

- ID: `P2724`
- Reference: `grid-cover-time-four-by-five`
- Page: https://theoremdb.org/statements/P2724
- Record maturity: Reviewed problem with recorded work

## Problem

For simple random walk on \(P_4\square P_5\), with the starting vertex counted as visited at time zero, determine the maximum expected cover time over all starting vertices and identify every maximizing symmetry orbit.

### Problem setup

- **Definition.** Cover time is the first time by which all twenty vertices have been visited.
- **Remark.** The answer for each starting orbit is an exact rational number.

### What counts as a solution

- Supply reduced rational expectations for every start orbit or exact linear-system certificates from which all values and the maximizing orbit can be checked.

## Status

For the maximum expected cover time \(C_{4,5}\), the certified interval is \(19\le C_{4,5}\le8534169769/5542680\); the exact maximum and its maximizing starting-vertex symmetry orbit remain unresolved. [2](#reference-2)

## Work

### Evidence for the current status

**Computation 1 (The maximum expected cover time lies in a certified rational interval).** For the maximum expected cover time \(C_{4,5}\), the certified interval is \(19\le C_{4,5}\le8534169769/5542680\); the exact maximum and its maximizing starting-vertex symmetry orbit remain unresolved.

Write \(C_{4,5}\) for the maximum expected cover time. The certified interval is
\[
\boxed{19\le C_{4,5}\le \frac{8{,}534{,}169{,}769}{5{,}542{,}680}}.
\]
The upper endpoint is approximately \(1539.7190\).

The grid has 20 vertices, 31 edges, and diameter 7. The commute-time identity and \(R_{\mathrm{eff}}(x,y)\le d(x,y)\) give \(\max_{x,y}E_xT_y\le 2\cdot31\cdot7=434\). Matthews's inequality then gives \(E_xT_{\mathrm{cov}}\le H_{19}\max_{u,v}E_uT_v\), where \(H_{19}=275295799/77597520\). Multiplication and reduction yield the displayed upper endpoint. A walk needs at least nineteen moves to visit the other nineteen vertices, which proves the lower endpoint.

The exact maximum and its maximizing symmetry orbit remain unresolved in this record. The six start orbits have representatives \((0,0),(0,1),(0,2),(1,0),(1,1),(1,2)\).

### Background and intake notes

Exact dynamic programming on the three by three grid exposes the counterintuitive ordering of starting positions.

- Original intake status: Novelty remains unverified. No primary-source status audit was completed for this exact grid.
- For each connected visited set, the expectations for all possible current vertices satisfy one coupled Dirichlet system.
- Solving each state independently drops transitions that remain inside the visited set and gives wrong values.
- A corner need not maximize cover time; on the three by three pipeline check, the center gives the largest expectation.

- Recorded example: On the three by three grid, corner, edge-midpoint, and center starts form the three symmetry classes.

### Open directions

- **Route 1** (supported): General cover-time theory certifies the interval, and the exact connected-set recurrence reduces the finite computation to 116,166 systems. [2](#reference-2) [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python rebuilds the graph and checks every integer and rational used in the interval proof.

### Computational notes

- Exact rational dynamic programming over 217 proper connected visited subsets of P_3 square P_3 gave 140803109038245/4517710919176 for a corner, 275264650510462/8470707973455 for an edge midpoint, and 3978748873082/119305746105 for the center. These are approximately 31.1669143, 32.4960619, and 33.3491806.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `grid-cover-time-four-by-five`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>A. K. Chandra, P. Raghavan, W. L. Ruzzo, and R. Smolensky, “The electrical resistance of a graph captures its commute and cover times”. Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 (1989), 574-586. DOI 10.1145/73007.73062. Proceedings of STOC 1989, 574-586 https://doi.org/10.1145/73007.73062
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Largest expected cover time on the four by five grid: Literature and finite-state audit. General cover-time theory certifies the interval, and the exact connected-set recurrence reduces the finite computation to 116,166 systems.
2. <a id="reference-2"></a>Peter Matthews, “Covering Problems for Markov Chains,” Annals of Probability 16(3) (1988), 1215-1228. DOI 10.1214/aop/1176991686. cover-time comparison theorem, Annals of Probability 16(3), pages 1215-1228 https://doi.org/10.1214/aop/1176991686
   - Also cited at Annals of Probability 16 (1988), 1215-1228
   - Also cited at Peter Matthews, Covering problems for Markov chains, Annals of Probability 16 (1988), 1215-1228, cover-time inequality; commute-time identity and effective-resistance bound as recorded in the literature-audit object
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Largest expected cover time on the four by five grid, this source proves the harmonic-factor comparison between cover time and maximal hitting time used in the packet's upper bound.
   - Source named by the research packet.