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

arXiv2206.11625MaRDI QIDQ6402948FDOQ6402948

Authors: Asaf Etgar, Yael Kirkpatrick 

Publication date: 23 June 2022

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.

This page was built for publication: The $\mathbb{F}_2$-Rank and Size of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402948)