Weighted theta functions for non-commutative graphs

Publication date: 31 December 2020

Abstract: Gr"otschel, Lov'asz, and Schrijver generalized the Lov'asz

v a r t h e t a

function by allowing a weight for each vertex. We provide a similar generalization of Duan, Severini, and Winter's

i l d e v a r t h e t a

on non-commutative graphs. While the classical theory involves a weight vector assigning a non-negative weight to each vertex, the non-commutative theory uses a positive semidefinite weight matrix. The classical theory is recovered in the case of diagonal weight matrices. Most of Gr"otschel, Lov'asz, and Schrijver's results generalize to non-commutative graphs. In particular, we generalize the inequality

v a r t h e t a (G, w) v a r t h e t a (o v e r l i n e G, x) g e l a n g l e w, x a n g l e

with some modification needed due to non-commutative graphs having a richer notion of complementation. Similar to the classical case, facets of the theta body correspond to cliques and if the theta body anti-blocker is finitely generated then it is equal to the non-commutative generalization of the clique polytope. We propose two definitions for non-commutative perfect graphs, equivalent for classical graphs but inequivalent for non-commutative graphs.

Has companion code repository: https://github.com/dstahlke/NoncommutativeGraphs.jl

This page was built for publication: Weighted theta functions for non-commutative graphs

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