The first chapter of the book \"Graphs and their uses\" by Oystein Ore says that

Question

The first chapter of the book "Graphs and their uses" by Oystein Ore says that interval graphs can be used to resolve authorship disputes, but I couldn't find any details. How does this work? What is the algorithm?

From the text (Chapter 1.7):

Interval graphs have also been used to investigate the likely authorship of disputed pieces of writing, such as certain works of Plato. Various features of an authors prose style are studied for their appearance in several literary works. By drawing a graph in which the vertices correspond to these literary features and the edges correspond to pairs of them which occur together in the same work, we obtain a situation very similar to our archaeological example. As before, we can then investigate whether the resulting graph can be represented as an interval graph, and we can thereby attempt to arrange the works in chronological order. By doing this, it has sometimes been possible to relate the style of the disputed piece of writing to that of the author in question, and thereby to determine the likely authorship.

Explanation / Answer

I'll explain shortly the "archaeology example" your excerpt refers to. It seems that the authorship dispute problem is really no different from it, and any practical application would face similar problems as I will describe.

Around 1900, Flinders Petrie formulated a problem known as sequence dating while studying 800 types of pottery found in 900 Egyptian graves. To each artifact, we associate a time interval (unknown) during which it was used, and to each grave a time point (unknown) when its contents were interred. Then, the problem is to figure out the time relationships between the artifacts and the graves.

Now consider a graph G whose vertices correspond to distinct artifacts. There is an edge between two vertices if they were found in some common grave. Assuming each pair of artifacts whose usage intervals intersect are to be found together in some grave we have that G is an interval graph. Furthermore, an interval assignment for G is a candidate for the usage intervals of the artifacts. However, of course in practice, it might be that we have incomplete data so the assumptions do not hold, and in any case, we need additional techniques to choose the correct interval assignment.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.