Re: [中學] 排列組合 (一路領先的應用)

[hcsoso (索索)]

如同 TassTW 板友所說,
Catalan number 的確與 expander graph 有關.


--- expander graphs ---
什麼是 expander graphs?  就是那些擁有良好"擴展"性質的圖.
這些圖自 1970 年來被數學家以及資訊理論學家研究的十分透徹,
從它們的存在, 建構, 以及應用的研究,
到發現它們能被組合, 機率, 代數, 以及幾何的語言及方法處理,
造就它們獨特的地位.

(最近上 Complexity theory, 滿滿的都是 expander...
看似完全不相關的問題用 expander 就都解掉了 @@)

要說簡介的話, Hoory, Linial, and Wigderson 的 survey 可說是必讀.
http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf


--- 定義與性質  ---
定義上, 假設我們有一張 d-regular 的圖,
他的 adjacency matrix 的最大 eigenvalue 一定是 d,
而它的第二大 eigenvalue λ 與圖的擴展性質大有關係:

    性質.  若 S 為點子集, |S| <= |V(G)| / 2,
           則 S 與 V(G)-S 之間的邊數 >= (d-λ)|S| / 2.

因此, 第一大跟第二大的 eigenvalue 之間的 gap 大小,
決定了圖的擴展性質好壞.


--- 最好的 expander graph? ---
到底一個 d-regular graph 可以是多好的 expander?
換句話說, λ 到底可以小到什麼程度?

Alon 與 Boppana 給出了 λ 的下界:

    定理.  λ >= 2(d-1)^0.5 - o(1).

注意 2(d-1)^0.5 可不是什麼隨便的數字,
它可是 infinite d-regular tree (也就是究極的 expander) 的 spectral radius.

怎麼證明這個定理呢?  我們在這邊證明一個特例,
當最小的 eigenvalue λn 滿足 |λn| <= |λ|.

首先我們考慮圖的 adj. matrix A 的行為.  注意

    trace A <= d + (n-1)λ,

如果我們能得知 A 的 trace 的話, 也許我們就可以給出一些下界;
不幸的是, A 的 trace 是 0, 我們得到無聊的 bound.
但是這是為什麼呢?  是因為 trace of A 其實是圖中每個點從自己出發,
走一步之後走回自己的方法數和; 這當然是零!

不過我們可以換考慮

    trace A^{2k} <= d^{2k} + (n-1)λ^{2k},

然後想辦法計算 trace A^{2k}.
但這當然正好是每個點從自己出發, 走 2k 步後回到原點的方法數和!

然後我們不難看出這個數量會大於等於 |V(G)| 倍的
"從一棵 infinite d-regular tree 的頂點出發, 走 2k 步後回到頂點" 的數量.
後者是什麼?  當然是 Catalan number! 不過我們要小心處理往上走與往下走的不同,
總共有 Catalan(k) * d * (d-1)^{k-1} 種方法.

經過計算之後, 我們就得到了 λ >= 2(d-1)^0.5 - o(1).  Yay!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 50.129.128.114
推 WINDHEAD    :先推再看
※ 編輯: hcsoso          來自: 50.129.128.114       (12/13 14:14)
→ hcsoso      :我突然想到, 這是不是當初張鎮華老師的代數圖論上過?
推 TassTW      :我那年代數圖論沒教這個
→ TassTW      :他是要講 interlacing 和 connectivity bound
→ hcsoso      :我記不太得了, 不過我當年好像是跟你上同一門課...
→ hcsoso      :我記得是用 spectra of graphs 對吧
※ 編輯: hcsoso          來自: 192.17.182.214       (12/14 02:47)
推 TassTW      :ya, spectrum 就是 A 的 eigenvalues
→ TassTW      :不過我那時不認識你 xDDDDDD