Tuesday, August 12, 2008

People in Germany

• 突然接到 Josef 的電話，他約我要一起跑步，時間剛好是中午一點左右，我才剛吃完飯。
• 老人上公車時，司機也是給它油門催下去，車上站立的乘客都差點跌倒，更不用說剛上車的老人會怎樣了。
• 辦公室舀糖的小湯持直接用來攪拌剛泡的咖啡，然後再放回糖包裡。
• 為了涼爽點，把門戶打開讓空氣對流，但是不把門卡好，結果走廊上辦公室的門一扇一扇「碰」一聲關上，他們也不以為意。
• 開車的時候，看到綠燈就往前衝，不會擔心垂直方向的來車。 (ps: 某位德國友人說，If I die, at least I am right.)

Too high sometimes

7:3 為甚麼看見你弟兄眼中有刺、卻不想自己眼中有梁木呢。
7:4 你自己眼中有梁木、怎能對你弟兄說、容我去掉你眼中的刺呢。
7:5 你這假冒為善的人、先去掉自己眼中的梁木、然後才能看得清楚、去掉你弟兄眼中的刺。

Sunday, August 10, 2008

Go Go Taiwan!!

Taiwan Go Go Go~~ 奧運代表隊加油！中華成棒隊加油！

Wednesday, August 06, 2008

Hereditary and semihereditary graph properties

Definition. A graph property P is semihereditary if there exists a hereditary graph property H such that the following hold:

Any graph satisfying P also satisfies H.
There is a function M: (0,1) -> N, such that any graph G of size at least M(ε), which is far from satisfying P, contains an induced subgraph that does not satisfy H.

Sunday, August 03, 2008

Testing colorability & hereditary graph properties

• J. Komlós: Covering odd cycles. Combinatorica 17 (1997) 393-400.
• N. Alon and M. Krevelevich: Testing k-colorability. SIAM J. Comput. 15 (2002) 211-227.
• E. Fischer: Testing graphs for colorability properties. Random Struct. Alg. 25 (2005) 289-309.
• N. Alon and A. Shapira: A characterization of the (natural) graph properties testable with one-sided error. SIAM J. Comput. 37 (2008) 1703-1727.
• N. Alon and A. Shapira: A characterization of easily testable induced subgraphs. Comb., Probab. Comput. 15 (2006) 791-805.

property testing 的結果已經多到嚇死人了！如果寫篇 survey paper 應該是不錯的貢獻，可是作者的功力可得要有相當的程度才行。

﻿
Let us say P is the set of n-vertex graphs that have vertex cover less than k. Then P is a hereditary property.

A monotone graph property is also a hereditary graph property.
(舊文)