Outputs (2)

NP-completeness of the combinatorial distance matrix realisation problem (2025)
Presentation / Conference Contribution
Fairbairn, D., Mertzios, G., & Peyerimhoff, N. (2025, December). NP-completeness of the combinatorial distance matrix realisation problem. Presented at 14th International Symposium on Algorithms and Complexity (CIAC 2025), Rome, Italy

The k-CombDMR problem is that of determining whether an n×n distance matrix can be realised by n vertices in some undirected graph with n+k vertices. This problem has a simple solution in the case k=0. In this paper we show that this problem is polyn... Read More about NP-completeness of the combinatorial distance matrix realisation problem.

Trivalent expanders, $(Delta – Y)$-transformation, and hyperbolic surfaces (2019)
Journal Article
Ivrissimtzis, I., Peyerimhoff, N., & Vdovina, A. (2019). Trivalent expanders, $(Delta – Y)$-transformation, and hyperbolic surfaces. Groups, Geometry, and Dynamics, 13(3), 1103-1131. https://doi.org/10.4171/ggd/518

We construct a new family of trivalent expanders tessellating hyperbolic surfaces with large isometry groups. These graphs are obtained from a family of Cayley graphs of nilpotent groups via (Delta–Y)-transformations. We study combinatorial, topologi... Read More about Trivalent expanders, $(Delta – Y)$-transformation, and hyperbolic surfaces.