scientific article; zbMATH DE number 3884197

From MaRDI portal
Publication:3218154





Let \(T_ n\) be a tournament with n vertices. A permutation \(x_ 1,x_ 2,...,x_ n\) of the vertices of \(T_ n\) gives rise to a sequence \((e_ 1,e_ 2,...,e_{n-2})\) of zeros and ones where (i) \(e_ i=0\) if \(x_ i\to x_{i+1}\) in \(T_ n\); \(e_ i=1\) if \(x_ i\leftarrow x_{i+1}\) in \(T_ n\). In the case where \(e_ i=1-e_{i-1}\) for \(i=2,3,...,n-1\), the path \(x_ 1,x_ 2,...,x_ n\) is called an antidirected Hamiltonian path. \textit{B. Grünbaum} [J. Comb. Theory, Ser. B 11, 249-257 (1971; Zbl 0198.293)] proved that, except for three special tournaments with 3, 5 and 7 vertices respectively, every tournament contains an antidirected Hamiltonian path. \textit{A. Thomason} [Paths and cycles in tournaments (to appear)] proved that if n is sufficiently large, for every tournament \(T_ n\) and every sequence \((e_ 1,e_ 2,...,e_{n-1})\) a path \(x_ 1,...,x_ n\) can be found satisfying (i). The author considers questions regarding the actual number of permutations of a given tournament which will satisfy a given sequence \(e_ 1,...,e_{n-1}\). The purpose of the paper, a continuation of previous work by the author, is to provide theorems and machinery regarding these numbers. He conjectures that these numbers belong to a matrix of rank n-2.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3218154)