Abstract: Robinson matrices are structured matrices, introduced in the 1950’s by W.S. Robinson, and motivated by their application to archaeology for the chronological dating of Egyptian graves. A symmetric matrix is said to be Robinsonian if its rows and columns can be simultaneously reordered in such a way that the entries are monotone nondecreasing in the rows and columns when moving toward the main diagonal. Robinsonian matrices can be seen as a matrix analog of unit interval graphs, which are precisely the graphs having a Robinsonian adjacency matrix. We will discuss several aspects of Robinsonian matrices: links to unit interval graphs; new efficient combinatorial recognition algorithm based on Similarity-First Search, a natural extension to weighted graphs of Lex-BFS; structural characterisation by minimal forbidden substructures; and application to tractable instances of the Quadratic Assignment Problem.

[Slides]

Abstract: We survey old and new results bounding the Shannon capacity of a graph (by Lovasz, Haemers, Zuiddam, Bukh & Cox and others), and consider topological observations and questions emerging from them.

[Slides]