In his book "Large networks and graph limits" (available online here: http://web.cs.elte.hu/~lovasz/bookxx/hombook-almost.final.pdf), Lovasz describes a multiplication operation (he calls it concatenation) on "bi-labeled graphs". An $(m,n)$ bi-labeled graph is a graph in which some vertices are labeled with the left labels $1, \ldots, m$, and some are labeled with the right labels $1, \ldots, n$. The left and right label $i$ are distinguished. A vertex is allowed to have more than one left and/or right labels assigned to it.

The concatenation operation of Lovasz (definition begins on page 85 of the above link), is as follows. If $G$ is a $(m,n)$ bi-labeled graph and $H$ is a $(n,k)$ bi-labeled graph, then the concatenation $G \circ H$ is the $(m,k)$ bi-labeled graph obtained from the disjoint union of $G$ and $H$ by identifying the vertex of $G$ with right label $i$ with the vertex of $H$ with left label $i$ for all $i = 1, \ldots n$, and then forgetting these labels, but retaining the left labels of $G$ and the right labels of $H$.

If it is not clear how this corresponds to matrix multiplication, consider the following. Fix a graph $K$. For any $(m,n)$ bi-labeled graph $G$, define the $K$-homomorphism matrix of $G$ as the matrix $M^{G \to K}$ whose rows/columns are indexed by $m$-tuples/$n$-tuples of vertices of $K$ such that its $(u_1, \ldots, u_m),(v_1, \ldots, v_n)$-entry is equal to the number of homomorphisms from $G$ to $K$ that map the vertex with left label $i$ to $u_i$ and the vertex with right label $j$ to $v_j$ for all $i,j$. One can check that $M^{G \circ H \to K} = M^{G \to K}M^{H \to K}$.

It is unlikely, to say the least, that Lovasz was not aware of this correspondence between concatenation and matrix multiplication, but I could not find any explicit mention of this in the book or elsewhere. Admittedly I have not read the entire book in detail yet, but I have looked through it for mention of this.

Does anyone know if this correspondence is explicitly spelled out anywhere? Either in the book or an article somewhere?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.