10
$\begingroup$

I've been stuck on the following problem for some time already. This is a problem that arose while I was studying some properties of boolean circuits (this is just for the anecdote, it should not matter here). I hope it's neither an entirely trivial question (as I've been unable to solve it myself) nor a too hard one.

Let $(n,k)$ be two integers, with $k \ll n$ (in the particular case I'm interested in, $n$ is a power of $2$ and $k = \log_2{n}$). Suppose that we are given $n$ subsets of $[n] = \{1, \cdots, n\}$, denoted $(S_1, \cdots, S_n)$, such that:

  • $\bigcup_{i=1}^n S_i = [n]$
  • For $i=1$ to $n$, $|S_i| \leq k$ (where $|\cdot|$ denotes the size of the set)

Is it possible to find $m \in O(n/k)$ subsets $(S'_1, \cdots, S'_m)$ of $[n]$ such that:

  • For $i=1$ to $m$, there is $J \subseteq [n]$ such that $S'_i= \bigcup_{j \in J} S_j$
  • $\bigcup_{i=1}^m S'_i = [n]$
  • For $i=1$ to $m$, $|S'_i| \in O(k)$

In other (intuitive) words, I have "too many subsets" ($n$), each subset being "small" (less than $k$ elements), which entirely cover $[n]$. Can I "regroup" them, using unions, into a smaller number ($m \in O(n/k)$) of subsets so that each new subset remains "not too big" ($O(k)$), but still the new subsets entirely cover $[n]$?

I've failed to get even a good intuition of the result I should expect. Although I've made my best to formulate it as a well-defined question, I'm in fact interested about whatever interesting can be said about it, especially in the setting $k = \log_2{n}$. If, for example, the answer is no and some counter example is found, then I'd be interested in knowing whether there is some natural characterization of the set $S_i$ for which sets $S'_i$ satisfying the above conditions can be found, or if one can get a yes answer by relaxing some bound (like, $m \in O((n\log\log n)/k)$, or $|S'_i| \in O(k\log k)$). More generally, if the question appears to be non-trivial, I'd be satisfied by an answer providing interesting insights even if it does not fully answer the question. Even relevant references would definitely help. Do not hesitate to tell me also if I've missed tags that relate to this question.

Thanks in advance :)

EDIT: I've done some research, and the problem shares many similarities with the set cover problem and the maximum coverage problem. However, these problems are concerned with the optimality of the solution, while I'm only asking for the existence of some (possibly non-optimal) solution that satisfy the given constraints. I'm currently trying to get some intuition of the result by looking at whether uniformly random subsets of $[n]$ of size $k$ would satisfy (with some reasonable probability) the constraints.

$\endgroup$
  • $\begingroup$ I'm afraid that however much effort you put into stating your question and offering a bounty, it has points where it's unclear and these prevent even starting an attempt at solution. Most importantly, it is out of its scope to apply the big O notation when $n$ and $k$ are constant. This is built for dependencies on $k$ (or $n/k$) as $k$ and $n$ grow to infinity, but your problem does not allow that because there's no algorithm how to build $S_i$ for different $n$ and $k$, just one predetermined starting point. $\endgroup$ – The Vee Nov 22 '16 at 14:25
  • $\begingroup$ The problem is indeed "trivial" when $k$ is a constant. I thought it was clear in the question that $k = k(n)$ is a function of $n$, and I mentionned that I'm especially interested in the case $k = \log{n}$. The question is broad because I've not made much progress on it - but if you have an answer for a well defined class of "starting points" sets $S_i$, I'd already be happy (I've made some progress not yet reported here on what can be expected on average for the case of random sets, but it's quite narrow) $\endgroup$ – Geoffroy Couteau Nov 22 '16 at 14:34
3
+100
$\begingroup$

My answer is very partial, but I decided that better this than nothing.

While thinking on your question, I was becoming more and more pessimistic, from an assertion “it is a simple combinatorial lemma” to a question “how can we obtain non-trivial advances?”. What means “non-trivial”, if even the relaxed question is actual? But we have a balance between $m$ and $|S_j’|$, that is grouping the family $\mathcal S=\{S_i\}$ into arbitrary groups consisting of $\Theta(k^\alpha)$ subsets we obtain $|S_j’|=O(k^{1+\alpha})$ and $m=\Theta(n/k^{\alpha}) $. So, in particular, we have a question can we improve an upper bound $|S_j’|=O(k^2)$ for $m=n/k$?

I started from the case $k=2$. We can proceed as follows. Let $\mathcal T$ be a maximal mutually disjoint subfamily of the family $\mathcal S$. The maximality of the family $\mathcal T$ implies that for each $S\in \mathcal S\setminus\mathcal T$ we can pick a set $f(S)\in\mathcal T$ such that $S\cap f(S)\ne\varnothing$. Fix an arbitrary enumeration of the family $\mathcal T$ and inductively for each $j\in [|\mathcal T|]$ put $\mathcal S_j=\{T_j\}\cup \{S\in\mathcal S\setminus\mathcal T: f(S)=T_j\}\setminus \bigcup_{j’=1}^{j-1}\mathcal S_{j’}$, $P_j=\bigcup\mathcal S_j$, and $n_j=| P_j |$. Then the sets $P_j$ are mutually disjoint and $[n]=\bigcup P_j$, so $\sum n_j=n$. Let $j$ be an arbitrary index. Since each element of the family $\mathcal S_j$ contains a points of a two-point set $T_j$, we can easily construct a cover $\mathcal C_j$ of the set $P_j$ by at most $n_j/2$ subsets, such that each of them is a union of at most two subsets from the family $\mathcal S_j$ and has size at most $3$. Taking a union of all covers $\mathcal C_j$ we obtain a cover of the set $[n]$ by $m\le\sum n_j/2=n/2$ subsets of size at most $3$. Unfortunately, proceeding by induction by $k$ from this point I can obtain, even in the luckiest case, a bound $|S_j’|\le k^2/2+O(k)$.

So I started to think about a counterexample. But it is hard for me to tell, how it would look and how to check it. I only have the following idea, which may yield (or not) some advance. Let $k\le \log_2 n$. Instead of subsets of $[n]$ I’ll consider the subsets of the group $\Bbb Z_n=\Bbb Z/n\Bbb Z$. Let $A=\{0,1,2,\dots, 2^{k-1}\}$ and for each $i\in\Bbb Z_n$ let $S_i=i+A$.

PS. I shared your question with some my coauthors, who may be interested in it and maybe together we'll be able to obtain some advances.

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot for your answer -- and thanks for sharing it! I'll look at the direction you suggest, searching for a counterexample too (I've also reached a point where I'm quite pessimistic about the answer that I can expect). $\endgroup$ – Geoffroy Couteau Nov 22 '16 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.