4
$\begingroup$

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.)

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – supercooldave
    Commented Jun 14, 2010 at 7:08
  • $\begingroup$ 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. $\endgroup$
    – Kevin Ventullo
    Commented Jun 14, 2010 at 7:30
  • $\begingroup$ Did you look at the exponential principle yet? (chapter 5 of Stanley EC II) Possibly also arxiv.org/abs/0911.3760 $\endgroup$
    – Martin Rubey
    Commented Jun 14, 2010 at 7:35
  • $\begingroup$ @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. $\endgroup$
    – joshuahhh
    Commented Jun 14, 2010 at 7:45
  • $\begingroup$ 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. $\endgroup$
    – supercooldave
    Commented Jun 14, 2010 at 8:22

2 Answers 2

Reset to default
3
$\begingroup$

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.]

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'm not sure I follow you, but if you're saying that the only possibility is for the set S to be partitioned into subsets and a given set to be "connected" iff it is/(is a subset of) one of those subsets, that's not right. For instance, we might have S={1,2,3}, F={{1},{2},{3},{1,2},{1,2,3}}... But please let me know if I am misunderstanding your point. $\endgroup$
    – joshuahhh
    Commented Jun 14, 2010 at 7:58
  • $\begingroup$ Oh, and also note that if {a,b} and {b,c} are connected, that doesn't imply that {a,c} is connected (as you may have assumed, based on your mention of transitivity?). All that glueability implies is that {a,b,c} is connected. $\endgroup$
    – joshuahhh
    Commented Jun 14, 2010 at 8:01
  • $\begingroup$ Re: your edit -- "transitive closure" isn't quite an appropriate term to use. There is no relation here, other than perhaps the relation "a~b if {a,b} is connected". And that relation is not at all fundamental, since we can have interesting families without any pairs present. Take F2={singletons, {1,2,3}, {2,3,4}, {1,2,3,4}}. And if you mean to say that each maximal connected set can be built from smaller sets via gluing, that's not true either... Take the example I called F above. (continued) $\endgroup$
    – joshuahhh
    Commented Jun 14, 2010 at 9:27
  • $\begingroup$ (continuation) Any given connected set can either be built up from smaller sets or not, and these smaller sets don't have to be pairs. The obligation runs in the other direction: if smaller connected sets are arranged in the correct way, they entail the existence of larger connected sets. (Thanks a lot for taking the time to think about this stuff, by the way!) $\endgroup$
    – joshuahhh
    Commented Jun 14, 2010 at 9:27
  • $\begingroup$ A way of thinking is in terms of equations a = b, or to be clearer F(x) = F(y). If you give me as axioms such equalities for all pairs of elements of your connected sets, the question for me becomes the scope of what can be proved about F. So my description is: use the partition induced by the values of F being provably equal. Your remark is to do with the sets of axioms. So this is a kind of series of remarks about "equational logic", in my view. The gluing on overlaps is accurately modelled by the conjunction of F(x) = F(y) and F(y) = F(z), which gives F(x) = F(z). $\endgroup$
    – Charles Matthews
    Commented Jun 14, 2010 at 9:37
1
$\begingroup$

I can't really follow the discussion in Charles' answer (perhaps, the question got changed?), but there is a clear way to interpret this structure.

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.

This indeed looks similar to an "exponential structure" mentioned by Martin Rubey (Stanley, Enumerative combinatorics Def 5.5.1), but there is no postulated relation between the decompositions of different maximal connected subsets (no regularity dictated by "size"), so it is different.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Jun 17, 2010 at 12:45
  • $\begingroup$ 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. $\endgroup$
    – Victor Protsak
    Commented Jun 17, 2010 at 16:48
  • $\begingroup$ 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! $\endgroup$
    – joshuahhh
    Commented Jul 6, 2010 at 22:13

You must log in to answer this question.

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