On the extremal values of the cyclic continuants of Motzkin and Straus

Abstract

In a 1983 paper, G. Ramharter asks what are the extremal arrangements for the cyclic analogues of the regular and semi-regular continuants first introduced by T.S. Motzkin and E.G. Straus in 1956. In this paper we answer this question by showing that for each set $A$ consisting of positive integers $1<a_1<a_2<\cdots <a_k$ and a $k$-term partition $P:n_1+n_2+\cdots +n_k=n$, there exists a unique (up to reversal) cyclic word $x$ which maximizes (resp. minimizes) the regular cyclic continuant $K^{\circlearrowright }(\cdot )$ amongst all cyclic words over $A$ with Parikh vector $(n_1,n_2,\dots ,n_k)$. We also show that the same is true for the minimizing arrangement for the semi-regular cyclic continuant ${\dot{K}}^{\circlearrowright }(\cdot )$. As in the non-cyclic case, the main difficulty is to find the maximizing arrangement for the semi-regular continuant, which is not unique in general and may depend on the integers $a_1,\dots ,a_k$ and not just on their relative order. We show that if a cyclic word $x$ maximizes ${\dot{K}}^{\circlearrowright }(\cdot )$ amongst all permutations of $x$, then it verifies a strong combinatorial condition which we call the singular property. We develop an algorithm for constructing all singular cyclic words having a prescribed Parikh vector.

Preliminary version, 21 pages

References in corpus (1)

• Extremal values of semi-regular continuants and codings of interval exchange transformations