# Cayley graphs do not have isolated maximal cliques

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.

• Your question is not clear. "Disjoint" is a property of two things, not a property of one thing. May 23 '20 at 9:04
• @BrendanMcKay edited the post. May 23 '20 at 11:17
• Your terminology looks confusing. "Unique maximal clique" usually means that it is a maximal clique and there is no other maximal clique. May 23 '20 at 11:23
• @FedorPetrov no, my meaning is that there is a maximal clique and no other "vertex disjoint" maximal clique May 23 '20 at 11:41
• Rephrased: "Do all maximal cliques in $G$ pairwise intersect"? (Also I don't see why you need to assume $G$ is non-complete: then your condition is trivially satisfied.) May 23 '20 at 12:44

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.

Theorem. If a vertex-transitive graph with $$N$$ vertices has cliques of size $$k$$ such that $$k^2, 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 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).

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.

• It is optimal in some sense: if a Cayley graph contains a clique of size $<\sqrt n$, then it contains its isomorphic copy, from probabilistic reasons May 23 '20 at 16:01
• @IlyaBogdanov you mean if a cayley graph has clique size $< \sqrt n$, then it has disjoint cliques of maximal size? Any reference for this? May 23 '20 at 16:51
• If a clique size is $k$, there are $n$ copies of one clique (starting from any vertex), and only $k(k-1)+1$ of them intersects the initial one (any vertex of a copy may coincide with any vertex of the origin). May 23 '20 at 16:54
• will the property hold for cayley graphs on cyclic or abelian groups at least? May 23 '20 at 16:56
• @IlyaBogdanov in saying that there are $n$ cliques of size $k$, you are using the vertex transitivity of the graph, isnt it? So this should hold for vertex transitive graphs also, right? May 23 '20 at 17:02