Rank distributions of graphs over the field of two elements

Abstract

A square matrix $M$ represents a graph $\Gamma$ if its nonzero off-diagonal entries encode the adjacencies of $\Gamma$ according to a fixed vertex ordering. Over the field of two elements, we study the distribution of ranks within the affine space of all matrices representing a particular graph. The motivating question is which graphs of order $n$ are represented by more matrices of rank $n-1$ than of rank $n$. This reflects the fact that the most frequently occurring rank is not $n$ but $n-1$ in the space of all $\mathfrak{n} \times \mathfrak{n}$ matrices over $\mathbb{F}_2$, a property which is exceptional to $\mathbb{F}_2$. This thesis focuses on connected graphs that have a path or cycle as a subgraph induced on all but one vertex (called the extra vertex).

The path graph $\mathrm{P}_{\mathrm{n}}$ serves as the starting point of this study. The path graph is fundamental in the related and widely studied minimum rank problem, and provides a foundation for our later analysis of the set $\mathcal{G}^{\mathrm{P}}$ of graphs containing an induced path on all but one vertex. A main result is a characterisation of all such graphs that are represented by more matrices of rank $n-1$ than rank $n$ over $\mathbb{F}_2$. This is achieved by first examining the vectors in the nullspace of each matrix representing $P_n$. An expression for the difference $\alpha(\Gamma)$ between rank $n-1$ and rank $n$ representations of a given graph $\Gamma \in \mathcal{G}^{\mathrm{P}}$ is determined in terms of these nullspace vectors. A recurrence is then established, expressing $\alpha(\Gamma)$ in terms of $\alpha$ for graphs in $\mathcal{G}^{\mathrm{P}}$ for which the extra vertex has lower degree than in $\Gamma$. We classify all $\Gamma \in \mathcal{G}^{\mathrm{P}}$ satisfying $\alpha(\Gamma)<0$ by first classifying those for which the extra vertex has degree 1, then using that to simplify and classify the degree 2 case, and continuing like this until it is shown that no such graphs exist for degree $\geqslant 6$.

We then turn to the analogous problem for the cycle graph. We show that half of all $\mathbb{F}_2$-matrices representing $C_n$ have rank $n-1$, approximately one-third have rank $n$, and approximately one-sixth have rank $n-2$. We then investigate the set of graphs containing an induced cycle on all but one vertex, denoted by $\mathcal{G}^{\mathrm{C}}$. Our analysis reveals essential structural contrasts between the classes $\mathcal{G}^{\mathrm{P}}$ and $\mathcal{G}^{\mathrm{C}}$ : while the degree of the extra vertex is bounded in the path case, it can be arbitrarily large in the cycle case. An infinite family of graphs called alternating wheel graphs demonstrate this contrast, as there exists an alternating wheel graph $\Gamma \in \mathcal{G}^{\mathrm{C}}$ with an extra vertex of any even degree $\mathrm{d} \geqslant 4$ satisfying $\alpha(\Gamma)<0$.