Probabilistic refinement of the asymptotic spectrum of graphs

DOI10.1007/S00493-020-4324-5zbMATH Open1499.05508arXiv1903.01857OpenAlexW3198306887MaRDI QIDQ2064765FDOQ2064765

Authors: Péter Vrana 

Publication date: 6 January 2022

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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)