Upper bounds on the Tuza constants
- 講者王弘倫 教授 (國立臺灣師範大學資訊工程學系)
邀請人:蔡孟宗 - 時間2023-08-08 (Tue.) 16:00 – 18:00
- 地點資訊所新館106演講廳
摘要
For a hypergraph $H$, the transversal is a subset of vertices whose intersection with every edge is nonempty. The cardinality of a minimum transversal is the transversal number of $H$, denoted by $[@BackSlash]tau(H)$. The Tuza constant $c_k$ is defined as $[@BackSlash]sup{[@BackSlash]tau(H)/ (m+n)}$, where $H$ ranges over all $k$-uniform hypergrpahs, with $m$ and $n$ being the number of edges and vertices, respectively. The upper bounds on $c_k$ can be obtained by a kind of linear programs, in which the numbers of variables are different. In this talk, we give an analysis of how good the bound can be achieved based on the linear programming approach.