Intersection number of the tensor product of graphs

Question

(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$.

Answer 1

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