# Product dimension of graphs

Given a simple undirected graph $G$, its product dimension is defined as the least positive integer $k$ such that $G$ embeds into a direct product of $k$ complete graphs. In a paper published in 1980, Lovasz et al state the following theorem.

Let $D_k$ denote the graph on $k$ vertices and no edges and $n\ge 2$. If $k>(n-1)!$ then the product dimension of $K_n+D_k=n+1$.

They provide a proof for the case $k> n!$ and for the other case they say that it follows from an unpublished result by Deza and Frankl. I am trying to find a proof for the other case. Hence this question.

Frankl and Deza initiated the study of families of intersecting permutations. There is a lot of literature on this subject and some very hard results but let's focus on an easy result which was one of their early observations. Call two permutations $\pi,\pi'\in S_n$ intersecting if they agree in some position, or in other words $\pi(i)=\pi'(i)$ for some $i$. An intersecting family of permutations is a subset of $S_n$ where any two permutations are intersecting.
Claim: An intersecting family in $S_n$ has size at most $(n-1)!$.
Let's explain how this relates to the result about product dimensions. The direct product of $n$ complete graphs $K_{r_1},\dots, K_{r_n}$ can be described by taking vertices to be $n$-tuples $u=(u_1,\dots,u_n)$ and an edge between any pair unless they agree on some coordinate (in other words, it is the complement of the rook graph on the $r_1\times\cdots\times r_n$ grid).
Suppose that $K_n+D_k$ can be embedded in the product of $n$ complete graphs. Let's label the vertices of $K_n$ as $\{w_1,w_2,\dots,w_n\}$ and let's show that to any vertex $v$ of $D_k$ we can associate a permutation in $S_n$. By the interpretation above, $v$ and $w_i$ agree on at least one coordinate, while the $w_i$'s do not agree on any coordinate. Denote by $\pi(i)$ the index of the coordinate where $v$ and $w_i$ agree. This is a permutation that uniquely determines $v$.
Now, the family $\pi_1,\dots,\pi_k$ is intersecting, since there are no edges between any two vertices of $D_k$. Therefore we must have $k\le (n-1)!$ from our earlier claim.