Title: On the independence number of sparser random Cayley graphs Show Chinese title

Title: 关于更稀疏的随机Cayley图的独立数

Abstract: The Cayley sum graph $\Gamma_A$ of a set $A \subseteq \mathbb{Z}_n$ is defined to have vertex set $\mathbb{Z}_n$ and an edge between two distinct vertices $x, y \in \mathbb{Z}_n$ if $x + y \in A$. Green and Morris proved that if the set $A$ is a $p$-random subset of $\mathbb{Z}_n$ with $p = 1/2$, then the independence number of $\Gamma_A$ is asymptotically equal to $\alpha(G(n, 1/2))$ with high probability. Our main theorem is the first extension of their result to $p = o(1)$: we show that, with high probability, $$\alpha(\Gamma_A) = (1 + o(1)) \alpha(G(n, p))$$ as long as $p \ge (\log n)^{-1/80}$. One of the tools in our proof is a geometric-flavoured theorem that generalises Fre\u{i}man's lemma, the classical lower bound on the size of high dimensional sumsets. We also give a short proof of this result up to a constant factor; this version yields a much simpler proof of our main theorem at the expense of a worse constant. Show Chinese abstract

Abstract: 集合 $A \subseteq \mathbb{Z}_n$ 的Cayley和图 $\Gamma_A$ 被定义为具有顶点集 $\mathbb{Z}_n$，并且在两个不同顶点 $x, y \in \mathbb{Z}_n$ 之间存在一条边当且仅当 $x + y \in A$。 格林和莫里斯证明了，如果集合$A$是$\mathbb{Z}_n$的一个密度为$p = 1/2$的$p$-随机子集，那么$\Gamma_A$的独立数以高概率渐近等于$\alpha(G(n, 1/2))$。 我们的主要定理是对他们的结果首次推广到$p = o(1)$：我们证明了，在高概率下，当$p \ge (\log n)^{-1/80}$成立时，有$$\alpha(\Gamma_A) = (1 + o(1)) \alpha(G(n, p))$$。 我们在证明中使用的一个工具是具有几何风味的定理，该定理推广了 Freĭman 引理（经典高维和集大小的下界）。 我们还给出了这个结果的一个简短证明，误差在常数因子范围内；这一版本以更差的常数值为代价，为我们主要定理提供了一个更为简单的证明。