2025
The Lamplighter Groups and Thompson’s Group F have Infinite Weak-Cop Number
Geometrae Dedicata, 2025 Anders Cornect, Eduardo Martinez-Pedroza
The weak-cop number of a graph, introduced by Lee et al (2023), is a quasi-isometric invariant of graphs and hence of finitely generated groups via their Cayley graphs. While for any \(m \in \mathbb{Z}_+ \cup \{\infty\} \) there exist graphs with weak-cop number \(m\), it is an open question whether there exists finitely generated groups whose weak-cop number is different than \(1\) and \(\infty\). We prove that wreath products of nontrivial groups by infinite groups have infinite weak-cop number. We also prove that Thompson’s group \(F\) has infinite weak-cop number. The results are proved by defining two new pursuit and evasion games and proving the existence of strategies for the evader. In the case of Thompson’s group \(F\), we also present an alternative and more algebraic argument proving that it has infinite weak-cop number.
2024
Gromov’s Approximating Tree and the All-Pairs Bottleneck Paths Problem
Preprint Anders Cornect, Eduardo Martinez-Pedroza
Given a pointed metric space \((X,\mathrm{dist},w)\) on \(n\) points, its Gromov’s approximating tree is a \(0\)-hyperbolic pseudo-metric space \((X,\mathrm{dist}_T)\) such that \(\mathrm{dist}(x,w)=\mathrm{dist}_T(x,w)\) and \(\mathrm{dist}(x,y)−2\delta\log_2n \le \mathrm{dist}_T(x,y) \le \mathrm{dist}(x,y)\) for all \(x,y \in X\) where \(\delta\) is the Gromov hyperbolicity of \(X\). On the other hand, the all pairs bottleneck paths (APBP) problem asks, given an undirected graph with some capacities on its edges, to find the maximal path capacity between each pair of vertices. In this note, we prove: (1) Computing Gromov’s approximating tree for a metric space with \(n+1\) points from its matrix of distances reduces to solving the APBP problem on an connected graph with \(n\) vertices. (2) There is an explicit algorithm that computes Gromov’s approximating tree for a graph from its adjacency matrix in quadratic time. (3) Solving the APBP problem on a weighted graph with n vertices reduces to finding Gromov’s approximating tree for a metric space with \(n+1\) points from its distance matrix.
Presentations
2023
An Improved Algorithm for Gromov’s Approximating Tree
MUN Summer Undergraduate Research Forum, Oct. 2023; Science Atlantic Mathematics, Statistics and Computer Science, Oct. 2023; MUN Cross-Campus Combinatorics Conference, Aug. 2023
In 1987, Mikhail Gromov described an algorithm for constructing an approximating tree for an arbitrary finite metric space, with additive error proportional to a property of the space called the Gromov hyperbolicity. We discuss an improved version of this algorithm when the metric space is a graph, which runs in \(O(n^2)\) time given the graph’s adjacency matrix.
2022
The Watchman’s Walk on Directed Circulants and 3-Regular Cayley Graphs
MUN Summer Undergraduate Research Forum, Sep. 2022; East Coast Combinatorics Conference, Aug. 2022
The watchman number of a graph \(G\) is the length of a minimum, closed, dominating walk on \(G\), which we denote \(w(G)\). We provide results on the watchman number of certain Cayley graphs. We establish sharp bounds, along with exact values in certain special cases, for directed circulant graphs of out-degree \(2\). We also provide a full survey of the watchman number for all \(3\)-regular Cayley graphs of abelian groups, using a known classification of such graphs into isomorphism classes.