论文标题
$ \ mathbb {z} _2^{n} $的Cayley图的单一签名和感应子图
Unitary Signings and Induced Subgraphs of Cayley Graphs of $\mathbb{Z}_2^{n}$
论文作者
论文摘要
让$ g $为基础Abelian $ 2 $ -Group $ \ Mathbb {z} _2^{n} $相对于尺寸$ d $的集合$ S $。我们证明，对于任何此类$ g，s $和$ d $，在任何一套以上的顶点的任何引起的子图中的最高度至少为$ \ sqrt d $。这是从黄（Huang）最近的突破性结果推论出来的，他证明了上述$ n $ -hypercube $ q^n $，其中一组发电机$ s $是所有锤子重量$ 1 $的向量的集合。通过他的方法，我们定义并研究了图的邻接矩阵的统一签名，并将其与黄的正交签名进行比较。作为副产品，我们回答了Belardo等的最新问题。 al。关于签名$ 5 $的规范图的范围。
Let $G$ be a Cayley graph of the elementary abelian $2$-group $\mathbb{Z}_2^{n}$ with respect to a set $S$ of size $d$. We prove that for any such $G, S$ and $d$, the maximum degree of any induced subgraph of $G$ on any set of more than half the vertices is at least $\sqrt d$. This is deduced from the recent breakthrough result of Huang who proved the above for the $n$-hypercube $Q^n$, in which the set of generators $S$ is the set of all vectors of Hamming weight $1$. Motivated by his method we define and study unitary signings of adjacency matrices of graphs, and compare them to the orthogonal signings of Huang. As a byproduct, we answer a recent question of Belardo et. al. about the spectrum of signed $5$-regular graphs.
