On the characterizations of ${\mathcal{D}}_k\backslash {\mathcal{D}}_{k-2}$

Abstract

The determinant of a tournament $T$, denoted by $\det (T)$, is defined as the determinant of the skew-adjacency matrix of $T$. It is well-known that $\det (T)$ is equal to $0$ if $n$ is odd, and $\det (T)$ is the square of an odd integer if $n$ is even. For a positive odd integer $k$, let ${\mathcal{D}}_k$ be the set of tournaments whose all subtournaments have determinant at most $k^2$. Former studies showed that for $k\in \{1,3,5\}$, a tournament $T\in {\mathcal{D}}_k\backslash {\mathcal{D}}_{k-2}$ ($T\in {\mathcal{D}}_1$ when $k=1$) if and only if $T$ is switching equivalent to a transitive blowup of $L_{k+1}$, where $L_{k+1}$ is a tournament of order $k+1$ with a specific structure. For $k\ge 7$, no characterization results are known. A natural problem is to characterize tournaments in ${\mathcal{D}}_k\backslash {\mathcal{D}}_{k-2}$ that can be switching equivalent to a transitive blowup of $L_{k+1}$ for $k\ge 7$. To address this problem and to further explore the structural properties of tournaments in ${\mathcal{D}}_k$, we introduce CR tournaments, strong CR tournaments, basic tournaments and $Z$-matrices, and investigate their properties. We use these properties to characterize those tournaments $T\in {\mathcal{D}}_k\backslash {\mathcal{D}}_{k-2}$ where $T$ contains a subtournament switching isomorphic to a basic strong CR tournament in ${\mathcal{D}}_k\backslash {\mathcal{D}}_{k-2}$. This result implies former characterizations of ${\mathcal{D}}_3\backslash {\mathcal{D}}_1$ and ${\mathcal{D}}_5\backslash {\mathcal{D}}_3$. Using $Z$-matrices, we also show that for even $n$, $L_n$ is a basic strong CR tournament, and thus solve the open problem posed in [Discrete Math. 349 (2) (2026) 114766].

arXiv comment38 pages, 1 figure