The ${\mathbb{F}}_2$-Rank and Size of Graphs

Abstract

We consider the extremal family of graphs of order $2^n$ in which no two vertices have identical neighbourhoods, yet the adjacency matrix has rank only $n$ over the field of two elements. A previous result from algebraic geometry shows that such graphs exist for all even $n$ and do not exist for odd $n$. In this paper we provide a new combinatorial proof for this result, offering greater insight to the structure of graphs with these properties. We introduce a new graph product closely related to the Kronecker product, followed by a construction for such graphs for any even $n$. Moreover, we show that this is an infinite family of strongly-regular quasi-random graphs whose signed adjacency matrices are symmetric Hadamard matrices. Conversely, we provide a combinatorial proof that for all odd $n$, no twin-free graphs of minimal ${\mathbb{F}}_2$-rank exist, and that the next best-possible rank $(n+1)$ is attainable, which is tight.

arXiv commentAdded comparison to the results of Godsil and Royle. We thank Sam Adriaensen for bringing them to our attention