ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let PiP_i denote the path graph with ii vertices, and let □\square denote the Cartesian product of graphs. For i≤ji\leq j with i,j∈Z>1i,j\in\mathbb{Z}_{>1}, consider Pi□PjP_i\square P_j. A graph has the complete maximal identity property if its maximal stable configuration is equivalent to the identity for every choice of sink.

Path-product conjecture. The only graphs Pi□PjP_i\square P_j with the complete maximal identity property are P2□PjP_2\square P_j when j≡1(mod3)j\equiv1\pmod{3}, together with P2□P2P_2\square P_2, which is K4K_4.

The conjecture was supported by a SageMath verification for 1<i≤j≤1001<i\leq j\leq100. The proposition establishing the listed P2□PjP_2\square P_j cases is proved in the paper, but the exclusion of all other path products remains open.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.