Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given any collection $\mathcal{C} = \{E_1, E_2, ..., E_m\}$ of finite and nonempty discrete sets, is there a set $I$ such that $$ \forall E_k \in \mathcal{C}, \; E_k \cap I \neq \emptyset,$$ and $$ \forall i \in I, \; \exists E_k \in \mathcal{C}, E_{k} \cap I = \{i\} $$ ?

For example, for $E_1 = \{1,2\}$, $E_2 = \{2,3\}$ and $E_3 = \{1,3\}$ with $m = 3$, a possible $I$ is $\{1,2\}$.

I've been trying to answer this question ever since stumbling upon it in my research, under a different form. I'm hardly a real mathematician so I submitted this problem to some nearby theoretical computer scientists hoping they'd tell me it was trivial, but no such luck.

All I've found until now are a few of rather trivial observations. To begin with, the second property to be verified by $I$ is equivalent to there being an injection $g$ from $I$ to $\{1, ..., m\}$ such that $E_{g(i)} \cap I = \{i\}$ for all $i \in I$. Also, the problem can be formulated as a graph problem using a bipartite graph with $m$ vertices on one side representing the sets in the collection and vertices on the other side for each element in the union set $\bigcup_{i=1}^m E_k$, but graph theory isn't my forte either. Finally, notice that we only really need to consider the collections where $E_1, ..., E_m$ also verify the following properties:

  • any one set $E_j$ is not included in any other $E_k$;
  • there exists no element $e$ in exactly one set $E_k$, in other words $e$ is either in none or in at least two sets of $\mathcal{C}$.
share|improve this question

2 Answers 2

up vote 3 down vote accepted

Let $I$ be a minimal set that intersects each $E_j$, where minimal means that no point can be removed from $I$ without it no longer intersecting each $E_j$. Take any $i\in I$. We know $i$ lies in some $E_j$, otherwise $I$ was not minimal. If every $E_j$ that contains $i$ also contains another element of $I$, then we can remove $i$ from $I$ and it still intersects each $E_j$, so again $I$ would not be minimal. So some $E_j$ that includes $i$ contains no other element of $I$.

share|improve this answer

Let $\mathcal{E} = \bigcup_{k=1}^m E_k.$

For each $j\in\mathcal{E}$, let $A_j = \{ k\in [1,m] : j\in E_k \}$. Then the anticipated subset $I\subset\mathcal{E}$ should satisfy the following requirements: $$\bigcup_{i\in I} A_i = \{ 1, 2, \dots, m \}$$ and $$\forall i\in I\quad A_i\not\subset \bigcup_{j\in I\atop j\ne i} A_j.$$ (the latter means that there exists $k\in A_i$ such that $k\not\in A_j$ for all $j\in I\setminus\{i\}$, that is, $E_k\cap I=\{i\}$)

That is, the collection $\{ A_i : i\in I\}$ forms a minimal cover of the set $\{ 1, 2, \dots, m\}$. Such cover always exists -- one can start with the collection $\{ A_j : j\in\mathcal{E} \}$ and iteratively remove $A_i$ that is a subset of the union of the remaining sets until no such sets left.

In the example with $E_1=\{1,2\}$, $E_2=\{2,3\}$ and $E_3=\{1,3\}$ we have $A_1 = \{1,3\}$, $A_2 = \{ 1,2\}$, $A_3=\{2,3\}$. Clearly, removing any set from the collection $\{ A_1, A_2, A_3 \}$ leaves us with a solution.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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