Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 52 min ago
PreprintCC BY 4.0arXiv

An Algebraic Matching Algorithm for the Genus of Grid Diagrams

  • Jun Wang
  • Shasha Yang
Open at sourcePDFDOICite

Abstract

Grid diagrams encode knots and links combinatorially through an (n,n) winding matrix W(G). A fundamental invariant of the grid diagram is its genus g(G), which records essential topological information about the underlying knot. We give an algebraic algorithm that computes g(G) directly from W(G). The method repurposes the Hungarian algorithm ,after a column normalization that makes the matrix non-negative, it applies row-column reductions and minimum-vertex-cover corrections until the zero entries admit a perfect matching, equivalently until the minimum marking number equals n. By Konig's theorem the resulting permutation defines a distinguished grid state, and g(G) is then read from this matrix via the classical grid homology formula (Ozsvath-Stipsicz-Szabo). The novelty of this paper is the algorithm and its strongly polynomial analysis; the underlying invariant is known grid-homology theory. We illustrate the method on the trefoil and additional examples, and discuss extensions to (m,n) matrices and grid-move navigation toward the knot genus g(K).

Related

  1. Constructing Lagrangian surfaces in all symplectic toric $4$-manifolds from multi-grid diagrams
    Shintaro Fushida-Hardy, Laura Wakelin
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  2. Length Bounds for MDS Algebraic Geometry Codes of Arbitrary Positive Genus
    Haojie Chen, Chuangqiang Hu, Guorui Ma
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  3. Homology of matching complexes of 3× n grid graphs
    Pratiksha Chauhan, Anchal Sharma, Samir Shukla
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  4. A New Algebraic Algorithm for LWE
    Luca Campa, Massimo Fumiani, Arnab Roy
    arXivPreprintCC BY-NC-SA 4.0Full textAlgebra & number theoryarXiv
  5. A Low-rank ADI Algorithm for the Numerical Solution of Large Discrete-time Non-symmetric Algebraic Riccati Equations
    Umair Zulfiqar
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv

Cite

BibTeXRIS
BibTeX
@misc{wang2026algebraic,
  title = {{An Algebraic Matching Algorithm for the Genus of Grid Diagrams}},
  author = {Jun Wang and Shasha Yang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.16514},
  eprint = {2610.16514},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.16514},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - An Algebraic Matching Algorithm for the Genus of Grid Diagrams
AU  - Jun Wang
AU  - Shasha Yang
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2610.16514
UR  - https://arxiv.org/abs/2610.16514
AB  - Grid diagrams encode knots and links combinatorially through an (n,n) winding matrix W(G). A fundamental invariant of the grid diagram is its genus g(G), which records essential topological information about the underlying knot. We give an algebraic algorithm that computes g(G) directly from W(G). The method repurposes the Hungarian algorithm ,after a column normalization that makes the matrix non-negative, it applies row-column reductions and minimum-vertex-cover corrections until the zero entries admit a perfect matching, equivalently until the minimum marking number equals n. By Konig's theorem the resulting permutation defines a distinguished grid state, and g(G) is then read from this matrix via the classical grid homology formula (Ozsvath-Stipsicz-Szabo). The novelty of this paper is the algorithm and its strongly polynomial analysis; the underlying invariant is known grid-homology theory. We illustrate the method on the trefoil and additional examples, and discuss extensions to (m,n) matrices and grid-move navigation toward the knot genus g(K).
ER  -