Spinorial formulations of graph problems

DOI10.1007/S00006-011-0298-0MaRDI QIDQ430733zbMATH OpenOpenAlexFDO

Authors Glenn M. Harris, G. Stacey Staples

Publication date 26 June 2012

Published in Advances in Applied Clifford Algebras (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00006-011-0298-0

zbMATH Keywords

Clifford algebracliquescyclesfinite graphFock subspacegraphsmatchingsquantum probabilityspinor polynomialsspinor spacespinors

Mathematics Subject Classification ID

Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Clifford algebras, spinors (15A66)

Review text

This paper presents a spinorial formulation of some problems in graph theory. Firstly, it gives a brief review of basic results from graph theory and from Clifford algebras and spinors. Then, starting with an arbitrary finite graph, spinor spaces are constructed such that their properties reveal information about the structure of the graph. Spinor polynomials are introduced, and the notions of degrees of polynomials and Fock subspace dimensions are tied together with matchings, cliques, independent sets, and cycle covers of arbitrary finite graphs. The maximal clique problem is revisited and a new spinorial formulation based on the graph's vertex incidence spinor is presented. Finally, the spinor adjacency operator associated with a graph is introduced and used to enumerate cycles of arbitrary length.

Recommendations

• A spinorial formulation of the maximum clique problem of a graph
• Clifford algebras, random graphs, and quantum random variables
• Reductions in computational complexity using Clifford algebras
• Computational complexity reductions using Clifford algebras
• Spins and fermions on arbitrary lattices

Cites work

• A new adjacency matrix for finite graphs
• A spinorial formulation of the maximum clique problem of a graph
• Clifford algebras and spinors.
• Cohomology in the pure spinor formalism for the superstring
• scientific article; zbMATH DE number 3238347 (Why is no real title available?)
• scientific article; zbMATH DE number 3091887 (Why is no real title available?)
• Nilpotent adjacency matrices and random graphs.
• Nilpotent adjacency matrices, random graphs and quantum random variables
• On computational complexity of Clifford algebra
• Spinor approach to the rotation and reflection groups

Cited in

(7)

• Zeon and idem-Clifford formulations of Boolean satisfiability
• Zeons, orthozeons, and graph colorings
• Clifford algebras, random graphs, and quantum random variables
• A spinorial formulation of the maximum clique problem of a graph
• Kravchuk matrices and induced operators on Clifford algebras
• Laplace and Dirac operators on graphs
• Hamiltonian cycle enumeration via fermion-zeon convolution

This page was built for publication: Spinorial formulations of graph problems

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