{
  "id": "2410.07411",
  "version": "v1",
  "published": "2024-10-09T20:22:42.000Z",
  "updated": "2024-10-09T20:22:42.000Z",
  "title": "Isometric embeddings of resonance graphs as finite distributive lattices",
  "authors": [
    "Zhongyuan Che"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a plane bipartite graph and $\\mathcal{M}(G)$ be the set of all perfect matchings of $G$. The resonance graph $R(G)$ is a graph whose vertex set is $\\mathcal{M}(G)$, and two perfect matchings are adjacent in $R(G)$ if their symmetric difference is a cycle forming the periphery of a finite face of $G$. It is known that any connected resonance graph can be isometrically embedded as a finite distributive lattice into hypercubes. The isometric dimension of a connected $R(G)$, denoted by $\\mathrm{idim}(R(G))$, is the smallest dimension of a hypercube that $R(G)$ can be isometrically embedded into. Let $d$ be the number of finite faces of $G$ such that there are no forbidden edges on their peripheries. We show that any connected $R(G)$ has $\\mathrm{idim}(R(G)) \\ge d$ and provide characterizations on when the equality holds. Moreover, if a connected $R(G)$ has $\\mathrm{idim}(R(G)) = d$, then we design an algorithm to generate a binary coding of length $d$ for all perfect matchings of $G$ which induces an isometric embedding of $R(G)$ as a finite distributive lattice into a $d$-dimensional hypercube without generating $\\mathcal{M}(G)$. Our results provide answers for the fundamental cases of both open questions raised in [\\textit{SIAM J. Discrete Math.} {\\bf 22} (2008) 971--984.]",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-10-09T20:22:42.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "finite distributive lattice",
      "resonance graph",
      "isometric embedding",
      "perfect matchings",
      "finite face"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}