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.



Cayley graphs do not have isolated maximal cliques
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](https://mathoverflow.net/questions/150744/the-line-graphs-of-complete-graphs-and-cayley-graphs).


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


