# The product of the clique and independence numbers in the Cayley sum graph

For a finite abelian group $G$ and a subset $S\subseteq G$ with $0\in S=-S$, let $$\alpha(S):=\max\{|A|\colon(A-A)\cap S=\varnothing\}$$ and $$\omega(S):=\max\{|A|\colon A-A\subseteq S\}.$$ These quantities are the independence number and the clique number, respectively, of the Cayley graph induced by $S$ on $G$. Since Cayley graphs are vertex-transitive, we have $$\alpha(S)\omega(S)\le |G|. \tag{*}$$

Let now $$\alpha^+(S):=\max\{|A|\colon(A+A)\cap S=\varnothing\}$$ and $$\omega^+(S):=\max\{|A|\colon A+A\subseteq S\}.$$ Is there an analog of the estimate ($*$) for these quantities (maybe, a somewhat weaker one, or with some "restrictions apply" etc.)?

• @MikhailTikhomirov: Well, not necessarily as far as I can see. If $S$ is not generating, then the graph is not connected, but this does not affect anything.
– Seva
Oct 16 '17 at 16:04
• If $S$ is allowed to not generate $G$, then we may take $G = \mathbb{Z}_{3n}$, $S = \{3x \in G\}$, then $\alpha^+(S) \geq n$ for $A = \{3x + 1 \in G\}$, and $\omega^+(S) \geq n$ for $A = S$. I am not sure which conditions you should require to make it past this example. Oct 16 '17 at 16:08
• In the previous comment, we may even add 1 to $S$, so that the new $S$ generates $G$ and the same estimates hold. Oct 16 '17 at 16:15
• @MikhailTikhomirov: Good example, but rather specialized (a large subgroup involved); so, I still hope somewhat of the sort I was asking could be true.
– Seva
Oct 16 '17 at 16:21
• Another example is $G = \mathbb{Z}_p$ with prime $p$, where for $S = [\lceil p / 2 \rceil, p - 1]$ we have $\alpha^+(S) \geq p / 4$ with $A = [0, \lfloor p / 4 \rfloor]$, and $\omega^+(S) \geq p / 4 - 1$ with $A = [\lceil p / 4 \rceil, \lfloor p / 2 \rfloor]$. In this case $G$ is simple. Oct 16 '17 at 17:12

If the set $S$ is arbitrary, then no strong variant of $(*)$ holds unless $G$ has order $2$.
Indeed, consider a factorization of $G$, and suppose there is a factor $H \sim \mathbb{Z}_n \neq \mathbb{Z}_2$. Let $S$ be the set of all elements of $G$ such that their projection on $H$ is at least $n / 2$. But then $\alpha^+(S) \geq \frac{n - 1}{4n}|G|$ for $A = [0, \lfloor (n - 1) / 4 \rfloor]$. Also, $\omega^+(S) \geq \frac{\max(1, n / 4 - 3 / 2)}{n}|G|$ for $A = [\lceil n / 4 \rceil, \lfloor (n - 1) / 2 \rfloor]$. We can see that both $\alpha^+(S), \omega^+(S) = \Omega(|G|)$, hence LHS of $(*)$ can be $\Omega(|G|^2)$, which is only a constant away from the trivial $|G|^2$ bound.
If $G \sim \mathbb{Z}_2^k$, then $G$ has order 2, and $(*)$ does hold since addition and subtraction are the same thing.