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

看板Math作者hcsoso (索索)時間13年前 (2012/12/13 14:02)推噓3(3推 0噓 5→)

留言8則, 3人參與討論串3/4 (看更多)

如同 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

12/13 14:12, , 1^F

12/13 14:12, 1^F

※ 編輯: hcsoso 來自: 50.129.128.114 (12/13 14:14)

→

hcsoso

12/13 15:13, , 2^F

12/13 15:13, 2^F

推

TassTW

12/14 02:32, , 3^F