A unified construction of semiring-homomorphic graph invariants

DOI10.1007/S10801-020-00983-YzbMATH Open1478.05120arXiv1901.01090OpenAlexW3132076842WikidataQ123109808 ScholiaQ123109808MaRDI QIDQ2052822FDOQ2052822

Authors: Tobias Fritz 

Publication date: 29 November 2021

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

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.

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

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

zbMATH Keywords

Shannon capacity of graphsfractional colouring numberLovász number

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Title not available (Why is that?)
• Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants
• Title not available (Why is that?)
• Title not available (Why is that?)
• Abstract Vergleichsstellensätze for Preordered Semifields and Semirings I
• Probabilistic refinement of the asymptotic spectrum of graphs

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)