0
$\begingroup$

Let's say I have a set of elements $V$. I can use all subsets of $V$ of size $k$ to satisfy intersection conditions.

Example: $V = \{ 1, 2, 3, 4, 5\}$, $k = 3$. $|B_1 \cap B_2|=2$,$|B_2 \cap B_3|=2$,$|B_3 \cap B_1|=1$

One solution would be $\{ \{1, 2, 3\}, \{1, 2, 4\}, \{2, 4, 5\} \}$.

I'm wondering how to find/enumerate these solutions. The intersection conditions are limited if $B_4$ is added to the conditions.

Example: $V = \{ 1, 2, 3, 4, 5\}$, $k = 3$. $|B_1 \cap B_2|=2$,$|B_2 \cap B_3|=2$,$|B_3 \cap B_1|=\bf{2}$

One solution would be $\{ \{1, 2, 3\}, \{1, 2, 4\}, \{1, 2, 5\} \}$. If $B_4$ is added, then $|B_4 \cap B_i| = 2$ cannot be true for all $i$.

It would be also nice to know if I could find the possible values of $|B_4 \cap B_i|$ too. It looks like these values really depend on the contents of the first $B_i$ sets, although I'm not sure.

$\endgroup$
4
  • $\begingroup$ Is $V$ finite? And what kinds of intersection conditions are you considering? Only conditions of the form $|B_i\cap B_j|=m$? $\endgroup$
    – Servaes
    Commented Sep 20, 2020 at 10:30
  • $\begingroup$ @Servaes Let's say it's finite. Yes, only $|B_i \cap B_j|=m$. One problem is given intersection conditions, enumerate the solutions satisfying them. Another is figuring out the valid intersection conditions when solution set is extended by an extra $B_i$. $\endgroup$
    – Looft
    Commented Sep 20, 2020 at 12:43
  • $\begingroup$ One general method to approach such problems is through binary integer programming, but this does not seem like the most effective approach here. This is a very general problem, though. Bounds on the intersection numbers, or on $k$ or $|V|$, could make the problem more feasible. $\endgroup$
    – Servaes
    Commented Sep 20, 2020 at 13:31
  • $\begingroup$ I'm currently interested in values where $|V| \leq 50$ and $k \leq 10$. To me, it looks like there is a lot of symmetry and the problem gets constrained pretty quickly. Pairwise intersection conditions constrain the whole solution very well. But yes, all of my approaches seem to not exploit the symmetry and just go through too many combinations. $\endgroup$
    – Looft
    Commented Sep 20, 2020 at 15:59

1 Answer 1

Reset to default
2
$\begingroup$

Associate each subset $B \subseteq \{1,2,3,4,5\}$ with a vector $v_{B} \in \mathbb{R}^{5}$ with 0/1 entries, such that the $j$th entry of $v_{B}$ is 1 if and only if $j \in B$. This is called the characteristic vector of $B$.

Now you have that $|B_{i} \cap B_{j}| = v_{B_{i}}\cdot v_{B_{j}}$.

So you are looking for vectors with 0/1 entries satisfying $v_{i}\cdot v_{i} = 3$ for all $1\leq i \leq 3$, $v_{1}\cdot v_{2} = 2$, $v_{2}\cdot v_{3} = 2$, $v_{1}\cdot v_{3} = 1$. This is equivalent to finding a $5\times 3$ 0/1 matrix $$A = \begin{bmatrix} v_{1} & v_{2} & v_{3} \end{bmatrix}$$ such that $$A^{T}A = \begin{bmatrix} 3 & 2 & 1\\ 2 & 3 & 2\\ 1 & 2 & 3 \end{bmatrix}$$

In general it is not easy to find all 0/1 solutions to such an equation, or even to determine if any 0/1 solution exists. You can assign variables to the entries of $A$ and get a system of homogeneous quadratic equations in 15 variables, there is special software that can solve this for you but it will take a lot of time if there are more than a few variables involved.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .