# Upper bound for size of minimal covers of a set

Would appreciate any insight about the following regarding set covers:

Begin with a universe set $$X = \{x_1,x_2,...,x_n\}$$ and a set $$S=\{s_1, s_2,...,s_p\}$$ such that each $$s_i \subseteq X$$ and $$\bigcup S = X$$. Consider the task of finding all inclusion-minimal covers of $$X$$. (Covers are inclusion-minimal if the removal of any subset $$s_i$$ from the cover destroys its coverage property.)

Given the set of inclusion-minimal covers $$C=\{c_1, c_2, ... c_m\}$$, what is an upper bound for $$\max|c_i|$$, that is, the largest inclusion-minimal cover? It seems fairly straightforward to show that one upper bound is $$|X|$$ (that is, an inclusion-minimal cover will contain at most the same number of subsets as there are elements in $$X$$ itself).

But can a better bound be found?

Additional information: No restrictions are assumed for $$S$$. The bound would ideally be expressed in terms of one or more properties of $$S$$ (in whatever form those might take).

A conjecture: If $$\min |s_i| = k$$, then $$\max |c_i|$$ (the size of the largest inclusion-minimal cover) is bounded above by $$|X| - k + 1$$. This is based upon two observations:

(1) In constructing any inclusion-minimal cover, we start with any element from $$S$$ (call it $$s_{1'}$$). As $$s_{1'}$$ covers a particular subset of elements from $$X$$, the next added cover element (call it $$s_{2'}$$) must cover at least one new element from $$X$$ not covered by $$s_{1'}$$.

(2) If $$\min |s_i| = k$$, then we can choose the first element $$s_{1'}$$ in our cover to have size $$k$$. This leaves $$|X| - k$$ elements in $$X$$ left uncovered. By the first observation, each additional $$s_i$$ must cover at least one new element in $$X$$, so we can add at most $$|X| - k$$ additional elements to the cover, leading to a cover size at most $$|X| - k + 1$$.

As noted in the comments, this type of bound might not be significantly smaller than $$|X|$$ itself. However, I am hoping to use this in a combinatorial context, so any savings helps. Even smaller bounds would still be useful.

• What parameters do you want the bound to be in terms of? Certainly it's at most $|X|$ and at most $|S|$. Is there some other parameter of particular interest? – D.W. Jan 4 '20 at 3:21
• both bounds from @D.W. are tight. An example is $S:=\{\{x\};x \in X\}$. – narek Bojikian Jan 4 '20 at 3:23
• It might be an interesting question to find such a bound when the sets in $S$ have a fixed size. However, in the current formulation you can't say much about the bounds. – narek Bojikian Jan 4 '20 at 3:28
• @D.W. It would have to based on some property of $S$ (or the individual $s_i$) but I wouldn't know how to be more specific than that at this point. For instance, perhaps it's the case that if we have $|s_i| \geq 2$ for all $i$, (that is, there are no subsets that contain only a single element from $X$) then the bound is actually less than $|X|$. – Robert Rovetti Jan 4 '20 at 5:19
• @narekBojikian The sets in $S$ are not necessarily constrained to have a fixed size, although that is an interesting sub-case. I'd hope that whatever computation for the bound would be based on exactly those sorts of properties about $S$ (for instance, if the size of the sets in $S$ are themselves bounded, does that allow us to say something about the bound of $\max |c_i|$. – Robert Rovetti Jan 4 '20 at 5:24

The trivial bounds are that $$|c| \le |X|=n$$ and $$|c| \le |S|=p$$.
Knowing bounds on the sizes of the sets $$s_i$$ doesn't help much. For instance, consider the family of sets $$s_1,\dots,s_{n-k+1}$$ given by $$s_i=\{i,n-k+2,\dots,n-1,n\}$$. These sets are all of size $$k$$, and yet the largest inclusion-minimal cover has size $$n-k+1$$, i.e., exactly equal to the trivial bound of $$|S|$$ and fairly close to the trivial bound of $$|X|$$. So, knowing only the sizes of the sets does not help to provide upper bounds that are much better than the trivial ones.
• With the $|S|$ in this example, it appears that $|S| = n-k+1$, which is equivalent to the value of the trivial bound $|S|=p$....unless I'm reading this wrong? – Robert Rovetti Jan 4 '20 at 20:10