The rank distribution of matrices representing graphs with a long induced path over the field of two elements
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912584921251840 |
|---|---|
| author | Safarji, Badriah O'Brien, Cian Quinlan, Rachel |
| author_facet | Safarji, Badriah O'Brien, Cian Quinlan, Rachel |
| contents | A square matrix $M$ represents a graph $Γ$ if its nonzero off-diagonal entries encode the adjacencies of $Γ$, subject to a fixed ordering of the vertices. Over the field of two elements, we investigate the distribution of ranks in the affine space consisting of all matrices representing a given $Γ$. In particular, we consider which graphs of order $n$ are represented by more matrices of rank $n-1$ than of rank $n$. This property reflects an exceptional feature of the space $M_n(\mathbb{F}_2)$ of all $n\times n$ matrices over $\mathbb{F}_2$, namely that its most frequently occurring rank is not $n$ but $n-1$. Our analysis focuses on the class of connected graphs with an induced path on all but one vertex. The main result is a characterisation of all such graphs that are represented by more matrices of rank $n-1$ than of rank $n$ over $\mathbb{F}_2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10332 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The rank distribution of matrices representing graphs with a long induced path over the field of two elements Safarji, Badriah O'Brien, Cian Quinlan, Rachel Combinatorics 05C50 (Primary), 15A03, 15B33 (Secondary) A square matrix $M$ represents a graph $Γ$ if its nonzero off-diagonal entries encode the adjacencies of $Γ$, subject to a fixed ordering of the vertices. Over the field of two elements, we investigate the distribution of ranks in the affine space consisting of all matrices representing a given $Γ$. In particular, we consider which graphs of order $n$ are represented by more matrices of rank $n-1$ than of rank $n$. This property reflects an exceptional feature of the space $M_n(\mathbb{F}_2)$ of all $n\times n$ matrices over $\mathbb{F}_2$, namely that its most frequently occurring rank is not $n$ but $n-1$. Our analysis focuses on the class of connected graphs with an induced path on all but one vertex. The main result is a characterisation of all such graphs that are represented by more matrices of rank $n-1$ than of rank $n$ over $\mathbb{F}_2$. |
| title | The rank distribution of matrices representing graphs with a long induced path over the field of two elements |
| topic | Combinatorics 05C50 (Primary), 15A03, 15B33 (Secondary) |
| url | https://arxiv.org/abs/2509.10332 |