Graph information ratio

DOI10.1137/16M1110066MaRDI QIDQ4599114zbMATH OpenOpenAlexFDO

Authors Lele Wang, Ofer Shayevitz

Publication date 18 December 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.09343

zbMATH Keywords

graph capacitygraph homomorphisminformation theory

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Information theory (general) (94A15) Coding theorems (Shannon theory) (94A24)

Abstract: We introduce the notion of information ratio $extIr(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 $G^k$ to $H^n$ 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 $extIr(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, $extIr(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.

Recommendations

• On an infinite family of graphs with information ratio \(2 - 1/k\)
• Entropy of Digraphs and Infinite Networks
• On the information ratio of graphs without high-degree neighbors
• On the information ratio of graphs with many leaves
• Secret sharing based on Cartesian product of graphs

Cites work

• A note on the star chromatic number
• Girth and fractional chromatic number of planar graphs
• Homomorphisms of 3-chromatic graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3683587 (Why is no real title available?)
• scientific article; zbMATH DE number 3745081 (Why is no real title available?)
• scientific article; zbMATH DE number 3468645 (Why is no real title available?)
• scientific article; zbMATH DE number 1054727 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 6116733 (Why is no real title available?)
• scientific article; zbMATH DE number 3366941 (Why is no real title available?)
• n-tuple colorings and associated graphs
• On metric properties of maps between Hamming spaces and related graph homomorphisms
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• On the Shannon capacity of a graph
• Optimization problems over unit-distance representations of graphs
• Relative capacity and dimension of graphs
• Resource convertibility and ordered commutative monoids
• Sur le coloriage des graphs
• The Shannon capacity of a graph and the independence numbers of its powers
• The Shannon capacity of a union

Cited in

(2)

• A unified construction of semiring-homomorphic graph invariants
• CROSS RATIO GRAPHS

This page was built for publication: Graph information ratio

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4599114)