组合数学中的组合谱 组合谱是组合数学中研究离散结构（如图、复形、超图）特征值分布的工具，它将线性代数中的谱理论应用于组合对象，揭示其对称性、连通性和代数性质。 基本概念：从图的邻接矩阵出发 考虑一个简单图 \( G = (V, E) \)，其邻接矩阵 \( A \) 满足 \( A_ {ij} = 1 \) 当且仅当顶点 \( i \) 与 \( j \) 相邻，否则为 0。矩阵 \( A \) 的特征值集合称为图的 谱 （spectrum）。例如，完全图 \( K_ n \) 的谱包含一个特征值 \( n-1 \)（重数 1）和特征值 \( -1 \)（重数 \( n-1 \)）。 正则图的谱性质 若图是 \( d \)-正则的（每个顶点度数为 \( d \)），则最大特征值为 \( d \)，且所有特征值满足 \( |\lambda_ i| \leq d \)。第二大的特征值 \( \lambda_ 2 \) 控制图的扩展性（expansion property）：\( \lambda_ 2 \) 越小，图越接近完全图，连通性越强。 拉普拉斯矩阵的谱 图的拉普拉斯矩阵定义为 \( L = D - A \)，其中 \( D \) 为度对角矩阵。\( L \) 的特征值均为非负实数，最小特征值恒为 0，对应全 1 向量。第二小特征值 \( \mu_ 2 \)（代数连通度）反映图的连通程度：\( \mu_ 2 > 0 \) 当且仅当图连通。 组合谱的推广：超图与复形 对于超图或单纯复形，可定义高阶拉普拉斯算子（如 Hodge Laplacian）。例如，对单纯复形，其 \( k \)-维拉普拉斯矩阵的零空间维数等于 \( k \)-维同调群的维数，从而将谱与拓扑不变量关联。 应用：等谱问题与结构判定 等谱图（谱相同但不同构）的存在表明谱不能完全确定结构，但谱能反映某些组合性质，如通过特征值界限判定色数、独立数等。例如，Hoffman界指出：若图的最小特征值为 \( \lambda_ {\min} \)，则色数 \( \chi(G) \geq 1 - \frac{\lambda_ {\max}}{\lambda_ {\min}} \)。 前沿方向：高维扩展子 高维扩展子（high-dimensional expanders）利用高阶拉普拉斯算子的谱间隙定义，推广了图的扩展性，在误差校正码和拓扑数据分析中有重要应用。