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

Gal Beniamini, Asaf Etgar, Yael Kirkpatrick

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 el…