On the Fractional Covering Number of Hypergraphs

Abstract

The fractional covering number$\tau^*$ of a hypergraph $H = ( V, E )$ is defined to be the minimum possible value of $\sum_{x \in V} t( x )$ where t ranges over all functions $t : V \to \mathbb{R}$ which satisfy $\sum_{x \in e} t ( x ) \geqq 1$ for all edges $e \in E$. In the case of ordinary graphs G, it is known that $2\tau^* ( G )$ is always an integer. By contrast, it is shown (among other things) that for any rational $p/q\geqq 1$, there is a 3-uniform hypergraph H with $\tau^* ( H ) = p/q$.