均匀超图的谱|代数|多项式|定理|方程组|特征值|行列式|超图

均匀超图的谱

SPECTRA OF UNIFORM HYPERGRAPHS

https://people.math.sc.edu/cooper/spectraofhypergraphs.pdf

摘要

我们提出了一种均匀超图的谱理论，该理论与谱图理论紧密平行。建立在经典工作之上的众多最新进展，使人们对“对称超行列式”（即多维数组）有了丰富的理解。对称超行列式与行列式有许多共性，但多重线性代数的背景远比解决谱图理论（即普通矩阵）所需的线性代数复杂得多。尽管如此，仍可以通过特征多项式以及变分法来定义超矩阵的特征值。我们将这一概念应用于均匀超图的“邻接超矩阵”，并证明了谱图理论中若干基本结果的自然类比。目前仍存在大量未解问题，我们提出了若干进一步研究的方向。

引言

谱图理论是组合数学、计算机科学和社会科学中一个被广泛研究且高度适用的学科。广义上讲，人们首先将图的结构编码在一个矩阵 M M 中，然后探究图的性质与 M M 的特征值或奇异值之间的联系。已有工作研究了“邻接矩阵”，以及源自图的其他矩阵：“（组合）拉普拉斯矩阵”、“无符号拉普拉斯矩阵”、“归一化拉普拉斯矩阵”、“二部邻接矩阵”、“关联矩阵”等（参见 [4, 11, 14, 15]）。一个自然的研究途径是将谱技术推广到超图，尽管在这方面已知的结果明显匮乏。文献中已有尝试定义超图的特征值并研究其性质，取得了一定程度的成功。著名的例子包括 [10, 16, 18, 23, 27]。这些工作大多关注图的拉普拉斯谱的推广，与我们后续讨论的主题有着截然不同的风格。

遗憾的是，试图简单地将邻接矩阵的谱理论推广到超图会立即遇到严重障碍。由于超边由两个以上的顶点指定，没有明显的方法来定义超图的邻接矩阵。对于 k k-均匀超图，可以得到一个直接的推广，即得到一个 k k 阶数组（本质上是一个张量），但这样做就失去了用于分析它的强大而精密的线性代数工具。另一种与 k k 维数组策略相关的策略是将特征值视为一个方程组的同时消失，该方程组中的每个方程都包含参数 λ λ，其中特征值是那些使方程组有解的 λ λ。这推广了矩阵特征值是含参数 λ λ 的线性方程组消失这一概念。

最近的工作 [9, 17, 22, 24, 26] 提供了一些框架和工具来分析这种高维数组，我们广泛利用这些发展来定义和分析我们的超图特征值。我们获得了一系列与经典谱图理论结果紧密平行的结果，包括最大特征值的界、色数的谱界，以及特征多项式系数的子超图计数描述。我们还描述了一些自然超图类和运算的谱，包括不相交并、笛卡尔积、 k k-部图、 k k-柱体（超立方体的推广）和完全超图。

最近的工作利用了我们描述的超图特征值的变体，获得了关于超图中最大团 [6]、基于超图产生的图中的团 [7] 以及偶均匀超图的连通性性质 [20] 的结果。我们为这一系列工作添加了许多关于超图特征值的基本结果。我们的许多结果采用了特征值的代数刻画，这在超图研究中一直未被充分利用。此外，我们对某些超图类的特征值（在某些情况下还有特征向量）的刻画给出了几类我们现在已经了解其谱的超矩阵。我们希望这项工作能为进一步研究对称超矩阵的特征值提供基础。

论文的其余部分组织如下。在第 2 节中，我们给出对称超矩阵特征值的定义和背景，包括变分和代数公式。在第 3 节中，我们定义了 k k-均匀超图的邻接超矩阵，并推导了谱图理论许多核心结果的超图推广。第 4 节探讨了几种“常见”超图的谱：完全图、笛卡尔积、 k k-柱体等。第 5 节概述了大量进一步研究的方向。

对称超矩阵的特征值

在本节中，我们回顾对称超矩阵特征值的定义和基本性质。这些定义和结果大多出现在 [9, 17, 22, 24, 26] 及其参考文献中；我们在此收集它们是为了方便读者，并为后续章节建立符号体系。

Qi ([26]) 和 Lim ([22]) 提出了对称矩阵特征值向高阶对称（甚至非对称）超矩阵情形的几种推广。我们采用 [26] 中的以下定义。

其中收缩是对 A A 除第一个指标外的所有指标进行的。我们主要避免使用张量术语，而是使用多项式进行研究，尽管为了简洁起见，我们有时会使用上述符号。

利用上述定义（及其一些推广），已经使用变分或解析技术完成了大量工作，包括函数正定的条件以及佩龙-弗罗贝尼乌斯型定理 ([9, 17, 22])。我们依赖这些结果，但更多地借鉴了 Qi 在 [26] 中提出的代数方法，该方法使用了代数几何中称为结式（resultant）的构造。我们将简要介绍该构造的背景及其一些有用性质。

2.1. 多元多项式结式。 两个单变量多项式（或者等价地，两个双变量齐次多项式）的结式是一种经典构造，用于判断这两个多项式是否有公共根。它可以通过多种方式定义和计算，包括两个多项式的所谓“西尔维斯特矩阵”（Sylvester matrix）的行列式。另一方面，如果我们在 n n 个变量中有 n n 个线性形式，系数矩阵的行列式告诉我们这些形式何时有公共非平凡零点。多元多项式结式是一种将这两个概念统一在一个框架下的构造。希望深入了解该主题的读者可以在 Gelfand 等人 [19] 的著作中找到关于结式及其推广的高度代数化的论述；那些寻求不那么专业化且更具算法化方法的读者可以参考 Cox 等人 [13] 的著作。

我们重述两个给出关于结式重要事实的定理。关于这些结果的证明，请参见 [19]。首先是结式的存在性和（在适当归一化后）唯一性。

一般超图谱

我们首先证明一个关于多项式方程组结式的更一般的引理，该方程组可以看作是两个不相交系统的并集。然后，该定理的证明只是这个引理的一个简单应用。

原则上，人们可以对任意固定的均匀度 k k 和固定的余次数 d d 进行类似的计算，以确定哪些 k k-价多重子图在 d d 条边上被计数，以及以何种重数计数。在实践中，即使对于适中的均匀度和余次数值，计算也会变得非常繁琐。相反，我们希望能为 k k-图找到一种类似于图情形的刻画，即在图的情形中，系数根据秩 [4] 对“半等价”（sesquivalent）子图进行计数。这种刻画几乎肯定取决于对对称超行列式更好的理解。

4. 特殊超图的谱

4.1. 一般 k k-部超图。 如果 k k-图 H H 的顶点可以被划分为 k k 个集合，使得每条边恰好从每个集合中使用一个顶点，则称 H H 为 k k-部的，或称为 k k-柱体（ k k-cylinder）。最著名的情况是 2-柱体，即二部图。关于二部图的以下刻画有几种证明（参见 [4, 15]）。

定理 4.1.图 G G 是二部图当且仅当其多重集谱关于原点对称。

该定理可以重述为：图是二部图当且仅当其（多重集）谱在乘以任意二次单位根的作用下是不变的。我们将此推广到 k k-柱体。

定理 4.2. k k-柱体的（多重集）谱在乘以任意 k k 次单位根下是不变的。