Low temporal repetition forces excess trace

Definitions and mathematical statement

Let $n,r$ be positive integers and put $t=\lceil n/r\rceil$. For each $s\in\{1,\ldots,t\}$, let $A_s=(a^{(s)}_{ij})$ be an $n\times n$ matrix with entries in $\{0,1\}$ satisfying \[ a^{(s)}_{ii}=1,\qquad a^{(s)}_{ij}a^{(s)}_{ji}=0\quad(i\ne j),\qquad \sum_{j=1}^n a^{(s)}_{ij}\geq r+1\quad(1\leq i\leq n). \] The second condition forbids simultaneous opposite off-diagonal entries within the same matrix; it does not compare different matrices. The matrices may be identical or distinct. Products and traces are taken over the ordinary integers, not using Boolean multiplication.

Must every such sequence satisfy \[ \operatorname{tr}(A_1A_2\cdots A_t)>n? \] The diagonal entries equal to one already contribute $n$ constant closed walks to the trace. Thus the proposed strict inequality asks for an additional closed walk $i_0,i_1,\ldots,i_t=i_0$ that changes vertex at least once and obeys $a^{(s)}_{i_{s-1},i_s}=1$ at every time $s$. Waiting at a vertex is allowed by the diagonal ones, and repeated vertices are permitted. This interpretation keeps the specified chronological order of the matrices, which cannot generally be rearranged. Parameter choices for which no matrix satisfies the row bounds impose no extra claim. The distinct-index qualification in the no-opposite-entry condition is necessary for consistency with the prescribed diagonal.

Short English statement

Do sufficiently many dense oriented adjacency matrices necessarily have a product whose trace exceeds the contribution of stationary walks?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001060 (AIM-COMBINATORICS-0185), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, The Caccetta-Haggkvist conjecture, item 6.17. Original workshop question underlying AIM-COMBINATORICS-0185. https://aimath.org/WWN/caccetta/caccetta.pdf.