← All problems

The representation-number conjecture for larger toroidal grid graphs

1 year old · traced to

Let TGrm,n\text{TGr}_{m,n} be the toroidal grid graph formed from the Cartesian product of the cycle graphs CmC_m and CnC_n, with m,n≥3m,n\geq 3, and let R(G)\mathcal{R}(G) denote the representation number of a graph GG. Representation-number conjecture. If n,m≥3n,m\geq 3 and m+n≥8m+n\geq 8, then

R(TGrm,n)≥4.\mathcal{R}(\text{TGr}_{m,n})\geq 4.

The graphs TGr3,3\text{TGr}_{3,3} and TGr3,4\text{TGr}_{3,4} have known 3-representations, but no 3-representation is known for larger toroidal grid graphs; the conjecture predicts that all cases with m+n≥8m+n\geq 8 require representation number at least 44.

References
  1. Nawaf Shafi Alshammari, Sergey Kitaev and Artem Pyatkin, “On the representation number of grid graphs and cylindric grid graphs”, arXiv:2507.16469 (2025).

Progress summary

Refreshed
Open · progress reported

A submitted construction claims the conjecture is false in one five-by-three case, but this has not been independently checked.

Alshammari, Kitaev, and Pyatkin posed the conjecture in their 2025 paper: every toroidal grid graph with m,n≥3m,n\geq 3 and m+n≥8m+n\geq 8 has representation number at least 44.

Known results

  • Explicit 33-representations are known for TGr3,3\mathrm{TGr}_{3,3} and TGr3,4\mathrm{TGr}_{3,4}.
  • For larger toroidal grids, no 33-representation was known in the 2025 source.
  • TGr4,4\mathrm{TGr}_{4,4} is isomorphic to the 44-dimensional cube, which has a known 44-representation.

Community submission (unverified), November 7, 2026

A submitted proof argues that the conjecture is false at (m,n)=(3,5)(m,n)=(3,5), giving an explicit 4545-letter 33-uniform word representing C3□C5C_3\square C_5. If correct, this is a counterexample and refutes the universal conjecture; the submission is not independently verified.

Current status (as of November 2026): The conjecture remains unverified; an unverified submission claims a counterexample at (m,n)=(3,5)(m,n)=(3,5), while no independently confirmed refutation or proof is recorded.

Sources

Solutions 1

A 45-letter word refuting the toroidal-grid representation-number conjecture of Alshammari, Kitaev and Pyatkin (arXiv:2507.16469, Conjecture 1)See full solutionHide full solution

Result and scope. Alshammari-Kitaev-Pyatkin Conjecture 1: R(C_m □ C_n) ≥ 4 for m, n ≥ 3 and m + n ≥ 8. False at (3, 5): an explicit 45-letter 3-uniform word represents C_3 □ C_5, so its representation number is at most 3.

Complete proof: A 45-letter word refuting the toroidal-grid representation-number conjecture of Alshammari, Kitaev and Pyatkin (arXiv:2507.16469, Conjecture 1) · PDF.

The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.

This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.