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

Improve this question
$\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
    Commented Oct 16, 2017 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$
    – Mikhail Tikhomirov
    Commented Oct 16, 2017 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$
    – Mikhail Tikhomirov
    Commented Oct 16, 2017 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
    Commented Oct 16, 2017 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$
    – Mikhail Tikhomirov
    Commented Oct 16, 2017 at 17:12

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .