𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Contractors and connectors of graph algebras

✍ Scribed by László Lovász; Balázs Szegedy

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
170 KB
Volume
60
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We study generalizations of the “contraction‐deletion” relation of the Tutte polynomial, and other similar simple operations, to other graph parameters. The question can be set in the framework of graph algebras introduced by Freedman at al [Reflection positivity, rank connectivity, and homomorphisms of graphs, J. Amer. Math. Soc. 20 (2007), 37–51.] Graph algebras are defined by a graph parameter, and they were introduced in order to study and characterize homomorphism functions. We prove that for homomorphism functions, these graph algebras have special elements called “contractors” and “connectors”. This gives a new characterization of homomorphism functions. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 11–30, 2009

📜 SIMILAR VOLUMES

Computing View Graphs of Algebraic Surfa
Computing View Graphs of Algebraic Surfaces
✍ J.H. Rieger 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 496 KB

The "bad" directions or centres of projection, which yield degenerate projections of a smooth surface \(S\) embedded in 3-space, lie on a bifurcation set \(\mathcal{B}\) of positive codimension in view space \(\mathcal{V}\) (where \(\mathcal{V}=\mathbb{P}^{2}\) or \(\mathbb{R}^{3} \backslash S\) ).

The Algebra of Flows in Graphs
The Algebra of Flows in Graphs
✍ David G Wagner 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 452 KB

We define a contravariant functor K from the category of finite graphs and graph morphisms to the category of finitely generated graded abelian groups and homomorphisms. For a graph X, an abelian group B, and a nonnegative integer j, Ž j Ž . . an element of Hom K X , B is a coherent family of B-valu

On graphs and algebraic graphs that do n
On graphs and algebraic graphs that do not contain cycles of length 4
✍ Noga Alon; H. Tracy Hall; Christian Knauer; Rom Pinchasi; Raphael Yuster 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

We consider extremal problems for algebraic graphs, that is, graphs whose vertices correspond to vectors in R d , where two vectors are connected by an edge according to an algebraic condition. We also derive a lower bound on the rank of the adjacency matrix of a general abstract graph using the num

An algebraic characterization of project
An algebraic characterization of projective-planar graphs
✍ Lowell Abrams; Daniel C. Slilaty 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract We give a detailed algebraic characterization of when a graph __G__ can be imbedded in the projective plane. The characterization is in terms of the existence of a dual graph __G__\* on the same edge set as __G__, which satisfies algebraic conditions inspired by homology groups and inte