Cayley graphs do not have isolated maximal cliques

Question

Let a Cayley graph $G$ of a group $H$ with respect to the generating set $\{s_i\}$ have a clique of order $> 2$. In addition assume the graph $G$ is non-complete. If the clique size is less than half the order of $G$, then is it possible for some group $H$ that $G$ has a unique "disjoint maximal clique". By "disjoint maximal clique", I mean a clique equal to the clique size of the graph, and such that any other clique of same order would not be vertex disjoint with the prior clique.

I don't think so. For, if $(e),(s_1),(s_1\cdot s_2),(s_1\cdot s_2\cdot s_3),\ldots,(s_1\cdot s_2\cdots s_n)$ be the sequence of vertices in a maximal clique, then I think even $(s_1^2),(s_1^3),(s_1^2\cdot s_2),\ldots,(s_1^2\cdot s_2\cdots s_n)$ would also be a sequence of vertices in a maximal clique, where $e$ denotes the identity element. But, what if $s_1$ is an order $2$ or $3$ element. How do we ensure that there always exist a disjoint clique apart from the clique $(e),(s_1),(s_1\cdot s_2),(s_1\cdot s_2\cdot s_3),\ldots,(s_1\cdot s_2\cdots s_n)$? Will this be true at least for the case when $H$ is an abelian/cyclic group? Any hints? Thanks beforehand.

Answer 1

Let $G$ be the linegraph of the complete graph $K_n$ for $n\geq 5$. For some but not all $n$, $G$ is a Cayley graph, see Chris Godsil's answer to another question.

$G$ has $\binom n2$ vertices and degree $2n-4$. The maximum cliques of $G$ correspond to the edges incident with one vertex and so they have size $n-1$. Moreover, the cliques corresponding to two different vertices of $K_n$ have one point in common, namely the edge between those two vertices.

Therefore, $G$ is an example of a Cayley graph for which any two maximum cliques intersect, even though the maximum cliques only have size about the square root of the number of vertices.

I wonder if this example is optimal in some sense.

---

ADDED: Here is an exposition of Ilya's argument from the comments.

Theorem. If a vertex-transitive graph with $N$ vertices has cliques of size $k$ such that $k^2<N$, then there are two such cliques which are disjoint.

Proof. Take a fixed $k$-clique $C$ and apply a random automorphism $\gamma$. The expected number of elements of $C$ that map to an element of $C$ is $k^2/N$, so $k^2<N$ implies that $C$ must sometimes map to a clique disjoint from itself.

In the case of a Cayley graph of a group $\varGamma$, we can use a random non-identity element of $\varGamma$ to improve the inequality to $k(k-1)<N-1$.

There is a clique size gap of about $\sqrt 2$ between these bounds and the linegraph of a complete graph. So the problem is still missing a complete solution.