2016/12/29 by Lele Wang, Wang, Lele, Ofer Shayevitz +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1612.09343
openalex publication_date 2016/12/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce the notion of information ratio Ir(H/G) between two (simple, undirected) graphs G and H, defined as the supremum of ratios k/n such that there exists a mapping between the strong products Gk to Hn that preserves non-adjacency. Operationally speaking, the information ratio is the maximal number of source symbols per channel use that can be reliably sent over a channel with a confusion graph H, where reliability is measured w.r.t. a source confusion graph G. Various results are provided, including in particular lower and upper bounds on Ir(H/G) in terms of different graph properties, inequalities and identities for behavior under strong product and disjoint union, relations to graph cores, and notions of graph criticality. Informally speaking, Ir(H/G) can be interpreted as a measure of similarity between G and H. We make this notion precise by introducing the concept of information equivalence between graphs, a more quantitative version of homomorphic equivalence. We then describe a natural partial ordering over the space of information equivalence classes, and endow it with a suitable metric structure that is contractive under the strong product. Various examples and open problems are discussed.