Additive Quasi-isometry via rooted graph partitions and layering partition

Abstract

For a graph H, ⟨ H ⟩ denotes the class of all subdivisions of H and tw(H) denotes the treewidth of H. In this paper, we prove the following. For k≥ 1, R≥ 1, let G,H be two graphs such that strong isometric path complexities (Chakraborty et al. [\textsc{Disc. Math., 2026}]) of both G and ⟨ H ⟩ are at most k, and G admits an honest, ``nicely rooted'' R-bounded H-partition. Then, there is a graph F with tw(F)≤ tw(H) such that G admits a (1,33· R· k²)-quasi-isometry to F. Using results of Albrechtsen, Distel, and Georgakopoulos (2025), we also obtain that K_2,t-asymptotic minor-free graphs admit quasi-isometries with additive distortion to K_2,t-minor-free graphs. This answers an open question raised by the above authors. As part of our proof, we combine the graph-partition based method and the layering partition based method (Chepoi et al. [\textsc{Discrete Comput. Geom.} 2012]) to obtain additive quasi-isometry when both the source and all subdivisions of the target graph have bounded strong isometric path complexity.

Isometry Groups of Right Invariant Metrics in Geometric Quantum Complexity
Xiaobo Liu, Lei Zheng
arXiv17 Sep 2026PreprintarXiv licenceFull textGeometry & topology Quantum physics & quantum informationarXiv
The Haagerup property is not invariant under quasi‐isometry
Mathieu Carette, Kevin Whyte, Sylvain Arnt +2
Bulletin of the London Mathematical Society15 Oct 2026Peer-reviewedCC BY5 citedMathematical physicsOpenAlex
Commensurability and quasi-isometry classification for one vertex one loop tubular groups
Amy Tao
arXiv4 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theory Geometry & topologyarXiv
Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO
Richard Y. Zhang
arXiv29 Aug 2026PreprintarXiv licenceFull textOptimisation & control StatisticsarXiv
Rank-one Factored Gradient Descent without Restricted Isometry: Application to Quantum Pure State Tomography on Multi-Qubits
Takahiro Kajisa
arXiv26 Oct 2026PreprintCC BY 4.0Full textOptimisation & control Quantum physics & quantum informationarXiv

Cite

BibTeX RIS

BibTeX

@misc{chakraborty2026additive,
  title = {{Additive Quasi-isometry via rooted graph partitions and layering partition}},
  author = {Dibyayan Chakraborty and Yann Vaxès},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.36186},
  eprint = {2609.36186},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.36186},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Additive Quasi-isometry via rooted graph partitions and layering partition
AU  - Dibyayan Chakraborty
AU  - Yann Vaxès
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.36186
UR  - https://arxiv.org/abs/2609.36186
AB  - For a graph H, ⟨ H ⟩ denotes the class of all subdivisions of H and tw(H) denotes the treewidth of H. In this paper, we prove the following. For k≥ 1, R≥ 1, let G,H be two graphs such that strong isometric path complexities (Chakraborty et al. [\textsc{Disc. Math., 2026}]) of both G and ⟨ H ⟩ are at most k, and G admits an honest, ``nicely rooted'' R-bounded H-partition. Then, there is a graph F with tw(F)≤ tw(H) such that G admits a (1,33· R· k^2)-quasi-isometry to F. Using results of Albrechtsen, Distel, and Georgakopoulos (2025), we also obtain that K_2,t-asymptotic minor-free graphs admit quasi-isometries with additive distortion to K_2,t-minor-free graphs. This answers an open question raised by the above authors. As part of our proof, we combine the graph-partition based method and the layering partition based method (Chepoi et al. [\textsc{Discrete Comput. Geom.} 2012]) to obtain additive quasi-isometry when both the source and all subdivisions of the target graph have bounded strong isometric path complexity.
ER  -

Abstract

Related

Cite