7
$\begingroup$

Consider $k$ sets $S_1, S_2, \ldots, S_k$, of the following properties:

  • For every $i$, $\left|S_i\right| = p$
  • For every pair of $i$ and $j$, $\left|S_i \cap S_j\right| = \frac{p}{2}$

Now I need to find the minimum of $\left|\bigcup S_i\right|$ in terms of $k$ and $p$.

(Assume $p$ is large enough to be divisible by any small enough integers)

Via trial and error I suspect the answer to be $$\frac{\left(2^{m + 1} - 1\right)p}{2^m}$$ where $m = \lfloor\log_2 k\rfloor$, but cannot prove it.

That's also why I give that assumption about $p$, so that one do not need to worry about the situation where $\frac{p}{2^m}$ is not an integer.


Edition: actually, I verified that my suspected answer is wrong. For example, when $k = 5$, I managed to construct the sets using $\frac{5p}{6}$ elements. Now I am not sure what the actual answer should be. :(


Correction: I think I had mistaken $p$ with another variable I used in a larger problem where this proof is required, when giving the $\frac{5p}{6}$ lower bound in the edition above. It should be $\frac{5p}{3}$.

An example would be when $k = 5$ and $p = 6$ (to be divisible by both $2$ and $3$), then my $5$ sets would be $$\left\{1, 2, 3, 4, 5, 6\right\}, \left\{1, 2, 3, 7, 8, 9\right\}, \left\{1, 4, 6, 7, 9, 10\right\}, \left\{2, 4, 5, 7, 8, 10\right\}, \left\{3, 5, 6, 8, 9, 10\right\}$$ using $10$ elements. They are obtained basically as I try to "average" the occurrences of each number (in this example, specifically, letting each number appear $3$ times). Maybe we can go from here, but how to prove in general that this average is reachable?

$\endgroup$
4
  • $\begingroup$ Equivalent problem: find smallest $n$ such that there exists a $n \times k$ boolean matrix $A = [\mathbf{c}_1\ \mathbf{c}_2\ \dots \ \mathbf{c}_k]$ such that for all $i$ we have $\mathbf{1}^T\mathbf{c}_i = p$, and for each pair of columns $\mathbf{c}_i, \mathbf{c}_j$ we have $\mathbf{c}_i^T \mathbf{c}_j = p/2$. Explanation: $n$ is the universe $|\cup S_i|$, each column is a set encoded by a binary yes/no for each element in the universe whether it's included in the set. $\endgroup$ – orlp Sep 19 '18 at 10:54
  • $\begingroup$ I'm skeptical of your $\frac{5p}{6}$ construction. What does it construct for $p = 4$? The minimum solution I can find has $|\cup S_i| = 7$, and my solver says no solution exists for $|\cup S_i| = 6$, whereas you claim it can be done in $4$ (assuming we round up). My solution is $$\{2, 3, 4, 5\}, \{3, 5, 6, 7\}, \{1, 2, 3, 7\}, \{1, 3, 4, 6\}, \{1, 4, 5, 7\}$$. $\endgroup$ – orlp Sep 19 '18 at 11:55
  • $\begingroup$ It is impossible to get $\frac{5p}6$ since $|\bigcup_i S_i|\ge |S_1|=p$. Also, if you want us to help you, do not withhold information. Tell us about the construction you found, and why you suspected your original guess. $\endgroup$ – Mike Earnest Sep 19 '18 at 17:56
  • $\begingroup$ @MikeEarnest Sorry I made a mistake in the edition. I have fixed it and provided a construction for the minimum I suspected. Please see correction in the problem body. The original guess related to powers of $2$ was made by trying out the best way of adding a $4^\text{th}$ set onto an optimal $3$ sets containing the least total elements, but it seems that this method is already shown incorrect anyways. $\endgroup$ – Beanandbean Sep 20 '18 at 6:38
0
$\begingroup$

Some estimation:

Let $$M:=\bigcup S_i = \{1,2,...,n\}$$ Let $d_i$ be a number of sets that $i\in M$ is in them. Then we have $$\sum_{i=1}^n d_i =k\cdot p$$ and $${k\choose 2}{p\over 2} = \sum _{i=1}^n{d_i\choose 2} $$

By Jensen we have:

$$\sum _{i=1}^n{d_i\choose 2} \geq {{1\over n}(\sum d_i)^2-(\sum d_i)\over 2}$$

so we have $$ {k\choose 2}{p\over 2}\geq {{1\over n}(kp)^2-(kp)\over 2}$$ and thus $${k-1\over 2}\geq {1\over n}kp-1$$ so $$n\geq {2kp\over k+1}$$


But I don't know how to find a configuration with $n=\Big[{2kp\over k+1}\Big]$. However, for odd $k$ equality is achieved if $d_1=d_2=...=d_n = {k+1\over 2}$

$\endgroup$
2
  • $\begingroup$ (1) typo? last inequality should be $n \ge {2kp \over k+1}$... right? (2) I'd think for general $p, k$ this bound is very loose. E.g for $p=2$ and large $k$ this bound becomes $n \ge 4$, but I think (99% sure) such an example can only be achieved with $n=k+1$, where each set has one element unique to itself and one element common to everybody. (3) In my answer, Family 1 does achieve the bound: my $U =$ your $n = {2kp \over k+1}$ whenever $k=2^d - 1$. $\endgroup$ – antkam Sep 21 '18 at 19:34
  • $\begingroup$ (4) actually in my answer, Family 2 also achieves your bound: my $U=$ your $n= {2kp \over k+1}$ for odd $k$ and $p = {k-1 \choose ({k-1 \over 2})}$. Furthermore, in those Family 2 examples, $d_1 = ... = d_n = {k+1 \over 2}$. $\endgroup$ – antkam Sep 21 '18 at 20:09
0
$\begingroup$

Not a full answer (or perhaps: answering a different question)

Discussion: For shorthand, write $U = |\bigcup S_i|$. Let $f(k,p)$ denote the minimum $U$, as a function of both $k$ (integer) and $p$ (even integer). There is no decomposition $f(k,p) = g(k) \cdot p$ that holds exactly for all $k,p$. (E.g. if $p=2, k=5$, the only solution I can think of has $U = 6$ where every set has 1 element unique to itself and 1 element common to every set, so $g(5) = 6/2=3$. Meanwhile the OP showed an example for $p=6, k=5, U=10$ so $g(5) = 10/6 = 5/3$.) For that reason, I also find it strange to say lets "assume" $p$ is large and highly composite... unless what you are actually interested in minimizing the ratio $U/p$, e.g. for large $p$, or for optimal $p$. E.g., were you perhaps interested in $h(k) = \min_p {f(k,p) \over p}$, i.e. the minimum ratio (that holds for some $p$, i.e. minimized over all possible even integers $p$)?

Anyway, depending on whether you want to minimize universe size $U$, or minimize the ratio $U/p$, the answers may be different. The rest of this post shows 2 separate families of solutions, one better at minimizing $U$ and the other better at minimizing $U/p$.

Family 1: based on $d$-bit binary vectors

Consider $d$-bit binary vectors $v \in \{0,1\}^d$. Let $D=\{1, 2, ..., d\}$ denote the bit positions. Let $T$ be a non-empty subset of $D$. There are $2^d - 1$ such subsets, which we name $T_1, T_2, ..., T_{2^d -1}$.

  • Define $S_i = \{v \in \{0,1\}^d: \sum_{t \in T_i} v_t = 1 \pmod 2\}$. I.e., for any vector $v$, sum up (modulo 2) all the bits $v_t$ at positions $t \in T_i$, and if the sum is $1$ then the vector belongs in $S_i$, otherwise it doesnt. E.g. for $T_i = \{2,3,5\}$, any vector $(*,1,1,*,1,*,*) \in S_i$ but any vector $(*,1,0,*,1,*,*) \notin S_i$, where $*$ denotes wildcard ($0$ or $1$).

  • For any $i$, it is obvious that exactly 1/2 of all vectors are in $S_i$, i.e. $|S_i| = 2^{d-1} = p$.

  • I think it's also true (although I cannot think of a short proof) that for any $i, j$, exactly 1/4 of all vectors are in $S_i \cap S_j$, i.e. $|S_i \cap S_j| = 2^{d-2} = p/2$.

Thus the sets $S_i$ meet the OP's requirements. There are $2^d - 1$ such sets, and of course you don't have to use all of them. In other words we have constructed examples, parameterized by $d$, where:

  • individual set size $p = 2^{d-1}$
  • no. of sets $k \le 2^d - 1$
  • universe size $U = 2^d - 1$, because every vector is in the union EXCEPT the zero vector
  • ratio $U/p = {2^d - 1 \over 2^{d-1}}$, akin to the original formula the OP suggested.

Family 2: based on $m$-choose-$n$

Let me now exhibit a different family of solutions generalizing the OP's $k=5, p=6$ example.

Suppose you have $m$ distinct objects $\{1, 2, ..., m\}$ and you choose $n<m$ of them. There are of course $L={m \choose n}$ ways to do this, i.e. there are $L$ such size-$n$ subsets. Order these $L$ subsets lexicographically and call them $T_1, T_2, ... T_L$. E.g. if $n=3$ then $T_1 = \{1,2,3\}, T_2 = \{1,2,4\}, ..., T_L = \{m-2, m-1, m\}$, etc. Now form the following $m\times L$ matrix $A$:

  • $A_{ij}=1$ if object $i \in T_j$.
  • $A_{ij}=0$ otherwise.

I.e. the $j$th column of $A$ is the Boolean vector for membership in $T_j$. Now switch your perspective and...

  • Identify the rows of $A$ as the OP's $S_i$ sets.

  • Identify the set of columns as the universe $\bigcup S_i$, and in particular, $L = |\bigcup S_i| = U$.

The following statements hold:

  • Each row contains the same number of $1$s: indeed, $\forall i, \sum_j A_{ij} = {m-1 \choose n-1}$, independent of $i$. This is the number of subsets $T_j$ that contains $i$, which equals the number of ways to choose the remaining $n-1$ elements out of the remaining $m-1$ possibilities. Since we identify each row $i$ as the OP's set $S_i$, this means $|S_i| = p = {m-1 \choose n-1}$.

  • For any two rows $i, i'$, their intersection contains the same number of $1$s: indeed, $\forall i, i', \sum_j (A_{ij}A_{i'j}) = {m-2 \choose n-2}$, independent of $i, i'$. This is the number of subsets $T_j$ that contains both $i$ and $i'$, which equals the number of ways to choose the remaining $n-2$ elements out of the remaining $m-2$ possibilities. Since we identify rows $i, i'$ as the OP's sets $S_i, S_{i'}$, this means $|S_i \cap S_{i'}| = p/2 = {m-2 \choose n-2}$.

  • Now we solve: ${m-2 \choose n-2} = {1 \over 2} {m-1 \choose n-1} \implies n = 1 + {m-1 \over 2} = {m+1 \over 2}$.

In other words, parameterized by odd integer $m$, we can define $n = {m+1 \over 2}$ and we have exhibited a collection of sets (rows of $A$) where:

  • individual set size $p={m-1 \choose n-1}$
  • no. of sets $k \le m$
  • universe size $U = L = {m \choose n}$, the no. of columns of $A$
  • ratio $U/p = {m \choose n} / {m-1 \choose n-1} = m/n = {2m \over m+1}$

Examples and comparisons:

The follow table lists, for several choices of $k$, the "best" examples offered by each family and the resulting $p, U, U/p$. (In each family, the best is obtained by taking the smallest $d$ or $m$ possible.)

                Family 1             Family 2
                --------             --------
     k     d   p   U   U/p      m   n   p   U   U/p
   ---     ---------------      -------------------
     3     2   2   3   3/2      3   2   2   3   3/2
   4,5     3   4   7   7/4      5   3   6  10   5/3
   6,7     3   4   7   7/4      7   4  20  35   7/4
   8,9     4   8  15  15/8      9   5  70 126   9/5
  10,11    4   8  15  15/8     11   6 252 462  11/6
  12,13    4   8  15  15/8     13   7   .   .  13/7
  14,15    4   8  15  15/8     15   8   .   .  15/8

As can be seen, Family 1 generally has much smaller $U$ (except equality when $k=3$), but Family 2 has smaller $U/p$ ratio (except equality when $k=3, 6,7, 14, 15$, and if I may extrapolate: $k= 30, 31, 62, 63,$ etc)

$\endgroup$

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.