The extremal length conjecture for tournaments and the cyclic tournament

About 10 years old · traced to

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) mod n):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 ℓmax⁡Tour(n,r)\ell_{\max}^{\mathrm{Tour}}(n,r) and ℓmax⁡Tour(n)\ell_{\max}^{\mathrm{Tour}}(n) for the corresponding maxima over tournaments and ranks.

The extremal length conjecture. For every n≥3n\geq 3, r∈[n−1]r\in[n-1], and T∈TournT\in\mathrm{Tour}_n,

ℓ(T,r)≤ℓ(πn,r)=ℓmax⁡Tour(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)=ℓmax⁡Tour(n)=n2+3n−62,\ell(\pi_n)=\ell_{\max}^{\mathrm{Tour}}(n)=\frac{n^2+3n-6}{2},

which is achieved for α:=n (n−1) … 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.

References

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.