超圖的 Tuza 常數
- 講者王弘倫 教授 (National Taiwan Normal University)
邀請人:蔡孟宗 - 時間2022-07-29 (Fri.) 10:00 ~ 12:00
- 地點資訊所新館107演講廳
摘要
對一超圖 $H$,其橫截 (transversal) 為一點子集,滿足與任一邊之交集非空。最小橫截之元素個數為 $H$ 之橫截數(transversal number),以 $[@BackSlash]tau(H)$ 表示。Tuza 常數定義為 $[@BackSlash]sup [@BackSlash]tau(H)/(m + n)$,其中 $H$ 為 $k$-均勻超圖,$m$ 與 $n$ 分別為 $H$ 的邊數與點數。在此演講中,我們將簡短回顧推導 $c_k$上界與下界所使用的技巧。