The largest clique in $X\times Y$ is the smallest of the largest cliques in $X$ and $Y$

Question

From the book Algebraic Graph Theory by Godsil and Royle

Show that $\omega(X\times Y)$ is the minimum of $\omega(X)$ and $\omega(Y)$.

Here $\omega(X)$ denotes the size of the largest clique in $X$.

This reminded me of the Hadetniemi conjecture

$\chi(X\times Y) = min\{\chi(X), \chi(Y)\}$

Since it is a conjuecture we will instead use the weaker (proven) statement:

$\chi(X\times Y) \le min\{\chi(X), \chi(Y)\}$

Clearly if $X$ and $Y$ are graphs such that $n = \chi(X) \le \chi(Y) = m$, we have that $\chi(X\times Y) \le n$ and therefore $\omega(X \times Y) \le n$.

---

This is as far as I got, the only bound I could get for $\omega(X\times Y)$, was that $\omega(X\times Y) \le \omega(X)$ and $\omega(X\times Y) \le \omega(Y)$. What I'm trying to do now is find that $\min\{\omega(X), \omega(Y)\}$ is a lower bound for $\omega(X\times Y)$, but I'm stumped.

How can I provide a lower bound for $\omega(X\times Y)$?

Answer 1

This is just to show $\min\{\omega(X), \omega(Y)\} \leq \omega(X\times Y)$.

Hint: Consider a clique $J\leq X$ and a clique $K\leq Y$. Can you find a clique of size $\min\{|J|, |K|\}$ in the subgraph $J\times K$ of $X\times Y$?

You might find it helpful to label $J = \{u_1, u_2, \dots, u_j\}$ and $K = \{v_1, v_2, \dots, v_k\}$, and draw a grid $J\times K = \{(u_i, v_n): 1\leq i\leq k, 1\leq n\leq j\}$, noting that two vertices are adjacent if and only if they are not in the same row or column.

Answer in the box below:

Let $|J| = j$ and $|K| = k$. Assume without loss of generality that $j\leq k$. Then the diagonal entries $\{(u_1, v_1), (u_2, v_2), \dots, (u_j, v_j)\}$ form a clique of size $j$.