Let $H = (V,E)$ be a $15$-uniform hypergraph. That is, every edge contains exactly $15$ vertices. Suppose $|V| = 63$ and $|E| = 21$. Moreover, assume that every vertex is contained in exactly $5$ edges ($5$-regular), and that the pairwise intersection of any two edges is exactly $3$ elements.
An edge cover of $H$ is a subcollection $\mathcal{E}\subset E$ such that every vertex of our hypergraph is contained in some edge of $\mathcal{E}$. Let $\tau(H)$ be the minimum number of edges required to form an edge cover of $H$.
I would like to show that $\tau(H) \geq 9$. Using the probabilistic method, I was able to show that $\tau(H)\leq 11$, which does not contradict this statement, and hence I'm inclined (and want) to believe that my claim is true. This is a question that came up while investigating a number-theoretic problem, which I will not elaborate on for the sake of clarity.
Can someone either suggest some ideas on how one might prove this, or give an example of a hypergraph satisfying those constraints, so that I may run the minimum set cover algorithm on said example to convince myself?
Best Answer
It is not true. Here are the $21$ hyperedges of such a hypergraph $H$:
And the first five hyperedges cover all vertices: $\tau(H)=5$