## A family of subsets with a “gluing” property

Somewhat in line with this previous MathOverflow question:

I'm looking at a combinatorial structure consisting of a finite set $S$ of objects, and a family $F$ of designated subsets of $S$. We call elements of $F$ "connected" subsets. (Think of them like connected sets in a topological space, in a loose way.) This family has to satisfy two properties:

• If any two connected sets have non-empty intersection, their union will be connected. (I call this property "glueability".)

• Singletons are always connected. (This property is too vacuous to deserve a name.)

My question is whether any of you have seen anything like this before, or have any idea how to deal with it. This is a sort of awkwardly vague request to make, but I would be very interested to hear if this structure had arisen in any other contexts.

(As an example of what I've come up with: You can easily prove that the maximal connected sets exactly partition the whole set.)

-
 What exactly do you mean by 'maximally connected'? In my mind, maximally connected would imply a lot of connectivity, which would mean a lot of overlap between the sets, which would exclude that they are a partition. – supercooldave Jun 14 2010 at 7:08 Are you assuming S is finite? Otherwise, there need not be any maximal connected sets. For example, take S to be any infinite set, and define the connected sets to be precisely the finite subsets of S. – Kevin Ventullo Jun 14 2010 at 7:30 Did you look at the exponential principle yet? (chapter 5 of Stanley EC II) Possibly also arxiv.org/abs/0911.3760 – Martin Rubey Jun 14 2010 at 7:35 @supercooldave: "Maximal connected set" is supposed to mean "one for which no superset is connected". So it's "maximal" in the poset sense. @Kevin Ventullo: That's a good point. I could change the glueability property to apply to any family of subsets with nonempty intersection (instead of just pairs), but for now I think I'll restrict the question to finite sets, which is what I really care about anyway. – Joshua H Jun 14 2010 at 7:45 Does it help if you make the relation "connected" explicit and formulate things as a combination of properties of the relation and of the sets the relation connects. For example, the relation is certainly reflexive and symmetric, but not transitive as mentioned below. And if S1 connected S2, then (S1 cup S2) connected (S1 cup S2)... Just an idea. – supercooldave Jun 14 2010 at 8:22
show 1 more comment

It's just an exercise in the transitivity of relations? You have the subsets where a given function F takes a given value: in other words any partition, or any equivalence relation. I wouldn't call this a structure.

Edit: As Joshua has remarked, it is not all the subsets of a given partition-set that need be "connected". But do we not get all examples by taking the P that are "maximal connected", and then taking certain subsets of that including P itself and the singletons in it? The only condition seems to be that there are enough subsets to make P by transitive closure.]

-
The maximal connected subsets $X_1,\ldots,X_n$ of a finite set $X$ form a partition of $X$. Each connected set $Y$ must be contained in one of the $X_i$s, and so partitioning into maximal connected subsets is repeated for each $X_i,$ each of their maximal connected subsets, and so on, until one arrives at one-element subsets, which are connected by the second axiom. Thus the "connected structure" on an $n$-element set $X$ may be recorded by a descending chain in the partition lattice $\Pi_n$ whose $k$th element is the partition of $X$ into "depth $k$ maximal connected sets" (a singleton is depth $m,m+1,m+2,\ldots$ ). A subset $Y\subset X$ is connected $\iff$ $Y$ is a block in one of the partitions in the chain. The chains that arise in this way satisfy a certain non-degeneracy condition.
 Since the whole set $S$ can be added to any family $F$ and still form a connected family, your top-level partition might just be $S$ itself. For the induction step in your analysis, therefore, you should look at "maximal proper" connected subsets. – Joel David Hamkins Jun 17 2010 at 12:45 You are right, Joel, and it occurred to me as well (offline). What is worse, this will necessarily be the case for each $X_i$ at the first level. Unfortunately, the maximal proper connected subsets are not going to form a partition. I am no longer convinced that there is clean answer. – Victor Protsak Jun 17 2010 at 16:48 Yep. You are thinking about this on much the same lines as I did. And you're entirely right that the recursive decomposition fails to work, at least in any obvious way. Thanks for your thoughts, though! – Joshua H Jul 6 2010 at 22:13