推 hcsoso :有趣! 我知道的方法是純組合的... 12/15 01:49
推 hcsoso :不等等, 我發現他們基本上是同樣的東西. 我到你個版 12/15 06:21
→ hcsoso :寫好了, 在這邊似乎離題了! 12/15 06:22
推 herstein :寫的認真給推XD 12/15 06:49
推 TWN2 :推塔神! 12/15 10:02
推 turboho :原po正妹 12/19 03:10
※ 引述《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
既然是這個的話我剛好知道一些表現理論在其中的應用,
也就是由 finite abelian group 做出的 cayley graphs 不可能是個 expander family
因為我們能證:
1. {Cay(Gn,Sn)} is expander <=> Kazhdan constant K(Gn,Sn) 的 inf > 0
其中 K(G,S) = min inf max ||ρ(s)v - v||
irrep ρ ||v||=1 s in S
如果 G 的 irreducible representations 都是一維,
那麼 K(G,S) = min max |ρ(s)-1|
ρ S
2. 若 G 是 finite abelian group, 則 K(G,S) ≦ 2π/(|G|^(1/d) - 1)
其中 d = |S|
所以如果
{Cay(Gn,Sn)} 是個 expander family,
by definition |G_n| 要趨近無限大,
導致 K(G_n,S_n) 趨近 0, 與 inf K(G_n,S_n) > 0 矛盾
====
1. 來自兩個 Kostant constant 的估計
2. 倒是意外的很基礎, 只要簡單的代數導論和群表現:
(proof)
有限交換群基本定理告訴我們 G 同構於 direct sum of cyclic groupa Z/n_i Z
所以 G 的 irreducible representations 就是
ρ_k: Z/n_1 Z⊕...⊕Z/n_r Z → C ; k = (k_1,...,k_r)
( a_1, ..., a_r) |→ Πe^{i2πk_ ia_i/n_i}
也就是說
* G 的 irreducible representations 總數 = |G|
* 因為 |S| = d, 令 S = {s_1, ... , s_d}, 所以 ρ(s_i) = e^iθ for some θ
微積分告訴我們 |e^iθ-1| ≦ |θ|
所以就剩下分析 K = min max{|Argρ(s_i)|}
ρ i
因此可以定一個 map
Irrep(G) → [0,2π]^d
ρ |→ (Argρ(s_1), ..., Argρ(s_d))
注意到 K ≦ 2π/(|G|^(1/d) - 1) <=> |G|^(1/d) - 1 ≦ 2π/K
所以我們只需要證 |G| ≦ c^d, 其中 c := ┌2π/K┐,
也就是說我們可以把弧度 [0,2π] 切成 c 段, [0,2π]^d 切成 c^d 段
反設 |G| > c^d,
那麼因為鴿籠原理(!), 必定有不同的 irrep φ, φ' 落在同一段,
也就是 |Arg φ(s_i) - Arg φ'(s_i)| < 2π/c
實際檢驗, 會發現 ρ(g):=φ(g)/φ'(g) 給出一個 irreducible repn,
並且 |Argρ(s_i)| = |Arg φ(s_i) - Arg φ'(s_i)| < 2π/c
所以 K = min max{|Argρ(s_i)|} ≦ 2π/c , 也就是 c ≦ 2π/K
但是這與 c := ┌2π/K┐ 矛盾, Q.E.D.
--
在馬橋，與「他」近意的詞還有「渠」。
區別僅在於「他」是遠處的人，相當於那個他； 我想找的是他，但只能找到渠。
「渠」是眼前的人，近處的人，相當於這個他。 我不能不逃離渠，又沒有辦法忘記他。
馬橋語言明智地區分他與渠，指示了遠在和近在的巨大差別。
指示了事實與描述的巨大差別，局外描述與現場事實的巨大差別。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.104.25.4