Spinorial formulations of graph problems (Q430733)

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.