Probabilistic refinement of the asymptotic spectrum of graphs

DOI10.1007/S00493-020-4324-5MaRDI QIDQ2064765zbMATH OpenOpenAlexFDO

Authors Péter Vrana

Publication date 6 January 2022

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

Shannon capacityasymptotic spectrum

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: The asymptotic spectrum of graphs, introduced by Zuiddam (arXiv:1807.00169, 2018), is the space of graph parameters that are additive under disjoint union, multiplicative under the strong product, normalized and monotone under homomorphisms between the complements. He used it to obtain a dual characterization of the Shannon capacity of graphs as the minimum of the evaluation function over the asymptotic spectrum and noted that several known upper bounds, including the Lov'asz number and the fractional Haemers bounds are in fact elements of the asymptotic spectrum (spectral points). We show that every spectral point admits a probabilistic refinement and characterize the functions arising in this way. This reveals that the asymptotic spectrum can be parameterized with a convex set and the evaluation function at every graph is logarithmically convex. One consequence is that for any incomparable pair of spectral points $f$ and $g$ there exists a third one $h$ and a graph $G$ such that $h(G)<minf(G),g(G)$, thus $h$ gives a better upper bound on the Shannon capacity of $G$. In addition, we show that the (logarithmic) probabilistic refinement of a spectral point on a fixed graph is the entropy function associated with a convex corner.

Recommendations

• The asymptotic spectrum of graphs and the Shannon capacity
• On the Shannon capacity of probabilistic graphs
• The Shannon capacity of a union
• On the Shannon capacity of a graph
• Developments in the theory of graph spectra

Cites work

• 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 1131873 (Why is no real title available?)
• scientific article; zbMATH DE number 780788 (Why is no real title available?)
• A bound on the Shannon capacity via a linear programming variation
• A sharp continuity estimate for the von Neumann entropy
• A unified construction of semiring-homomorphic graph invariants
• Blocking and anti-blocking pairs of polyhedra
• Bounds on Entanglement-Assisted Source-Channel Coding via the Lovász \(\vartheta \) Number and Its Variants
• Entropy splitting for antiblocking corners and perfect graphs
• Fredman–Komlós bounds and information theory
• Graph derivatives
• Graph imperfection. I
• Information theory. Coding theorems for discrete memoryless systems
• Normal hypergraphs and the perfect graph conjecture
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• On a Fractional Version of Haemers’ Bound
• On the Shannon capacity of a graph
• On the Shannon capacity of probabilistic graphs
• On the capacity of the arbitrarily varying channel for maximum probability of error
• Perfect couples of graphs
• Perfect graphs and graph entropy: An updated survey
• Quantum information theory and quantum statistics.
• Relaxations of vertex packing
• Repeated communication and Ramsey graphs
• Resource convertibility and ordered commutative monoids
• The asymptotic spectrum of graphs and the Shannon capacity
• The asymptotic spectrum of tensors.
• The sandwich theorem
• The zero-error side information problem and chromatic numbers (Corresp.)
• Two-step encoding for finite sources

Cited in

(2)

• Quantitative asymptotics of graphical projection pursuit
• Abstract Vergleichsstellensätze for Preordered Semifields and Semirings I

This page was built for publication: Probabilistic refinement of the asymptotic spectrum of graphs

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