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

Does the following relation between sets have a name or any special properties:

$X\bigcirc Y$ iff $X \cap Y = \emptyset$ or $X\subseteq Y$ or $Y\subseteq X$.

Although this is rather basic, it is part of something much grander.

share|improve this question
Perhaps the negation would be called "general position". –  Gerald Edgar Jun 1 '10 at 12:26
To supplement Gerald's comment, I think the negation is called independent pair in Boolean algebras. –  François G. Dorais Jun 1 '10 at 14:08
This relation came up in a paper I coauthored recently, although in a very elementary form - parenthesis are required to nest in a way that satisfy these properties. –  Steven Gubkin Jun 1 '10 at 15:15
In other words, $X \cap Y$ is either $\varnothing$ or $X$ or $Y$. I think there's an app(ellation) for that in lattice theory. –  Jon Awbrey Jun 1 '10 at 15:28
Associahedra and Weak Monoidal Structures on Categories ? –  supercooldave Jun 1 '10 at 15:29

4 Answers 4

I don't know if there is any better terminology but such families of sets (either disjoint or containing one another) are said to form a Laminar family or a hierarchical system. There is a bijection between Laminar families from a set S and S-rooted forests. If a laminar family has the additional property that each element in S is contained in at least one member of the family then one calls it a complete laminar family. The enumeration of laminar families is open.

share|improve this answer
Should that be "either disjoint or one containing the other"? –  Jon Awbrey Jun 2 '10 at 11:40

I agree that this is a natural and interesting property of a family of sets.

From my (arithmetic-geometric) perspective, the most prominent examples of such families are the disks in an ultrametric space. As Gjergji points out, there is indeed a deep connection to tree-like structures here: see for instance


Already the first paragraph in the introduction underscores my point.

So, although it is certainly not standard, there would be some logic in calling such families "ultrametric".

Good luck with your grandeur. There's plenty of fuel for it in this case, I think.

share|improve this answer
A basis with your "ultrametric" property is commonly called "non-archimedean." (I suppose this terminology comes from the p-adic topology.) –  François G. Dorais Jun 1 '10 at 14:05
@François: Interesting. I considered naming it that as well. Could you perhaps provide a reference or two? –  Pete L. Clark Jun 1 '10 at 16:06
If I had a handy copy of the Handbook of Set Theoretic Topology, I would give you a page number. Unfortunately, all I can remember is that they at least occur in Todorcevic's chapter. –  François G. Dorais Jun 1 '10 at 17:35

For the special case where $X$ and $Y$ are intervals of the real line, the complementary relation to this --- i.e. $X \cap Y \neq \varnothing$ but $X \not\subseteq Y$ and $Y \not\subseteq X$ --- is used to define overlap graphs (a.k.a. circle graphs). This is an intersection model of graphs, where vertices are labelled by intervals of the real line, and two vertices are adjacent if and only if those intervals overlap (intersect without nesting).

share|improve this answer
If we're invoking graph theory, it's interesting to note that the actual relation corresponds to intersection graph of nested intervals (or trivially perfect graphs). –  Pål GD Apr 21 at 2:57

There is a related concept dealing with separations as opposed to sets. A separation of a set $U$ is an ordered pair $(A,B)$ such that $A$ and $B$ are disjoint subsets of $U$ whose union is $U$. We say that two separations $(A,B)$ and $(C,D)$ are nested if $A \subset C$ or $B \subset D$. Otherwise, we say that the two separations cross. So, if $X$ and $Y$ are both subsets of $U$, then $X$ and $Y$ have your desired property if and only if the separations $(X, U - X)$ and $(Y, U-Y)$ do not cross. I think the term crossing separations is pretty standard, at least in the case of separations of graphs as opposed to separations of sets.

share|improve this answer

Your Answer


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.