More Like this

1. Tree-like graphings, wallings, and median graphings of equivalence relations

   https://doi.org/10.1017/fms.2025.22  

   Chen, Ruiyuan; Poulin, Antoine; Tao, Ran; Tserunyan, Anush (March 2025, Forum of Mathematics, Sigma)

   We prove several results showing that every locally finite Borel graph whose large-scale geometry is ‘tree-like’ induces a treeable equivalence relation. In particular, our hypotheses hold if each component of the original graph either has bounded tree-width or is quasi-isometric to a tree, answering a question of Tucker-Drob. In the latter case, we moreover show that there exists a Borel quasi-isometry to a Borel forest, under the additional assumption of (componentwise) bounded degree. We also extend these results on quasi-treeings to Borel proper metric spaces. In fact, our most general result shows treeability of countable Borel equivalence relations equipped with an abstract wallspace structure on each class obeying some local finiteness conditions, which we call aproper walling. The proof is based on the Stone duality between proper wallings and median graphs (i.e., CAT(0) cube complexes). Finally, we strengthen the conclusion of treeability in these results to hyperfiniteness in the case where the original graph has one (selected) end per component, generalizing the same result for trees due to Dougherty–Jackson–Kechris. 

   more » « less
2. Factorization and pseudofactorization of weighted graphs

   Kristin Sheridan, Joseph Berleant (July 2023, Discrete applied mathematics)

   For unweighted graphs, finding isometric embeddings of a graph G is closely related to decompositions of G into Cartesian products of smaller graphs. When G is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of G. When G is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of G. Prior work has shown that an unweighted graph’s pseudofactorization can be used to generate a canonical isometric embedding into a product of the smallest possible pseudofactors. However, for arbitrary weighted graphs, which represent a richer variety of metric spaces, methods for finding isometric embeddings or determining their existence remain elusive, and indeed pseudofactorization and factorization have not previously been extended to this context. In this work, we address the problem of finding the factorization and pseudofactorization of a weighted graph G, where G satisfies the property that every edge constitutes a shortest path between its endpoints. We term such graphs minimal graphs, noting that every graph can be made minimal by removing edges not affecting its path metric. We generalize pseudofactorization and factorization to minimal graphs and develop new proof techniques that extend the previously proposed algorithms due to Graham and Winkler [Graham and Winkler, ’85] and Feder [Feder, ’92] for pseudofactorization and factorization of unweighted graphs. We show that any n-vertex, m-edge graph with positive integer edge weights can be factored in O(m2) time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of O(m2+n2 log log n) time. We also show that a pseudofactorization for such a graph can be computed in O(mn) time, plus the time to solve APSP, resulting in an O(mn + n2 log log n) running time. 

   more » « less
3. A quasi-local mass

   Alaee, Aghil; Khuri, Marcus; Yau, Shing-Tung (April 2024, Communications in mathematical physics)

   We define a new gauge independent quasi-local mass and energy, and show its relation to the Brown–York Hamilton–Jacobi analysis. A quasi-local proof of the positivity, based on spacetime harmonic functions, is given for admissible closed spacelike 2-surfaces which enclose an initial data set satisfying the dominant energy condition. Like the Wang-Yau mass, the new definition relies on isometric embeddings into Minkowski space, although our notion of admissibility is different from that of Wang and Yau. Rigidity is also established, in that vanishing energy implies that the 2-surface arises from an embedding into Minkowski space, and conversely the mass vanishes for any such surface. Furthermore, we show convergence to the ADM mass at spatial infinity, and provide the equation associated with optimal isometric embedding. 

   more » « less
4. Mining Largest Maximal Quasi-Cliques

   https://doi.org/10.1145/3446637  

   Sanei-Mehri, Seyed-Vahid; Das, Apurba; Hashemi, Hooman; Tirthapura, Srikanta (June 2021, ACM Transactions on Knowledge Discovery from Data)

   Quasi-cliques are dense incomplete subgraphs of a graph that generalize the notion of cliques. Enumerating quasi-cliques from a graph is a robust way to detect densely connected structures with applications in bioinformatics and social network analysis. However, enumerating quasi-cliques in a graph is a challenging problem, even harder than the problem of enumerating cliques. We consider the enumeration of top- k degree-based quasi-cliques and make the following contributions: (1) we show that even the problem of detecting whether a given quasi-clique is maximal (i.e., not contained within another quasi-clique) is NP-hard. (2) We present a novel heuristic algorithm K ernel QC to enumerate the k largest quasi-cliques in a graph. Our method is based on identifying kernels of extremely dense subgraphs within a graph, followed by growing subgraphs around these kernels, to arrive at quasi-cliques with the required densities. (3) Experimental results show that our algorithm accurately enumerates quasi-cliques from a graph, is much faster than current state-of-the-art methods for quasi-clique enumeration (often more than three orders of magnitude faster), and can scale to larger graphs than current methods. 

   more » « less
5. Generating Sets and Algebraic Properties of Pure Mapping Class Groups of Infinite Graphs

   https://doi.org/10.5802/ahl.238  

   Domat, George; Hoganson, Hannah; Kwak, Sanghoon (January 2025, Annales Henri Lebesgue)

   We completely classify the locally finite, infinite graphs with pure mapping class groups admitting a coarsely bounded generating set. We also study algebraic properties of the pure mapping class group. We establish a semidirect product decomposition, compute first integral cohomology, and classify when they satisfy residual finiteness and the Tits alternative. These results provide a framework and some initial steps towards quasi-isometric and algebraic rigidity of these groups. 

   more » « less