The Lemmens-Seidel conjecture and forbidden subgraphs

問題與完整答案

本文研究固定共同角度 arccos(1/5) 的等角直線。取各線的單位代表向量，任兩不同向量的內積為 ±1/5。令 N₁/₅(r) 為 Rʳ 中此類直線的最大數，作者完整證明1973年的 Lemmens–Seidel 猜想：23≤r≤185 時 N₁/₅(r)=276；r≥185 時 N₁/₅(r)=⌊(3r−3)/2⌋。兩式在185維相接。這是固定角度的最大值，與允許任意角度的最大線數不同，也比「某配置已不能擴充」的飽和性更強。

幾何轉成譜與秩

Gram 矩陣可寫成 G=I+S/5，其中 Seidel 矩陣 S 的對角為0、非對角為±1。正半定條件等價於 λmin(S)≥−5，配置張成維數則是 rank(S+5I)。n>r 時 G 必奇異，故最小特徵值恰為−5。主定理敘述為：n≥277 時 rank(S+5I)≥⌊2n/3⌋+1。完整證明對所有可能的大系統分支實際提供較強的 rank≥2n/3+1；剩餘分支直接證明 n≤276。配合既有建構，就得到猜想中的精確最大值。

切換與真正剩下的情形

若以內積−1/5表示圖的邊，S=J−I−2A。反轉部分向量相當於切換圖中某個頂點集合與補集間的邊非邊，譜與秩不變。α([S])、ω([S]) 是整個切換類的最大獨立數與最大團數。交錯定理排除 K₇，故 ω≤6；ω=2、3、5、6 的情形已有足夠秩界。本文的新工具主要封住 ω=4，並逐步將可能反例壓到 α≤28。

禁子圖提供可計算的局部障礙

若一個誘導子圖的最小 Seidel 特徵值低於−5，則包含它的圖也不合法。作者使用這種極小禁子圖族 F₋₅ 中的一批成員，而非列舉全族。例如星圖 K₁,ᵣ 加 s 個孤點及 t 條獨立邊，當 r≥2、s+t≥1 時，合法的充要條件為 (r−4)(s+4t−4)≤36。K₁,₅ 加41個孤點使左側為37，因此被排除。此類簡單式來自 equitable quotient 與行列式。

從局部結構削減反例

誘導子圖 H 若有 adjacency 譜半徑大於2，完全不鄰接 H 的遠方 R(H) 就有譜半徑小於2，受到森林結構限制。利用這一點，作者先處理低最大度數、大獨立集及三角形自由圖。對 ω=4 的剩餘情形，再由大鄰域迫使小型禁子圖出現，先證 α≥39 已有秩界，接著改善到 α≥29。因此只需證明 ω=4、α≤28 的圖不可能超過276點。

四點基底與七個柱

選一個 K₄ 基底，按外點在基底的鄰接集合分柱，並利用切換辨認互補集合。外點分成四個一點柱與三個二點柱。空鄰接柱不存在，否則可切換成 K₅。用 S+5I 作為 Gram，將向量拆成基底投影與正交剩餘部分後，同一點柱的剩餘向量互相正交，平方長度為4；跨柱剩餘內積只有−4/3、2/3。這使柱的大小可由小型正半定矩陣限制。

19、68、20 三個關鍵數字

若兩個一點柱之間有邊，其餘每個一點柱至多19點。證明把對邊兩端的四種鄰接型計數化成行列式不等式，再利用整數性。另一方面，二點柱切換後與兩條獨立邊不相鄰，其柱圖三角形自由且獨立數≤26。禁子圖分析給柱大小≤68；若大小≥66，柱內每條邊兩端的度數和≤20。這些都是後續需要同時使用的限制，不能只保留68的點數上界。

gallery 讓不同柱互相制約

一條無共同鄰點的邊，其兩端共同非鄰點所誘導的圖稱為 gallery。在其中選另一條邊，可重新拆成兩個一點柱、一個二點柱和兩個端點。若 gallery 最大度數≤20，作者證明其大小κ≤105；若等號成立，還存在兩端度數都為20的邊。這個等號資訊十分重要，因為它能在重選基底後，把特定二點柱的大小從68降到65。

最終計數如何得到276

若任何基底的一點柱≥20，19界迫使其餘三柱聯集獨立，故 n≤4+2×28+3×68=264。否則所有一點柱≤19，gallery 最大度數≤20。若某 gallery 有105點，等號資訊使一個二點柱為65，四個gallery的計數給 n≤4×105/2+65=275；若全部≤104，同一計數式給 n≤4×104/2+68=276。這便排除最後的反例分支，完成整個猜想。

意義、數值與閱讀提醒

固定角度最大值在100維與185維均為276，186維為277，200維為298。證明的特色不是搜尋所有配置，而是用譜禁子圖、柱的局部界與gallery的全域計數逐層排除反例。來源：Meng-Yue Cao、Jack H. Koolen、Yen-Chi Roger Lin、Wei-Hsuan Yu，The Lemmens-Seidel conjecture and forbidden subgraphs，Journal of Combinatorial Theory, Series A 185（2022）。本導讀依 arXiv:2003.07511v1（2020年3月17日）全文，未宣稱重新執行原文全部計算。