关于鸡尾酒会图的谱的技术问询：参考文献与特征值求解
Great questions! Let's break this down clearly—cocktail party graphs are a classic example of regular graphs with a clean, well-documented spectrum.
一、鸡尾酒会图的谱是什么？
首先明确定义：鸡尾酒会图（记为$CP(n)$）是包含$2n$个顶点的简单图，构造方式为在完全图$K_{2n}$中移除一个完美匹配（即$n$条互不相交的边，每条边配对两个顶点）。换句话说，每个顶点与除自身和唯一“搭档”顶点外的所有顶点相连，是$(2n-2)$-正则图（每个顶点的度数为$2n-2$）。
它的谱（邻接矩阵的特征值集合，含重数）为：
- 特征值$\boldsymbol{2n-2}$，重数为1：这是正则图的主特征值，等于顶点的度数；
- 特征值$\boldsymbol{n-2}$，重数为$2n-2$：占据谱的主要部分；
- 特征值$\boldsymbol{-2}$，重数为1：最小的特征值。
举个直观例子：当$n=2$时，$CP(2)$就是4顶点的环（$C_4$），其谱为$2,0,0,-2$，完全符合上述公式（$2n-2=2$，$n-2=0$，重数$2*2-2=2$，$-2$重数1）。
二、如何求解鸡尾酒会图的特征值？
我们可以利用图的结构和矩阵特征值的性质来推导，步骤如下：
构造邻接矩阵
将$2n$个顶点分成$n$对：$(v_1,u_1),(v_2,u_2),...,(v_n,u_n)$（每对是被移除的完美匹配边），鸡尾酒会图的邻接矩阵可表示为：
$$A = J_{2n} - I_{2n} - M$$
其中：- $J_{2n}$是$2n \times 2n$的全1矩阵；
- $I_{2n}$是$2n \times 2n$的单位矩阵；
- $M$是完美匹配的邻接矩阵（分块对角矩阵，每个块为$\begin{pmatrix}0 & 1 \ 1 & 0\end{pmatrix}$）。
基于已知矩阵的特征值推导
我们利用$J$、$I$、$M$的特征值性质，分三种情况计算$A$的特征值：情况1：全1特征向量$\mathbf{1}$
全1向量是$J_{2n}$的特征向量（特征值$2n$）、$I_{2n}$的特征向量（特征值1）、$M$的特征向量（特征值1，因为$M\mathbf{1}=\mathbf{1}$）。代入$A$得：
$$A\mathbf{1} = 2n\mathbf{1} - \mathbf{1} - \mathbf{1} = (2n-2)\mathbf{1}$$
由此得到特征值$2n-2$，重数1。情况2：与$\mathbf{1}$正交且满足$M\mathbf{x}=\mathbf{x}$的向量
这类向量是形如$(1,1,-1,-1,0,...,0)^T$的线性组合（分量和为0，且在完美匹配下保持不变）。对于这类向量，$J_{2n}\mathbf{x}=0$（与全1向量正交），$I_{2n}\mathbf{x}=\mathbf{x}$，代入得：
$$A\mathbf{x} = 0 - \mathbf{x} - \mathbf{x} = -2\mathbf{x}$$
由此得到特征值$-2$，重数1（仅存在1个线性无关的此类向量与$\mathbf{1}$正交）。情况3：与$\mathbf{1}$正交且满足$M\mathbf{x}=-\mathbf{x}$的向量
这类向量是形如$(1,-1,0,...,0)^T$的线性组合（分量和为0，且在完美匹配下被翻转）。对于这类向量，$J_{2n}\mathbf{x}=0$，$I_{2n}\mathbf{x}=\mathbf{x}$，代入得：
$$A\mathbf{x} = 0 - \mathbf{x} - (-\mathbf{x}) = (n-2)\mathbf{x}$$
此类向量构成的空间维度为$2n-2$，对应特征值$n-2$的重数。
三、相关参考文献
如果需要更严谨的证明和深入的背景，这些权威资料值得参考：
- Algebraic Graph Theory（Chris Godsil & Gordon Royle）：这本教材详细讨论了鸡尾酒会图及其谱，同时覆盖了正则图特征值计算的通用方法；
- Graph Spectra（Andries Brouwer & Willem Haemers）：关于图谱的综合性参考书籍，在部分章节中将鸡尾酒会图称为“超八面体图”并给出详细分析；
- Handbook of Combinatorial Mathematics（Volume 2）：汇总了特殊图的关键性质，包含鸡尾酒会图的谱特征总结。
内容的提问来源于stack exchange，提问作者Vahid
