The minimum-length conjecture for odd tournaments and circulant tournaments

Let [n]={1,,n}[n]=\{1,\ldots,n\}, let Tourn\mathrm{Tour}_n denote the tournaments on [n][n], and let κn\kappa_n be the circulant tournament. Write (T,r)\ell(T,r) for the maximum word length of a rank-rr transformation generated by the arcs of TT, and let minTour(n,r)\ell_{\min}^{\mathrm{Tour}}(n,r) denote the minimum of this quantity over tournaments in Tourn\mathrm{Tour}_n.

The minimum-length conjecture. For every odd n3n\geq 3, every r[n1]r\in[n-1], and every TTournT\in\mathrm{Tour}_n,

minTour(n,r)=(κn,r).\ell_{\min}^{\mathrm{Tour}}(n,r)=\ell(\kappa_n,r).

Furthermore,

minTour(n,2)=n+1\ell_{\min}^{\mathrm{Tour}}(n,2)=n+1

and

minTour(n,r)=n+r\ell_{\min}^{\mathrm{Tour}}(n,r)=n+r

for all 3rn+123\leq r\leq\frac{n+1}{2}.

This conjecture proposes that the circulant tournament gives the minimum possible rank-wise length for odd orders, and specifies the minimum explicitly for ranks up to (n+1)/2(n+1)/2. The source gives no resolution of the claim.

Sources & referencesView supporting material

Primary source

P. J. Cameron, A. Castillo-Ramirez, M. Gadouleau and J. D. Mitchell, “Lengths of words in transformation semigroups generated by digraphs”, arXiv:1602.00935 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.