8
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
+25
$\begingroup$

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

Proof: Notice that if two permutations lie in the same coset of the subgroup generated by an n-cycle, then they can't intersect. Since there are (n-1)! such cosets we get the desired bound.


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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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