Thin Lehman matrices and their graphs

Jonathan Wang

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

Two square $0,1$ matrices $A,B$ are a pair of Lehman matrices if $AB^T = J+dI$, where $J$ is the matrix of all $1$s and $d$ is a positive integer. It is known that there are infinitely many such matrices when $d=1$, and these matrices are called thin Lehman matrices. An induced subgraph of the Johnson graph may be defined given any Lehman matrix, where the vertices of the graph correspond to rows of the matrix. These graphs are used to study thin Lehman matrices. We show that any connected component of such a graph determines the corresponding rows of the matrix up to permutations of the columns. We also provide a sharp bound on the maximum clique size of such graphs and give a complete classification of Lehman matrices whose graphs have at most two connected components. Some constraints on when a circulant matrix can be Lehman are also provided. Many general classes of thin Lehman matrices are constructed in the paper.

Détail

DOI : 10.37236/437

Classification : 05B20, 05C50
Mots-clés : thin Lehmann matrix, Johnson graph