Edge cover in a regular uniform hypergraph

combinatorial-designscombinatoricsdiscrete optimizationgraph theoryhypergraphs

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$:

{49,50,51,52,53,54,55,56,57,58,59,60,61,62,63}
{37,38,39,40,41,42,43,44,45,46,47,48,61,62,63}
{25,26,27,28,29,30,31,32,33,34,35,36,61,62,63}
{13,14,15,16,17,18,19,20,21,22,23,24,61,62,63}
{1,2,3,4,5,6,7,8,9,10,11,12,61,62,63}
{10,11,12,22,23,24,34,35,36,46,47,48,58,59,60}
{7,8,9,19,20,21,31,32,33,43,44,45,58,59,60}
{4,5,6,16,17,18,28,29,30,40,41,42,58,59,60}
{1,2,3,13,14,15,25,26,27,37,38,39,58,59,60}
{1,2,3,16,17,18,31,32,33,46,47,48,55,56,57}
{4,5,6,13,14,15,34,35,36,43,44,45,55,56,57}
{7,8,9,22,23,24,25,26,27,40,41,42,55,56,57}
{10,11,12,19,20,21,28,29,30,37,38,39,55,56,57}
{7,8,9,13,14,15,28,29,30,46,47,48,52,53,54}
{10,11,12,16,17,18,25,26,27,43,44,45,52,53,54}
{1,2,3,19,20,21,34,35,36,40,41,42,52,53,54}
{4,5,6,22,23,24,31,32,33,37,38,39,52,53,54}
{4,5,6,19,20,21,25,26,27,46,47,48,49,50,51}
{1,2,3,22,23,24,28,29,30,43,44,45,49,50,51}
{10,11,12,13,14,15,31,32,33,40,41,42,49,50,51}
{7,8,9,16,17,18,34,35,36,37,38,39,49,50,51}

And the first five hyperedges cover all vertices: $\tau(H)=5$

Related Question