UWA Logo What's On at UWA
   UWA HomeProspective Students  | Current Students  | Staff  | Alumni  | Visitors  | About  |     Search UWA    for      

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

* Login to add events... *
Today's date is Saturday, August 15, 2020
Groups and Combinatorics Seminar: Gordon Royle, 4pm May 10 in Weatherburn LT Other events...
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.
Contact Stephen Glasby <[email protected]>
Start Fri, 10 May 2019 16:00
End Fri, 10 May 2019 17:00
Submitted by Stephen Glasby <[email protected]>
Last Updated Tue, 07 May 2019 11:55
Included in the following Calendars:
Additional Information:
  • Locations of venues on the Crawley and Nedlands campuses are available via the Campus Maps website.
  • Download this event as: Text | iCalendar
  • Mail this event:

Top of Page
© 2001-2010  The University of Western Australia
Questions? Mail [email protected]