TransWikia.com

Cover number and matching number in hypergraphs.

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?

One Answer

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:

enter image description here

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP