Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a hypergraph $H$, we define $\tau (H)$ to be the minimum-vertex-cover number of $H$. That is, the size of the smallest $C \subseteq V(H)$ such that $C$ meets all edges in $E(H)$. A quite natural expansion to that definition is to allow to take fractions of vertices. So similiraly, we can define $\tau ^ \star (H)$ to be the $\min {\{\Sigma_ {v\in V}{f(v)}\ \vert \ f:V \rightarrow \mathbb {R^+}, \ \forall e \in E(H):\ \Sigma _{v \in e}f(v) \geq 1\}} $.

Consider then the following $k$-uniform hypergraph: Take the cycle-graph $C_n$ and make every path with $k$ points in it (a $k$ lengthed segment on the cycle) an edge in the hypergraph. Take all these edges but leave one out (they are symmetrical, it doesn't matter which). We arrive at a $k$-uniform hypergraph $H_{n,k}$ with $n$ vertices and $n-1$ edges.

For every $n,k$ find $\tau^\star (H_{n,k}). $

Note 1: It's very easy to see that for the full $k$-cycle hypergraph (without removing 1 edge) we get $\tau^\star=n/k$ by taking $1/k$ for all vertices. Obviously by removing a single edge we wish to improve this bound.

Note 2: For $k=1$ (edges are singletons) we get $\tau^\star=n-1$ by taking 1 for every edge except the missing one.

Note 3: If $k\geq 2$ and $k\vert n$ then it's clear that we cannot get anything better than $n/k$ since we can always fully partition the cycle into $n/k$ edges and each edge must have weight of at least $1$.

Note 4: If $k=n-1$ then there exists an edge on which all edges meet. So we can easily get $\tau^\star=1$ by putting 1 on that vertex.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.