均勻超圖的譜

均勻超圖的譜

SPECTRA OF UNIFORM HYPERGRAPHS

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

摘要

我們提出了一種均勻超圖的譜理論，該理論與譜圖理論緊密平行。建立在經典工作之上的眾多最新進展，使人們對“對稱超行列式”（即多維數(shù)組）有了豐富的理解。對稱超行列式與行列式有許多共性，但多重線性代數(shù)的背景遠比解決譜圖理論（即普通矩陣）所需的線性代數(shù)復雜得多。盡管如此，仍可以通過特征多項式以及變分法來定義超矩陣的特征值。我們將這一概念應用于均勻超圖的“鄰接超矩陣”，并證明了譜圖理論中若干基本結果的自然類比。目前仍存在大量未解問題，我們提出了若干進一步研究的方向。

1. 引言

譜圖理論是組合數(shù)學、計算機科學和社會科學中一個被廣泛研究且高度適用的學科。廣義上講，人們首先將圖的結構編碼在一個矩陣 M M 中，然后探究圖的性質與 M M 的特征值或奇異值之間的聯(lián)系。已有工作研究了“鄰接矩陣”，以及源自圖的其他矩陣：“（組合）拉普拉斯矩陣”、“無符號拉普拉斯矩陣”、“歸一化拉普拉斯矩陣”、“二部鄰接矩陣”、“關聯(lián)矩陣”等（參見 [4, 11, 14, 15]）。一個自然的研究途徑是將譜技術推廣到超圖，盡管在這方面已知的結果明顯匱乏。文獻中已有嘗試定義超圖的特征值并研究其性質，取得了一定程度的成功。著名的例子包括 [10, 16, 18, 23, 27]。這些工作大多關注圖的拉普拉斯譜的推廣，與我們后續(xù)討論的主題有著截然不同的風格。

遺憾的是，試圖簡單地將鄰接矩陣的譜理論推廣到超圖會立即遇到嚴重障礙。由于超邊由兩個以上的頂點指定，沒有明顯的方法來定義超圖的鄰接矩陣。對于 k k-均勻超圖，可以得到一個直接的推廣，即得到一個 k k 階數(shù)組（本質上是一個張量），但這樣做就失去了用于分析它的強大而精密的線性代數(shù)工具。另一種與 k k 維數(shù)組策略相關的策略是將特征值視為一個方程組的同時消失，該方程組中的每個方程都包含參數(shù) λ λ，其中特征值是那些使方程組有解的 λ λ。這推廣了矩陣特征值是含參數(shù) λ λ 的線性方程組消失這一概念。

最近的工作 [9, 17, 22, 24, 26] 提供了一些框架和工具來分析這種高維數(shù)組，我們廣泛利用這些發(fā)展來定義和分析我們的超圖特征值。我們獲得了一系列與經典譜圖理論結果緊密平行的結果，包括最大特征值的界、色數(shù)的譜界，以及特征多項式系數(shù)的子超圖計數(shù)描述。我們還描述了一些自然超圖類和運算的譜，包括不相交并、笛卡爾積、 k k-部圖、 k k-柱體（超立方體的推廣）和完全超圖。

最近的工作利用了我們描述的超圖特征值的變體，獲得了關于超圖中最大團 [6]、基于超圖產生的圖中的團 [7] 以及偶均勻超圖的連通性性質 [20] 的結果。我們?yōu)檫@一系列工作添加了許多關于超圖特征值的基本結果。我們的許多結果采用了特征值的代數(shù)刻畫，這在超圖研究中一直未被充分利用。此外，我們對某些超圖類的特征值（在某些情況下還有特征向量）的刻畫給出了幾類我們現(xiàn)在已經了解其譜的超矩陣。我們希望這項工作能為進一步研究對稱超矩陣的特征值提供基礎。

論文的其余部分組織如下。在第 2 節(jié)中，我們給出對稱超矩陣特征值的定義和背景，包括變分和代數(shù)公式。在第 3 節(jié)中，我們定義了 k k-均勻超圖的鄰接超矩陣，并推導了譜圖理論許多核心結果的超圖推廣。第 4 節(jié)探討了幾種“常見”超圖的譜：完全圖、笛卡爾積、 k k-柱體等。第 5 節(jié)概述了大量進一步研究的方向。

1. 對稱超矩陣的特征值

在本節(jié)中，我們回顧對稱超矩陣特征值的定義和基本性質。這些定義和結果大多出現(xiàn)在 [9, 17, 22, 24, 26] 及其參考文獻中；我們在此收集它們是為了方便讀者，并為后續(xù)章節(jié)建立符號體系。

Qi ([26]) 和 Lim ([22]) 提出了對稱矩陣特征值向高階對稱（甚至非對稱）超矩陣情形的幾種推廣。我們采用 [26] 中的以下定義。

其中收縮是對 A A 除第一個指標外的所有指標進行的。我們主要避免使用張量術語，而是使用多項式進行研究，盡管為了簡潔起見，我們有時會使用上述符號。

利用上述定義（及其一些推廣），已經使用變分或解析技術完成了大量工作，包括函數(shù)正定的條件以及佩龍-弗羅貝尼烏斯型定理 ([9, 17, 22])。我們依賴這些結果，但更多地借鑒了 Qi 在 [26] 中提出的代數(shù)方法，該方法使用了代數(shù)幾何中稱為結式（resultant）的構造。我們將簡要介紹該構造的背景及其一些有用性質。

2.1. 多元多項式結式。 兩個單變量多項式（或者等價地，兩個雙變量齊次多項式）的結式是一種經典構造，用于判斷這兩個多項式是否有公共根。它可以通過多種方式定義和計算，包括兩個多項式的所謂“西爾維斯特矩陣”（Sylvester matrix）的行列式。另一方面，如果我們在 n n 個變量中有 n n 個線性形式，系數(shù)矩陣的行列式告訴我們這些形式何時有公共非平凡零點。多元多項式結式是一種將這兩個概念統(tǒng)一在一個框架下的構造。希望深入了解該主題的讀者可以在 Gelfand 等人 [19] 的著作中找到關于結式及其推廣的高度代數(shù)化的論述；那些尋求不那么專業(yè)化且更具算法化方法的讀者可以參考 Cox 等人 [13] 的著作。

我們重述兩個給出關于結式重要事實的定理。關于這些結果的證明，請參見 [19]。首先是結式的存在性和（在適當歸一化后）唯一性。

1. 一般超圖譜

我們首先證明一個關于多項式方程組結式的更一般的引理，該方程組可以看作是兩個不相交系統(tǒng)的并集。然后，該定理的證明只是這個引理的一個簡單應用。

原則上，人們可以對任意固定的均勻度 k k 和固定的余次數(shù) d d 進行類似的計算，以確定哪些 k k-價多重子圖在 d d 條邊上被計數(shù)，以及以何種重數(shù)計數(shù)。在實踐中，即使對于適中的均勻度和余次數(shù)值，計算也會變得非常繁瑣。相反，我們希望能為 k k-圖找到一種類似于圖情形的刻畫，即在圖的情形中，系數(shù)根據(jù)秩 [4] 對“半等價”（sesquivalent）子圖進行計數(shù)。這種刻畫幾乎肯定取決于對對稱超行列式更好的理解。

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 次單位根下是不變的。

其根在乘以任意三次單位根下是對稱的。

值得一提的是，如果將該定理的陳述弱化為關于作為集合而非多重集的譜，則可以使用解析方法輕松證明。

。。。。。。。。

原文鏈接：https://people.math.sc.edu/cooper/spectraofhypergraphs.pdf