We present a new formulation of the maximum clique problem of a graph in complex space. We start observing that the adjacency matrix A of a graph can always be written in the form A=B^2 where B is a complex, symmetric matrix formed by vectors of zero length (null vectors) and the maximum clique problem can be transformed in a geometrical problem for these vectors. This problem, in turn, is translated in spinorial language and we show that each graph uniquely identifies a set of pure spinors, that is vectors of the endomorphism space of Clifford algebras, and the maximum clique problem is formalized in this setting so that, this much studied problem, may take advantage from recent progresses of pure spinor geometry.

A Spinorial Formulation of the Maximum Clique Problem of a Graph

BUDINICH, MARCO;
2006-01-01

Abstract

We present a new formulation of the maximum clique problem of a graph in complex space. We start observing that the adjacency matrix A of a graph can always be written in the form A=B^2 where B is a complex, symmetric matrix formed by vectors of zero length (null vectors) and the maximum clique problem can be transformed in a geometrical problem for these vectors. This problem, in turn, is translated in spinorial language and we show that each graph uniquely identifies a set of pure spinors, that is vectors of the endomorphism space of Clifford algebras, and the maximum clique problem is formalized in this setting so that, this much studied problem, may take advantage from recent progresses of pure spinor geometry.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11368/1689843
 Avviso

Registrazione in corso di verifica.
La registrazione di questo prodotto non è ancora stata validata in ArTS.

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 10
social impact