A unified construction of semiring-homomorphic graph invariants

DOI10.1007/S10801-020-00983-YMaRDI QIDQ2052822zbMATH OpenOpenAlexWikidataFDO

Authors Tobias Fritz

Publication date 29 November 2021

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

fractional colouring numberLovász numberShannon capacity of graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Fractional graph theory, fuzzy graph theory (05C72) Ordered rings, algebras, modules (06F25)

Abstract: It has recently been observed by Zuiddam that finite graphs form a preordered commutative semiring under the graph homomorphism preorder together with join and disjunctive product as addition and multiplication, respectively. This led to a new characterization of the Shannon capacity $Theta$ via Strassen's Positivstellensatz: $$, where $f:mathsfGraphomathbb{R}_{+}$ ranges over all monotone semiring homomorphisms. Constructing and classifying graph invariants $mathsfGraphomathbb{R}_{+}$ which are monotone under graph homomorphisms, additive under join, and multiplicative under disjunctive product is therefore of major interest. We call such invariants semiring-homomorphic. The only known such invariants are all of a fractional nature: the fractional chromatic number, the projective rank, the fractional Haemers bounds, as well as the Lov'asz number (with the latter two evaluated on the complementary graph). Here, we provide a unified construction of these invariants based on linear-like semiring families of graphs. Along the way, we also investigate the additional algebraic structure on the semiring of graphs corresponding to fractionalization. Linear-like semiring families of graphs are a new concept of combinatorial geometry different from matroids which may be of independent interest.

Recommendations

• Shannon capacity and the categorical product
• Semirings of graphs homomorphisms and applications in network problems
• The asymptotic spectrum of graphs and the Shannon capacity
• Generalized homomorphism graph functions
• A graph associated to a commutative semiring

Cites work

• A generalization of Strassen’s Positivstellensatz
• Approximate graph coloring by semidefinite programming
• Bounds on Entanglement-Assisted Source-Channel Coding via the Lovász Number and Its Variants
• Graph information ratio
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3650785 (Why is no real title available?)
• scientific article; zbMATH DE number 6116733 (Why is no real title available?)
• scientific article; zbMATH DE number 3399453 (Why is no real title available?)
• Mapping \(\mathbb F_1\)-land: an overview of geometries over the field with one element
• Model theory.
• Monoidal functors, species and Hopf algebras
• New lower bounds for the Shannon capacity of odd cycles
• On a Fractional Version of Haemers’ Bound
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• On the Shannon capacity of a graph
• Orthogonal representations over finite fields and the chromatic number of graphs
• Orthogonal Representations, Projective Rank, and Fractional Minimum Positive Semidefinite Rank: Connections and New Directions
• Orthogonality and dimensionality
• Positive polynomials and sums of squares
• Proofs from THE BOOK. Including illustrations by Karl H. Hofmann
• Quantum homomorphisms
• Resource convertibility and ordered commutative monoids
• Simple Lie algebras over a field of characteristic zero
• The asymptotic spectrum of graphs and the Shannon capacity
• The asymptotic spectrum of tensors.
• The sandwich theorem
• Zero-error information theory

Cited in

(6)

• Probabilistic refinement of the asymptotic spectrum of graphs
• Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants
• scientific article; zbMATH DE number 5657766 (Why is no real title available?)
• scientific article; zbMATH DE number 4106308 (Why is no real title available?)
• scientific article; zbMATH DE number 637339 (Why is no real title available?)
• Abstract Vergleichsstellensätze for Preordered Semifields and Semirings I

This page was built for publication: A unified construction of semiring-homomorphic graph invariants

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