動機
在固定基礎集的所有子集中,若要求所選子集兩兩互不包含,最多可以選出多少個?選取全部相同大小的子集顯然可行。中間大小的子集最多,這暗示存在一個最優答案,但混合不同大小的子集是否不可能做得更好,並不顯然。
Dilworth 定理把反鏈的大小與某個劃分的最優值等同起來,但它本身並不能算出子集偏序集的寬度。這裏我們利用子集所具有的額外對稱性:每個排列都生成一條由嵌套子集構成的完整鏈。統計某個被選中的子集落在多少條這樣的鏈上,會對小集合與大集合賦予不同的權重。這種加權計數既證明了極值上界,也給出了對含有多個秩的集族的有用限制。
定義
定義 6.3.1
(布爾層與反鏈集族)
對 ,記 ,並以包含關係為 賦予偏序。其第 層 由所有 元子集組成,故 。若集族 中任意兩個不同成員互不包含,則稱 為反鏈。定義它的 Lubell 權重為
每個分母中的二項式係數都是正數。當 時,基礎集為空,布爾(Boole)偏序集只有一個元素,即空子集。
布爾偏序集中的一條極大鏈恰含每個大小從零到 的子集各一個。它由每一步添加一個新的基礎集元素得到,所以這樣的鏈恰有 條。這裏「極大」指它在該偏序集內不能再被延長;布爾偏序集的極大鏈都具有最大可能的大小 。在一般的偏序集中,這兩種含義不必一致。
定義 6.3.2
(一層的上影)
對 與 ,其上影為
它記錄了在反鏈中選取 的某個成員之後,下一層中被禁止選取的所有集合。多個成員可能禁止同一個下一層集合,因此關聯次數不能當作互不相同的上影成員來計數。
定理/命題
定理 6.3.3
(LYM 不等式)
對每個反鏈 ,
不要求集族限於單獨一層。空集族的權重為零。
定理 6.3.4
(Sperner 的最優上界與取等情形)
中的每個反鏈的大小至多為 。完整的中間層可達到該上界。若 為偶數,則這是唯一的最大反鏈;若 為奇數,則僅有的最大反鏈是兩個完整的中間層。
定理 6.3.5
(歸一化的上影不等式)
對 與 ,
該不等式比較的是相鄰兩層中所佔的比例,並不是說它們的原始基數總是按同一方向排序。
證明思路或證明
證明
(在極大鏈上計數成員)
統計由 的成員 與包含它的極大鏈所組成的對。若 ,則生成該鏈的排列必須先把 的元素放在前面(順序任意),再把其餘元素放在後面(順序任意),共有 種選擇。另一方面,每條極大鏈至多包含反鏈的一個成員。因此
兩邊除以 即得 LYM 不等式,其中包括大小為零與大小為 的端點情形。
證明
(雙重計數直接包含關係)
對於上影不等式,統計滿足 、 且 的對 。每個被選中的 元集恰有 個直接上集,而每個上影成員至多包含 個被選中的 元集。因此
再利用 ,即得歸一化形式。
證明
(由權重上界到最優上界及其取等情形)
二項式係數之比 表明,最大的層大小為 :當 為偶數時取在一個中間秩,當 為奇數時取在兩個中間秩。因此任何反鏈的每個成員對其權重的貢獻至少為 。於是 ,這就證明了大小上界。每個中間層本身是反鏈,所以該上界可以取到。
若等號成立,則每個成員都必須位於最大的層上,因為位於較小層的成員的貢獻嚴格大於 。當 為偶數時,只有一個秩的大小為 ,所以該集族必為整個中間層。這也涵蓋了 的情形。
當 為奇數時,考慮 與 之間的二分包含圖。兩部分的大小都是 ,且每個頂點的度數都是 。該圖是連通的:任意兩個 元集可以這樣連接起來——反覆把一個不在目標集中的元素替換為目標集中缺少的元素,每次替換都經過二者共同的 元並集。每個上層頂點都有下層鄰點,所以這些路徑連通了整個圖。當 時,該圖就是一條邊。
它的下半部分的每個非空真子集 ,其鄰點個數嚴格多於 自身的大小。先由邊的計數得到鄰點個數至少與之相等。若兩者相等,則鄰點集上的每條邊都已來自 ,而 上的每條邊又都留在該鄰點集之內,它們就構成一個完整的連通分支,與圖的連通性矛盾。現在,一個最大反鏈由下部分 和避開其上影的上部分組成,其大小至多為
非空真子集的下部分會使這個值小於 。因此下部分必須為空,或者是整個下層;要達到 ,另一部分也相應地被確定。這就證明了奇數情形的取等分類。
證明透視
不可比性、單峰性與連通性在哪裏進入
三個事實各有分工。鏈計數給每個秩為 的成員代價 ;反鏈假設恰好只使用一次:沒有極大鏈同時經過兩個成員。關於集族的其他性質一概沒有用到。二項式係數的單峰性把代價轉化為大小:每個代價至少為 ,所以 。取等迫使每個不等式都取等號,從而把每個成員固定在大小為 的層上; 為偶數時論證到此結束。 為奇數時兩層並列,需要另一個想法:大小為 的混合集族需要一個非空真子集 使 。包含圖兩邊度數都是 的正則性只給出 ;排除混合集族所需的嚴格不等式來自連通性。
例題詳解
例題 6.3.6
(六個二元子集構成四元集上的最大集族)
的六個二元子集構成一個反鏈。每個的權重為 ,總和為一。極大鏈共有 條,每個二元子集屬於其中 條。這六組關聯恰好覆蓋全部 條鏈,每條鏈各含唯一的一個二元成員。Sperner 定理證明不存在更大的反鏈;偶數情形的取等結論說明,這個完整的層是唯一大小為六的集族。
例題 6.3.7
(可行的權重預算未必能實現給定的秩分佈)
在 上,設反鏈含有四個單元素集與 個二元子集。LYM 給出 ,故 。但實際的包含限制更強。重新標號後,這四個單元素集為 。任何二元子集都必須避開這四個元素,而只剩下元素五,這是不可能的。因此 。權重不等式只是必要條件,並不是對每個給定的秩分佈都能據以構造的充分規則。
例題 6.3.8
(上影解釋了混合中間各秩時的損失)
在 上,設 為含有元素一的四個二元子集。它的上影是含有一的六個三元子集。兩個中間層都有十個元素,所以歸一化後的大小分別為 與 。二元成員恰為這四個二元子集的反鏈至多能再加入上影之外的四個三元子集,因而大小至多為八。透過混合這些選擇,無法達到最優值十。從被選中的二元子集出發的關聯數為十二;每個上影三元子集包含其中兩個,這就解釋了實際上影成員為六個。
同一證明的期望形式
取一個均勻隨機的排列,並列出它的各個前綴子集。對於固定的子集,同一秩的所有集合作為前綴集出現的可能性相同。因此它出現的概率是該層大小的倒數。令一個隨機變量統計該鏈所遇到的所選集族的成員個數。它的期望值是這些出現概率之和,恰好就是 Lubell 權重。
對於反鏈,該變量始終至多為一,所以其期望至多為一。這與前面是同一個有限計數證明,只是用概率的語言表達,並不是對集族另作隨機輸入的假設。各個出現事件不必相互獨立。事實上,兩個不同的反鏈成員不可能同時出現在一條鏈上,正是這種依賴性使上界成立。
這一觀點有助於理解權重。小的子集落在所有極大鏈中相對較大的一部分上,因為它所在的層選擇很少。因此它比位於寬闊中間層的子集消耗更多的鏈預算。最優化比較的正是這些代價,而不是假設每個集合使用相同的資源。
上影的增長能說明甚麼,不能說明甚麼
歸一化不等式說明,當一個層上的集族被換成它的整個上影時,所佔的比例不會下降。集合的個數是否增加,則取決於兩層的相對大小。在中間層以下,下一層至少一樣大,所以上影的基數至少與原來相同。在中間層以上,較小的下一層可能含有更少的集合,即使它佔該層的比例變大。
例如,取三元基礎集的全部三個二元子集。它們的上影只是整個三元集。基數從三降為一,而兩個歸一化比例都等於一。丟掉分母,就會把正確的歸一化命題變成錯誤的、關於基數的普遍性斷言。
證明先按重數統計關聯,再對互不相同的鄰點個數進行估計。關聯上界中取等,要求每個上影成員都含有盡可能多的被選中前驅。在奇數維布爾偏序集並列的中間層上,連通性使這一點極其苛刻。正是這一額外限制,使混合的集族無法悄悄地達到與完整一層相同的極值大小。
概念視角組合
對極大鏈的覆蓋,而不是格的圖示
被選中的子集佔據經過它的每一條極大鏈。不同的反鏈成員佔據互不相交的鏈集合,所以它們歸一化後的佔有量之和至多為整個鏈集合。這一解釋依賴於全部極大鏈及其精確個數;一幅小的 Hasse 圖中可見路徑的條數並不是所要求的樣本空間。
究竟解決了哪個極值問題?
Sperner 定理計算的是布爾偏序集的寬度。隨後 Dilworth 定理保證它的全部子集可以劃分為同樣數目的鏈。LYM 證明中使用的極大鏈一般並不是這樣的劃分:它們大量重疊,只是作為一個對稱的檢驗鏈族來計數。混淆鏈的這兩種用途,會使論證聲稱得到了一個它從未構造過的不交分解。
常見錯誤
(包含意義下極大不等於最大)
證明所涉及的也是最大的大小,而不僅僅是包含意義下極大的反鏈。一個無法再接受另一個子集的集族仍可能很小。例如,只含空子集的集族是包含意義下極大的,因為其他每個子集都包含它,但當基礎集至少有兩個元素時,它比中間層小。這並不矛盾:極大只是禁止一步擴張,而最大則是在所有集族之間比較。
常見錯誤
反例模式
LYM 不等式並不蘊含互不可比
在 上,集族 的權重為 ,但它的兩個成員是可比的。正確的方向是:反鏈蘊含該不等式。僅有數值不等式不能證明反鏈性質,也不能用它代替對包含關係的檢驗。
常見錯誤
(空基礎集仍有一個子集)
不要認為空基礎集沒有子集:它有空子集。當 時, 只有一個元素,所以最大反鏈是 ,大小為 。若把 當作空集,上界就會變成 ,偶數情形的取等結論也隨之失效。
常見錯誤
(上影只看上一層,而非所有上集)
要區分下一層的上影與所有嚴格上集:上影證明中的關聯度數依賴於恰好添加一個元素。在 上,單元素集 的上影是 ,共兩個集,正好等於度數 。它的嚴格上集還包括 ;若把該集也計入,關聯計數 就不再成立。
總結
對極大鏈的關聯計數,證明了每個布爾反鏈所受的加權限制。最大的秩把它轉化為 Sperner 的最優大小上界,而當兩個中間秩並列時,上影擴張與連通性給出取等的分類。歸一化的上影不等式保留了原始基數比較可能丟失的資訊。
練習
快速檢查
(列出三元基礎集上的所有最大反鏈,並說明該列表是完整的。)
兩個中間秩並列,因此使用已證明的取等分類。
解答 · 答案
最優大小為 。由奇數情形的取等結論,達到該大小的集族只有全部三個單元素集與全部三個二元子集。二者的確都是反鏈,所以兩種情形都會出現。混合不同秩的集族可以是反鏈,但無法達到這個大小。
快速檢查
(若六元基礎集上的某個反鏈含有一個二元成員,證明它的大小至多為十九。)
利用該成員較大的權重。不要聲稱所得上界一定能夠達到。
解答 · 答案
最大的層有 個成員,而所選的二元成員的權重為 。若集族的大小為 ,則其餘每個成員的權重至少為 。於是 ,即 。由於 是整數,。這是在額外條件下的上界,並不是達到十九的構造。
快速檢查
(在五元基礎集上,選取三個單元素集。精確計算它們的上影,並與歸一化上影下界比較。)
統計至少含有一個所選元素的二元子集。
解答 · 答案
二元子集共有 個。恰有一個避開全部三個所選元素:由兩個未選元素構成的二元子集。因此上影含有九個二元子集。歸一化不等式只給出上影大小至少為 。這個嚴格的差距反映出,大多數上影二元子集所含的所選單元素集,比關聯上界中允許的兩個要少。