Timeline for The product of the clique and independence numbers in the Cayley sum graph
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 17, 2017 at 3:45 | vote | accept | Seva | ||
| Oct 17, 2017 at 1:37 | answer | added | Mikhail Tikhomirov | timeline score: 1 | |
| Oct 16, 2017 at 20:19 | comment | added | Fedor Petrov | In general, if $S$ and $S+2t$ do not intersect for certain element $t$, any large set $A$ for which $A+A\subset S$ gives you equally large $B=A+t$ such that $(B+B)\cap A=\emptyset$. | |
| Oct 16, 2017 at 19:07 | comment | added | Seva | @MikhailTikhomirov: Pretty convincing. How about combining these observations into an answer? | |
| Oct 16, 2017 at 17:12 | comment | added | Mikhail Tikhomirov | 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, 2017 at 16:21 | comment | added | Seva | @MikhailTikhomirov: Good example, but rather specialized (a large subgroup involved); so, I still hope somewhat of the sort I was asking could be true. | |
| Oct 16, 2017 at 16:15 | comment | added | Mikhail Tikhomirov | 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, 2017 at 16:08 | comment | added | Mikhail Tikhomirov | 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, 2017 at 16:04 | comment | added | Seva | @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. | |
| Oct 16, 2017 at 16:00 | comment | added | Mikhail Tikhomirov | Since you're talking about Cayley graphs, $S$ should generate $G$, shouldn't it? | |
| Oct 16, 2017 at 15:51 | history | asked | Seva | CC BY-SA 3.0 |