8
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ Perhaps the negation would be called "general position". $\endgroup$ Jun 1, 2010 at 12:26
  • 1
    $\begingroup$ To supplement Gerald's comment, I think the negation is called independent pair in Boolean algebras. $\endgroup$ Jun 1, 2010 at 14:08
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 1, 2010 at 15:15
  • $\begingroup$ 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. $\endgroup$
    – Jon Awbrey
    Jun 1, 2010 at 15:28
  • $\begingroup$ Associahedra and Weak Monoidal Structures on Categories ? $\endgroup$ Jun 1, 2010 at 15:29

4 Answers 4

12
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Should that be "either disjoint or one containing the other"? $\endgroup$
    – Jon Awbrey
    Jun 2, 2010 at 11:40
6
$\begingroup$

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

http://www.math.vanderbilt.edu/~hughescb/preprints/treesP.PDF

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.

$\endgroup$
3
  • 2
    $\begingroup$ A basis with your "ultrametric" property is commonly called "non-archimedean." (I suppose this terminology comes from the p-adic topology.) $\endgroup$ Jun 1, 2010 at 14:05
  • $\begingroup$ @François: Interesting. I considered naming it that as well. Could you perhaps provide a reference or two? $\endgroup$ Jun 1, 2010 at 16:06
  • $\begingroup$ 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. $\endgroup$ Jun 1, 2010 at 17:35
3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$
    – Pål GD
    Apr 21, 2015 at 2:57
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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