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 耶...
好吸引人喔，要不要搬過去呢？

SP-graph succinct encoding

這是學姊最近在做的問題：

對於一個 n-node 的 SP-graph，
有沒有一個 encoding 的方法能做到 4n+o(n)?

在想這個問題的過程，
發現 unlabeled unordered tree 好像還沒有低於 2n+o(n) 的 encoding!

說不定這是一個可以想的方向？

ISAAC 2009

ISAAC 2009 Accepted Papers

實驗室上了兩篇！

Tai-Hsin Hsu and Hsueh-I Lu, An Optimal Labeling for Node Connectivity
Tsung-Hao Liu and Hsueh-I Lu, Minimum Cycle Bases of Weighted Outerplanar Graphs

恭喜~~

O(n^8) time algorithm for even-hole-free graph recognition!!!

我想出來了！
先把 cap-free 跟 triangle-free 的 structure 弄好，
重要的觀察：wheels in triangle-free cleaned graphs are cutsets!
透過 tracking 穿過 decompositions，
然後再對 extended line tree 作量身打造的 O(n+m) algorithm，
就完成了！

hope that everything is correct:]

--

Woops, 時間計算有點錯誤，
decomposition 也要乘上 O(mn)!!
這樣最多可能要到O(n^8)...
除非 2-join 可以處理？

Subgrpah of a hypercube II

直接轉貼自己 Math 板上的文章~

目前找到最好的 citation:

Embedding trees in a hypercube is NP-complete,
A Wagner, DG Corneil - SIAM Journal on Computing, 1990

換句話說，對於一棵樹 T 要判斷是不是 n-cube 的子圖是一件很難的事...
更不用說對於一般圖 A 了。

不過，對於可以放進一個 n-cube 的圖，已經有人證明了 iff conditions:

B-valuations of graphs,
I Havel, J Moravek - Czech. Math. J, 1972

例如 trees 都可以放進 n-cube 中。

最後是一篇 survey:

Embeddings in Hypercubes,
M Livingston - 1988

不過，考慮 dilation 跟 expension 好像就有一些好的演算法？
但這波研究已經過去了，我想是大家已經覺得 well-known 了吧:]

那個 iff condition 可以研究看看...
看起來不乾淨:S

Subgraph of a hypercube

PTT Math 板上出現了有趣的問題~~

"Given an n-node graph G with |V(G)| \leq 2^n, with deg(x) \leq n for all node x,
for what condition we can say that G is a subgraph of a hypercube Q_n?"

Pretty interesting question...
We know that labeling may help,
and G must be bipartite and K_{2,3}-free,
maybe I'll think about it tomorrow :S

And an algorithm for subgraph isomorphism problem in bipartite graphs?

Playground Opening!!

遊樂場開門啦，先來個開山宗旨吧XD

「本遊樂場提供各類離散數學及資訊理論相關學術研究的資訊，
歡迎各界人士遊玩以及發表意見！」

為了符合宗旨，
首先就來個連結吧(笑)

The Status of the P Versus NP Problem

簡單來說，這可是所有在讀資訊理論的人的終極目標啊！
即使遙不可及，也應該約略了解一下:]