Mobius Transformations!!

Mobius Transformations,
PSL_2(C) acts on C by

f(z) = (az+b)/(cz+d)

代數作業老師還真敢出！
不過，能夠把它的各種性質真真實實算出來的感覺...
還是挺棒的(笑)

Current Research Projects

這也是今天 Senior Seminar 的報告主題...
順便來統計一下吧！
--
Main Attack:
Even/Odd holes in graphs, and related topics (skew partitions, perfect graphs)

Swap Disks:
Intersection represetation of plane graphs (with pishen)
Grid embedding of planar graphs

Minor issues:
Max cut (with coldestegg)
k-connected subgraphs (with coldestegg)

Surveys:
Geometric Complexity Theory
Algebraic Graph Theory
--
在研究上真是貪心...
廣博不忘專精！

Tools on planar graphs

Just make a note...
--
Klein's Spanner,
Lipton-Tarjan's Separator,
    Miller's Cycle Separator,
    Goodrich's Separator Decomposition Tree,
Schnyder's Realizer,
de Fraysseix-Pach-Pollack & Kant's Canonical Ordering,
Chiang-Lin-Lu's (My Teacher!!) Orderly Spanning Tree,
Yannakais' Four Page Embedding,
--
more to come!!

帽子戲法

網路上看到兩個有趣的帽子問題:]
--
1. 有 10 個人排了一條隊，每人頭上都有一頂黑色或者白色帽子。每個人只可以看到排自己前面的人所穿帽子的顏色，而且他們均不能看到自己帽子的顏色。

現在有一個公証人，他會向每個人問一條問題：「你自己的帽子是甚麼顏色？」他會順序由排最後的人問到排最前的人。每個人只可以回答：「黑色」或「白色」，而每個人回答時，其他人都是可以聽到他的答案的。

這 10 個人可以事先商量怎樣回答，以確保答對的次數最多。問：他們可以確保答對多少次？怎樣可以達到？

2. 監獄裏有 n 個囚犯。有一日，皇上要跟這 n 個囚犯玩一個遊戲。皇上會選出 n 種顏色。獄長會在每一個囚犯頭上戴上一頂帽子，每頂帽子的顏色是這 n 種顏色之一。帽子的顏色並無其他限制，所以可能每個囚犯的帽子顏色都相同，亦有可能每個囚犯的帽子顏色均不同的。

每個囚犯都可以看到其他囚犯的帽子，唯獨是不可以看到自己的帽子。現在，囚犯們要同一時間向獄長交一張紙，上面寫上他們猜測自己帽子的顏色。當然，這樣子就是說囚犯們不會看到其他囚犯的猜測了。

皇上說如果有任何一個囚犯答對了，就釋放所有囚犯；否則，全部囚犯都要處死。這些囚犯可以事先商量怎樣回答，以確保他們一定能夠被釋放？問：他們怎樣達到目的？
--
第二題比較難，不過蠻有趣的!!

SODA 2010

SODA 2010 Accepted Papers
好快！
--
總覺得，看著大師或是專家們的 blog ，
好像學到的東西不會比 paper 少(笑)

來跟幾個 blog 好了！

An efficient bijection between Jacobian of a graph and spanning trees

Article Here

看到這種結果...
都只能大叫

太漂亮了！！！

然後默默覺得自己能力還差好遠好遠...
--
即使不是成為發現者，
也許目標是像 West 一樣，
成為好的教學者！

Encoding unordered tree and SP-graph in optimal length

哈哈，結果跟老師一討論，好像很簡單的 separator 就可以做到 optimal 了，
不管 optimal 是多少XD (好像是在 1.58n 左右？)
SP-graph 就用他的 decomposition tree 的 separator 就可以了，
應該會一對一對應:]

果然簡單的問題早就被做光了XD
--
看到幾個有趣的 blog ，(像是 Lipton 的)
Wordpress 可以用 LaTeX 耶...
好吸引人喔，要不要搬過去呢？