Some mathematical problems in seriation

Some mathematical aspects of seriation are studied in this paper. Certain conditions on an abundance or an incidence matrix have been given in the past which imply that there exists a permutation of its rows so that the resulting matrix is a Q matrix (in which case the original matrix is said to be a pre-Q). These types of results have applications to chronologically ordering archaeological provenances under certain circumstances. Unfortunately these conditions are deficient both theoretically and practically, in that for much archaeological data the conditions are not necessarily true yet the corresponding provenances do have chronological orderings. Here we are able to generalize these results in two ways. First we are able to establish necessary and sufficient conditions on the rows of a matrix for it to be pre-Q. These conditions are local in that they concern only certain triples and quadruples of the rows. Secondly, we are able to interpret seriation in terms of a ternary relation R on a set A and prove the results in this general context. In this form the theorem says that if only certain of the triples and quadruples are R-strings, then the whole set A is an R- string, and so has a linear order consistent with the ternary relation R. This would appear to generalize a theorem of P. C. Fishburn. Both aspects of the generalization mean that the results stated herein have a wider applicability than those given heretofore. Possibly more importantly than this is that they lead to numerical invariants, called the fixing number and the related linear rigidity, of such an R-string on A. The archaeological interpretation of these is given in the paper and data supplied which illustrates this point. Finally various other conditions on products and representations of relations are stated which imply that A is an R-ring. One of these generalizes and completes a theorem of D. G. Kendall.

Recommendations

Cited in

(5)

This page was built for publication: Some mathematical problems in seriation

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