The extremal length conjecture for tournaments and the cyclic tournament

Let [n]={1,,n}[n]=\{1,\ldots,n\}, let Tourn\mathrm{Tour}_n denote the tournaments on [n][n], and let (T,r)\ell(T,r) be the maximum word length of a rank-rr transformation generated by the arcs of TT. Define the tournament πn\pi_n on [n][n] by

E(πn):={(i,(i+1)modn):i[n]}{(i,j):j+1<i}.E(\pi_n):=\{(i,(i+1)\bmod n):i\in[n]\}\cup\{(i,j):j+1<i\}.

Write maxTour(n,r)\ell_{\max}^{\mathrm{Tour}}(n,r) and maxTour(n)\ell_{\max}^{\mathrm{Tour}}(n) for the corresponding maxima over tournaments and ranks.

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

(T,r)(πn,r)=maxTour(n,r),\ell(T,r)\leq\ell(\pi_n,r)=\ell_{\max}^{\mathrm{Tour}}(n,r),

with equality if and only if TπnT\cong\pi_n. Furthermore,

(πn)=maxTour(n)=n2+3n62,\ell(\pi_n)=\ell_{\max}^{\mathrm{Tour}}(n)=\frac{n^2+3n-6}{2},

which is achieved for α:=n (n1)  2 n\alpha:=n\ (n-1)\ \dots\ 2\ n.

The conjecture identifies πn\pi_n as the unique extremal tournament for these transformation-semigroup word lengths. The paper notes that πn\pi_n is known to have the minimum number of strong subtournaments among strong tournaments, but the stated extremal length claim itself is proposed as a conjecture.

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.