2025/05/09 by Can, Mahir Bilen, Shantanu Chakrabartty, Chakrabartty, Shantanu
Computer Science · Mathematics · #05C12 #05C90 #54E35 #60B99 #68T05 #94B60 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Fixed Point Theorems Analysis #Information Theory (cs.IT) #Metric Geometry (math.MG) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2505.06405
openalex publication_date 2025/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let (X1,d1),…, (XN,dN) be metric spaces, where di: Xi × Xi → [0,1] is a distance function for i=1,…,N. Let X denote the set theoretic product X1× ⋯ × XN. Let G = (V,E) be a directed graph with vertex set V =\1,…, N\, and let P = \pij\ be a collection of weights, where each pij∈ (0, 1] is associated with the edge (i,j) ∈ E. We introduce the function dX,G,P: X× X → [0,1] defined by dX,G,P(g,h) := (1 - (1)/(N)∑j=1N ∏i=1N [1- di(gi,hi)]^\frac1pji ), for all g,h ∈ X. In this paper we show that dX,G,P defines a metric space over X. Then we determine how this distance behaves under various graph operations, including disjoint unions and Cartesian products. We investigate two limiting cases: (a) when dX,G,P is defined over a finite field, leading to a broad generalization of graph-based distances commonly studied in error-correcting code theory; and (b) when the metric is extended to graphons, enabling the measurement of distances in a continuous graph limit setting.