The Boolean matrix product of two 0-1 matrices and is the matrix defined as
If and the matrix is an adjacency matrix of a graph , then determines for all pairs of vertices in whether or not there is a path of length two from one vertex to the other. This operation can be used to detect if a graph has a 3-clique: we check for an such that .
I am interested in a natural generalization of this to 4-cliques in 3-uniform hypergraphs. Let be vertices of such a hypergraph . We say that a triangle on in is a set of three edges from of the form = {}, = {}, = {} for some vertex .
Let iff there is a triangle on in . We can detect if there is a 4-clique in by checking for such that , where is the "adjacency tensor" of .
More formally, we can define
Is there a name for this type of operation in the literature? I would expect the following to have a name: Given three order-3 tensors of dimensions , define the order-3 tensor However I can't seem to find anything related. (Pardon me for the lack of subscripts, but I find the above notation easier to read.)
No comments:
Post a Comment