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

  • $\begingroup$ 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. $\endgroup$ – Todd Trimble Mar 10 '16 at 13:25
  • $\begingroup$ (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.) $\endgroup$ – Todd Trimble Mar 10 '16 at 13:28
  • $\begingroup$ Right, that's the usual thing -- with all the concomitants I mentioned. $\endgroup$ – 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$.

  • 1
    $\begingroup$ 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)$. $\endgroup$ – Tony Huynh Mar 14 '16 at 1:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.