# Finding a set of subsets such that for each such subset in the set, there exists another subset in the same set which is non-disjoint

I'm sorry if the title is a bit convoluted. I'm a bit unsure how to formulate this condition in words, see below instead.

Say we are given a set $Y$. I want to find the following set: $\mathcal{A}$ such that for any $x=\{G_1, ..., G_k\} \in \mathcal{A}, G_i \subset Y$, we have that:

$\forall G_i \in x, \exists G_j \in x, i \neq j , \quad G_i \cap G_j \neq \emptyset$

I'm mostly interesting in finding an algorithm which generates this set. This problem arose when trying to figure out how to generate the set of subgraphs of a connected subgraphs, such that their union is still connected. So the sets above would then be vertex sets and I would form their induced graph.

So, I want to find the subgraphs such that the union of all those subgraphs $\bigcup_{i=1}^{k}G_{i} \text{ is connected}$. Since each of the subgraphs themselves are connected (since the graph is), the above stated condition ought to ensure that their union is connected.

Anyone have an idea how to tackle this? Any help is much appreciated!

-
Can you explain the notation $x=\{G_1,...,G_k\}$? – picakhu Jul 26 '11 at 14:16
$x$ is a combination of $k$ subsets of $Y$. $k$ is just an arbitrary number. So for example let $Y=\{1,2,3\}$. We might have $x=\{ \{1,2\}, \{2,3\} \}$ which has one "overlapping" element. Ah, it should be $x \subset A$ rather than $x \in A$ I realized now. – Erik Jul 26 '11 at 14:23
Another example, $Y=\{1,2,3,4,5\}$. An element of $\mathcal{A}$ would be $\{ \{1,2\}, \{2,3\}, \{3,4,5\} \}$. Yet another element would be: $\{ \{1,2,3\}, \{3,4,5\} \}$. I hope this makes it clearer. – Erik Jul 26 '11 at 14:32
This is a weak condition you've outlined and does not imply that the union of all the "subgraphs" is connected. For example you might have $G_1$ and $G_2$ with nonempty intersection and $G_3$ overlapping with $G_4$, yet nothing that connects $G_1 \cup G_2$ with $G_3 \cup G_4$. Have you really asked for what you want? – hardmath Jul 26 '11 at 14:36
That is true. Thanks for pointing that out! I guess what I'm really after is for example a 1-vertex overlapping partition of the original graph. That is, I want the union of the set of subgraphs to be the original (by assumption connected) graph. The partition can't be disjoint though. (These subgraphs will then later on be fed to a graph classification algorithm). – Erik Jul 26 '11 at 14:57

Given a (finite) set $Y$, I think you want a collection $A$ of subsets of $Y$, no two of which are disjoint (and my apologies if I've utterly misread the question). I think you also want $Y$ to be the union of the elements of $A$. Of course, there will in general be many such collections $A$. It is of some interest to find the biggest possible $A$, that is, the one with the most elements. It's not hard to see that the answer to this maximization problem is to pick some $y$ in $Y$ and let $A$ be the collection of subsets of $Y$ containing $y$.

Things get more interesting if you insist that all the elements of $A$ have the same size, say, $k$ (assume, to avoid triviality, $\#(Y)=n\ge2k$ ). Then the Erdos-Ko-Rado Theorem says the maximum size of $A$ is $n-1\choose k-1$.

-

Gerry's reading of the problem (no two subsets disjoint) is a fairly strong (yet interesting) condition. However it seems to me Erik intended to allow for pairs of disjoint sets, as long as the covering $Y = \bigcup G_i$ as a whole satisfies an "overlapping" condition Erik briefly outlined in a Comment.

Here's my reconstruction of the problem: Given a finite set $Y$, construct all $k$-coverings $\{ G_i |\; i = 1,..,k \}$ of $Y$, $k \gt 1$, such that the graph on nodes $G_i$ with edges corresponding to pairs that have nonempty intersection ("overlap") is connected.

For example, with $Y = \{1,2,3,4,5\}$ one might have a set of subsets $\{\{1,2\},\{2,3\},\{3,4\},\{4,5\}\}$, despite the fact that some pairs are disjoint.

One approach to this would be to enumerate all connected graphs with $k$ nodes, up to isomorphism, and then for each such graph determine all the ways to realize the graph with a $k$ set covering of $Y$. Apart from permutations on $Y$ there may be numerous distinct realizations of the same graph. For the example Erik gave in the last Comment (so far), $Y$ was covered by $\{\{1,2\},\{1,3\},\{1,4\},\{1,5\}\}$, which corresponds to $K_4$ the complete graph on four vertices since every pair of sets overlaps. But that graph is also realized by the covering $\{\{1,2\},\{1,2,3\},\{1,2,3,4\},\{1,2,3,4,5\}\}$, which is evidently not equivalent to Erik's example by some permutation on $Y$.

Added: The count of connected graphs (up to isomorphism or "unlabelled") of specified number of vertices is the subject of Sloane's sequence A001349 (OEIS). Note that Gerry's interpretation is for the complete graph, which is one of six possibilities for four vertices, one of 21 possibilities for five vertices, etc. Another interesting question is how big $Y$ must be in order to realize one (or all) of these graphs. $Y = \{1,2,3\}$ is big enough to realize $K_4$.

-

The more I look at the question, the less I understand it. I wonder whether we aren't dealing with (something like) Katona's question on separating covers. I quote from Vincent Vatter, Maximal independent sets and separating covers, Amer Math Monthly 118 (May 2011) 418-423:

A separating cover over the ground set $X$ is a collection $S$ of subsets of $X$ which satisfies two properties:

1. The union of the sets in $S$ is all of $X$, and

2. for every pair of distinct elements $x,y$ in $X$, there are disjoint sets $S,T$ in $S$ with $x$ in $S$ and $y$ in $T$.

Katona asked about the function $$s(m)=\min\lbrace n:\hbox{there is a separating cover on m elements with n sets}\rbrace$$ Endquote. Vatter goes on to give the answer, prove it, relate it to Moon and Moser's answer to a question of Erdos about the number of maximal independent sets a graph on $n$ vertices can have, and to a couple of other questions that one would not have thought to be at all related.

-