Flinders Petrie, the travelling salesman problem, and the beginning of mathematical modeling in archaeology (Q1946020)

William Matthew Flinders Petrie (1853--1942) was the first one to employ mathematical methods in order to study archaelogical findings. As it turns out, Petrie introduced the concepts of \textit{Hamming metric}, and of \textit{seriation}, solving the travelling salesman problem (henceforth, simply TSP), exhibiting a mathematical model of the graveyard in Naqada (Egypt). What is surprising is that Petrie was only an amateur and not a proper mathematician. At any rate, the first problem Petrie faced was to fix the chronological distance between the various graves. For this purpose he employed the Hamming metric according to which the distance between two vectors is given by the number of different components in the same place. For example, given two vectors \(v = \{ x_1,\ldots,x_n\}\) and \(u = \{ y_1,\ldots,y_m\}\), and supposing that \(x_i = y_i\) for any \(1 \leq i \leq n,m\) except at \(j\) and \(k\) where \(v\) and \(u\) differ, then the distance between \(v\) and \(u\) is \(2\). Formally, \(\text{ dist}(v,u) = 2 \). In the case of Petrie, the vectors are ``graves'' and the components are the relative ``items of pottery''. So, the more pottery is in common, the closer are the graves in time. But this is not all. Petrie introduced also a matrix \(A\) of this form: \[ \begin{matrix} & B & P & F & C & N & W & D & R & L\\ g_1 & & & & & & & &\\ g_2 & & & & & & & &\\ g_3 & & & & & & & &\\ . & & & & & & & &\\ . & & & & & & & &\\ . & & & & & & & &\\ \end{matrix} \] The columns indicate what type of pottery is associated to the graves (represented in the rows, as \(g_1,g_2,\ldots\)). Then, one entry \(a_{ij} = 1\) iff the grave \(g_i\) presents pottery of type \(j\), \(0\) otherwise. For example, the grave B130 has the entries: \(a_{\mathrm{B}130, B}\), \(a_{\mathrm{B}130, F}\), \(a_{\mathrm{B}130, N}\); i.e.: \[ \begin{matrix} & B & P & F & C & N & W & D & R & L\\ \text{B}130 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ \end{matrix} \] This means that the grave B130 has pottery of type \(B\) (black-topped), \(F\) (fancy-formed), and \(N\) (incised black). For sake of precision, grave B130 contains the items \(B22a\), \(B25c\), \(B25f\), \(F14\), \(N34\) and \(N37\), where the characters following \(B, F, N\) represent a variation of the type in issue. However, the number of graves so represented is very high, rendering the TSP difficult to solve. The move of Petrie's is to cut off the graves with few items, solving the TSP for only the richest graves, extending the results with approximation to the complete findings. From the above it becomes clear that it is difficult to underestimate the mathematical meaning of an archaeologist engaged in graveyards.