Details

Autor(en) / Beteiligte

• Vrana, Péter

Titel

Probabilistic Refinement of the Asymptotic Spectrum of Graphs

Ist Teil von

• Combinatorica (Budapest. 1981), 2021-12, Vol.41 (6), p.873-904

Ort / Verlag

Berlin/Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2021

Link zum Volltext

Quelle

SpringerLink (Online service)

Beschreibungen/Notizen

• The asymptotic spectrum of graphs, introduced by Zuiddam (Combinatorica, 2019), 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ász 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 ) < min{ f ( 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.