中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

超圖的 Tuza 常數

:::

超圖的 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$上界與下界所使用的技巧。