A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915572195786752 |
|---|---|
| author | Chalermsook, Parinya Orgo, Ly Zarsav, Minoo |
| author_facet | Chalermsook, Parinya Orgo, Ly Zarsav, Minoo |
| contents | Ferrer dimension, along with the order dimension, is a standard dimensional concept for bipartite graphs. In this paper, we prove that a graph is of Ferrer dimension three (equivalent to the intersection bigraph of orthants and points in ${\mathbb R}^3$) if and only if it admits a biadjacency matrix representation that does not contain $Γ= \begin{bmatrix} * & 1 & * \\ 1 & 0 & 1 \\ 0 & 1 & * \end{bmatrix}$ and $Δ= \begin{bmatrix} 1 & * & * \\ 0 & 1 & * \\ 1 & 0 & 1 \end{bmatrix}$, where $*$ denotes zero or one entry. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_20744 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three Chalermsook, Parinya Orgo, Ly Zarsav, Minoo Combinatorics Data Structures and Algorithms Ferrer dimension, along with the order dimension, is a standard dimensional concept for bipartite graphs. In this paper, we prove that a graph is of Ferrer dimension three (equivalent to the intersection bigraph of orthants and points in ${\mathbb R}^3$) if and only if it admits a biadjacency matrix representation that does not contain $Γ= \begin{bmatrix} * & 1 & * \\ 1 & 0 & 1 \\ 0 & 1 & * \end{bmatrix}$ and $Δ= \begin{bmatrix} 1 & * & * \\ 0 & 1 & * \\ 1 & 0 & 1 \end{bmatrix}$, where $*$ denotes zero or one entry. |
| title | A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.20744 |