Upper bounds on the Tuza constants
- LecturerProf. Hung-Lung Wang (Department of Information Engineering, National Taiwan Normal University)
Host: Meng-Tsung, Tsai - Time2023-08-08 (Tue.) 16:00 ~ 18:00
- LocationAuditorium 106 at IIS new Building
Abstract
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.