A spinorial formulation of the maximum clique problem of a graph

DOI10.1063/1.2186256MaRDI QIDQ3441737zbMATH OpenOpenAlexFDO

Authors Marco Budinich, P. Budinich

Publication date 16 May 2007

Published in Journal of Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math-ph/0603068

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Clifford algebras, spinors (15A66) Spinor and twistor methods applied to problems in quantum theory (81R25)

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 B 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.

Recommendations

• Spinorial formulations of graph problems
• On solving the maximum clique problem
• On computational complexity of Clifford algebra
• Continuous Characterizations of the Maximum Clique Problem
• Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation

Cites work

• A global optimization approach for solving the maximum clique problem
• An introduction to the spinorial chessboard
• Continuous Characterizations of the Maximum Clique Problem
• Evolution towards the maximum clique
• Exact bounds on the order of the maximum clique of a graph.
• Fock space description of simple spinors
• scientific article; zbMATH DE number 41100 (Why is no real title available?)
• scientific article; zbMATH DE number 3238347 (Why is no real title available?)
• scientific article; zbMATH DE number 3091887 (Why is no real title available?)
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Noncommutative geometry and gauge theory on discrete groups
• The maximum clique problem

Cited in

(8)

• Zeon and idem-Clifford formulations of Boolean satisfiability
• Zeons, orthozeons, and graph colorings
• On computational complexity of Clifford algebra
• Spinorial formulations of graph problems
• Laplace and Dirac operators on graphs
• Hamiltonian cycle enumeration via fermion-zeon convolution
• Block linear majorants in quadratic 0--1 optimization
• A characterization of the geometry of large maximal cliques of the alternating forms graph

This page was built for publication: A spinorial formulation of the maximum clique problem of a graph

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