A unified construction of semiring-homomorphic graph invariants
arXiv:1901.01090 · doi:10.1007/s10801-020-00983-y
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 via Strassen's Positivstellensatz: , where ranges over all monotone semiring homomorphisms. Constructing and classifying graph invariants 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ász 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.
arXiv comment25 pages. v3: incorporated referee's suggestions
References in corpus (6)
- Graph Homomorphisms for Quantum Players
- Resource convertibility and ordered commutative monoids
- Bounds on entanglement assisted source-channel coding via the Lovasz theta number and its variants
- Orthogonal Representations, Projective Rank, and Fractional Minimum Positive Semidefinite Rank: Connections and New Directions
- A generalization of Strassen's Positivstellensatz
- Orthogonality and Dimensionality