7
$\begingroup$

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?

$\endgroup$

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.