Institute of Information Science, Academia Sinica



Press Ctrl+P to print from browser

The Tuza constants of hypergraphs


The Tuza constants of hypergraphs

  • LecturerProf. Hung-Lung Wang (臺灣師範大學)
    Host: Meng-Tsung Tsai [@Tab]
  • Time2022-07-29 (Fri.) 10:00 – 12:00
  • LocationAuditorium107 at IIS new Building
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.
In this talk, we briefly review the techniques for deriving upper and lower bounds on $c_k$.