Mathematics Asked by Josh Ng on January 17, 2021
Given a 3-uniform hypergraph $H=(V, E),$ the matching number $nu(H)$ is the maximum number of pairwise-disjoint edges in $E(H) .$ The cover number $tau(H)$ is the size of the smallest set of vertices $A subseteq V(H)$ such that for every edge $e in E(H)$ we have $e cap A neq emptyset .$ Prove that for all 3-uniform hypergraphs $H, tau(H) leq 3 nu(H)$.
From the description the two numbers sound like the same thing to me? i.e. we can select a vertex from each edge in the maximal set of pairwise-disjoint edges to obtain $tau(H)$ (so we actually have $tau(H) leq nu(H)$). Am I missing something here?
It is possible that taking one vertex from each of the edges of a matching does not form a vertex cover.
Consider the following example:
This has $tau = 2$ and $nu = 1$, since all edges pairwise intersect, but there is no single vertex that is contained in each edge.
Correct answer by Brandon du Preez on January 17, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP