# Intersection number of the tensor product of graphs

(Trying to clarify the question; the answer given below is wrong.)

If ${\cal C}$ is a collection of subsets of a set $X$, we associate to ${\cal C}$ a graph $G_{\cal C} = (V,E)$ where $V = {\cal C}$ and $$E = \big\{\{A,B\}: A\neq B\in {\cal C} \land A\cap B \neq \emptyset\big\}.$$

If $G$ is a simple, undirected graph, we define its intersection number $\iota(G)$ to be the smallest $n\in\mathbb{N}$ such that there is a collection ${\cal C}$ of subsets $[n]:=\{1,\ldots,n\}$ such that $G_{\cal C} \cong G$.

Let $G, H$ be finite, simple, undirected graphs. Their tensor product $G\times H$ is given by $V(G\times H) = V(G) \times V(H)$ and $$E(G\times H) = \{\{(u, u'), (v,v')\}: \{u,v\} \in E(G) \text{ and } \{u',v'\} \in E(H)\}.$$

It is easy to see that $\iota(G\times H) \leq \iota(G)\dot \iota(H)$. (We give a proof of this just after the question.)

Question. Do we have $\iota(G\times H) = \iota(G) \iota(H)$ for all finite simple graphs $G, H$?

Proof that $\iota(G\times H) \leq \iota(G) \iota(H)$. Suppose $\iota(G) = n$ and $\iota(H) = m$, and ${\cal C}$ is a set of subsets of $[n]$ such that $G_{\cal C} \cong G$, and and ${\cal D}$ is a set of subsets of $[m]$ such that $G_{\cal D} \cong H$. Set $${\cal C} \times {\cal D} := \{C\times D: C\in{\cal C} \text{ and } D\in {\cal D}\},$$ notice that ${\cal C}\times {\cal D}$ is a set of subsets of $[m]\times [n]$ (which has $mn$ elements), and check that $G_{{\cal C}\times {\cal D}} \cong G\times H$.

• Since the word 'categorical' was invoked, I'll ask: what are the morphisms? In case anyone thinks the answer should be obvious, let me point out that by "simple undirected graph" I think graph theorists mean the same thing as a set equipped with a symmetric irreflexive relation $E$, and the obvious definition $x E y$ implies $f(x) E' f(y)$ would preclude the existence of a map from a pair of vertices with an edge between them to the one-point graph, and in fact the category has no terminal object and has fairly poor categorical properties. – Todd Trimble Mar 10 '16 at 13:25
• (To get a better-behaved category, one trick might be to recognize that there is a natural bijective correspondence between sets equipped with a symmetric irreflexive relation, and sets equipped with a symmetric reflexive relation, and switch to the latter category with the obvious notion of map. This gives actually quite a nice category.) – Todd Trimble Mar 10 '16 at 13:28
• Right, that's the usual thing -- with all the concomitants I mentioned. – Todd Trimble Mar 10 '16 at 13:58

So first, let's get a few problems out of the way, using that the intersection number is the smallest number of cliques needed to cover all edges of the graph. For all $n$, $i(K_n) = 1$. Next, we have $(*)$: $\exists n$ such that $G \times H = K_n$ is equivalent to $\exists n_g n_h$ such that $G = K_{n_g}$ and $H = K_{n_h}$ (by definition of the tensor product). Now we can say $(**)$: if $G = \cup_i K_{n_i}$ and $H = \cup_j K_{n_j}$ then $i(G \times H) = i(G) \cdot i(H)$.
Claim: for any pair of graphs $G$, $H$, $i(G \times H) = i(G) \cdot i(H)$.
To get a clique-covering of size $i(G) \cdot i(H)$, we just use the coverings of $G$ and $H$, as in $(**)$.
We can prove that there is no smaller covering by contradiction. Suppose that there is a clique covering of $G \times H$ with $i(G \times H) < i(G) \cdot i(H)$. Then by $(*)$, we get a clique covering of (wlog) $G$ of size less than $i(G)$, contradicting the minimality of the covering of $G$.
• It looks like you are using the strong product, while the question asks about the tensor product. For example, the tensor product of $K_2$ with itself is a matching of size $2$. So $i(K_2 \times K_2) > i(K_2)i(K_2)$. – Tony Huynh Mar 14 '16 at 1:05