1
$\begingroup$

Let us define a $n \times 2$ matrix M consisting of integer sets, such that the first column consists of the so-called intersecting sets, and the second column consists of the so-called intersected sets.

Also, for each element $a_{i,j}$ in $M$, $a_{i,1} \supset a_{i,2}$, i.e. i-th intersecting set is a superset over the i-th intersected set.

Let us define a single intersection chain as an ordered subset of indexes of $M$ which always ends with $n$. E.g. for $n = 3$ the intersection chains can be: (1,2,3) or (1,3) or (2,3). Also, in intersection chain each index intersects the succeeding indexes of a chain.

Also, let us assume that for each integer $a$ in the intersecting set $a_{i,1}$ of a chain, $a_{i,1}$ can only intersect at most one $a$ from all occurrences of $a$ in the higher indexed intersected sets of the chain.

E.g. Let (4,5,6) be an intersecting chain, and let $a_{4,1} = \{8,9,10\}$. Assuming that sets $a_{5,2} = \{8\}$ and $a_{6,2} = \{8,11\}$, then only one intersection of integer 8 by $a_{4,1}$ should be accounted since $a_{4,1} \cap \{a_{5,2} \cup a_{6,2} \} = \{8\}$.

Finally, we define an intersection scenario as a set of disjoint intersection chains such that all $n$ elements are present in the chains of the scenario. I.e. no two chains are the same and all $n$ elements are present in the chains of a scenario.

What is the maximum number of the intersected integers among the all possible scenarios? Is there a low-complexity algorithm or mathematical method which can derive this number?

Example:

Given the following matrix:

$M = \begin{bmatrix} \{ 1,2,3,4,5,6 \} & \{ 1,2,3,4,5,6 \} \\ \{ 1,2,3,4,7,8 \} & \{ 1,2 \} \\ \{ 3,4,5,6,7,8 \} & \{ 3,4,5,6,7,8 \} \end{bmatrix}$

There are two possible intersection scenarios:

  • scenario 1: ((1,2,3)),

i.e. $a_{1,1}$ intersects $a_{2,2}$ and $a_{3,2}$,

and $a_{2,1}$ intersects $a_{3,2}$

  • scenario 2: ((1,3),(2,3)),

i.e. $a_{1,1}$ intersects $a_{3,2}$,

and $a_{2,1}$ intersects $a_{3,2}$

The maximum number of uniqely intersected integers in scenario 1 is 8 since in this scenario:

  1. $a_{1,1} = \{ 1,2,3,4,5,6 \}$ intersects the following six integers from $a_{2,2}$ and $a_{3,2}$: $count(\{1,2,3,4,5,6\}) = 6$, and
  2. $a_{2,1} = \{1,2,3,4,7,8\}$ intersects the following two integers from $a_{3,2}$: $count(\{3,4\}) = 2$

The maximum number of uniqely intersected integers in scenario 2 is also 8 since in this scenario:

  1. $a_{1,1} = \{ 1,2,3,4,5,6 \}$ intersects the following four integers from $a_{3,2}$: $count(\{3,4,5,6\}) = 4$, and
  2. $a_{2,1} = \{1,2,3,4,7,8\}$ intersects the following two integers from $a_{3,2}$: $count(\{1,2,7,8\}) = 4$

NOTE: I am aware of the solution where the scenarios can be generated and the intersected integers computed, as given in the example. This may be done since there is a number of ways to partition a set of elements in non-empty disjoint subsets (called Bell number). However, I am interested in a low-complexity solution for a given problem.

$\endgroup$
  • $\begingroup$ Can you revise the question to help understand what "at most one same integer" means? Does it mean "at most one integer appears in intersections"? Does it mean "there is at most one number that appears in more than one of the intersections"? Something else? $\endgroup$ – D.W. Mar 30 at 22:15
  • $\begingroup$ Does it mean "at most one integer appears in intersections"? Almost yes, I would reformulate it: ** At most one integer from the intersecting set appears in intersection **E.g. given that the intersecting set A intersects sets B and C, the maximum number of intersected elements is $A \cap (B \cup C)$. Does this help? $\endgroup$ – Dijenek Mar 30 at 23:19
  • 1
    $\begingroup$ Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Mar 31 at 15:57
  • $\begingroup$ Unfortunately I'm still lost. Can you perhaps reformulate it using mathematics rather than English? $\endgroup$ – D.W. Mar 31 at 15:58
  • $\begingroup$ @D.W. If we assume the following intersection chain (1,2,3), where a_{2,1} intersects a_{2,2} and a_{3,2}, given the following values for those sets: a_{2,1} = {1,2,3}, a_{2,2} = {2,3} and a_{3,2} = {2,3}, the result of the intersection is {2,3}. So a_{2,1} \cap {a_{2,2} \cup a_{3,2}} = {1,2,3} \cap {{2,3} \cup {2,3}}. P.S. I edited the post, so it might be more clear from it. $\endgroup$ – Dijenek Mar 31 at 19:23

Your Answer

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

Browse other questions tagged or ask your own question.