SEMINAR: Groups and Combinatorics Seminar: Gordon Royle, 4pm May 10 in Weatherburn LT

Speaker: Gordon Royle (University of Western Australia)

Title: From Lehman Matrices To (Im)Perfect Graphs

Time and place: 4pm Friday 10 May 2019, Weatherburn LT

Abstract: A pair (A,B) of square 0/1 matrices is called a Lehman pair if AB^T = J + k I where J is the all-ones matrix, I is the identity matrix and k is a positive integer, and an individual square 0/1 matrix is called a Lehman matrix if it belongs to a Lehman pair. The study of such matrices arose independently in the work of Lehman on problems in operations research, and the work of Bridges and Ryser who viewed them as generalisations of certain combinatorial designs. A number of authors have given methods of constructing Lehman matrices, including several recursive constructions that generate larger Lehman matrices from smaller ones, but always with the same value of k. In joint work, Dillon Mayhew, Irene Pivotto and I discovered a curious construction that transforms certain Lehman matrices with k=1 into “Lehman-like” matrices with k=-1 (and vice versa). Although barely mentioned in the literature on Lehman matrices, solutions to the matrix equation AB^T = J - I are essentially equivalent to a class of graphs known as "partitionable graphs", which were the central object of study in the decades-long effort to prove Berge’s Strong Perfect Graph Conjecture by a direct characterisation of minimal imperfect graphs.

In this talk, I will introduce all the necessary background concepts, and describe how such an innocuous definition leads quite naturally to such disparate areas of combinatorics.