2
$\begingroup$

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.)?

$\endgroup$
8
  • 2
    $\begingroup$ @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. $\endgroup$
    – Seva
    Oct 16 '17 at 16:04
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 16 '17 at 16:08
  • 1
    $\begingroup$ In the previous comment, we may even add 1 to $S$, so that the new $S$ generates $G$ and the same estimates hold. $\endgroup$ Oct 16 '17 at 16:15
  • 1
    $\begingroup$ @MikhailTikhomirov: Good example, but rather specialized (a large subgroup involved); so, I still hope somewhat of the sort I was asking could be true. $\endgroup$
    – Seva
    Oct 16 '17 at 16:21
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 16 '17 at 17:12
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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