A type of algebraic structure related to sets of intervals

Publication date: 14 November 2020

Abstract: F. Wehrung has asked: Given a family

m a t h c a l C

of subsets of a set

O m e g a

, under what conditions will there exist a total ordering on

O m e g a

under which every member of

m a t h c a l C

is convex?

Note that if $A$ and $B$ are nondisjoint convex subsets of a totally ordered set, neither of which contains the other, then $A c u p B$ , $A c a p B$ , and $A s e t m i n u s B$ are also convex. So let $m a t h c a l C$ be an arbitrary set of subsets of a set $O m e g a$ , and form its closure $m a t h c a l P$ under forming, whenever $A$ and $B$ are nondisjoint and neither contains the other, the sets $A c u p B$ , $A c a p B$ , and $A s e t m i n u s B$ . We determine the form $m a t h c a l P$ can take when $m a t h c a l C$ , and hence $m a t h c a l P$ , is finite, and for this case get necessary and sufficient conditions for there to exist an ordering of $O m e g a$ of the desired sort. From this we obtain a condition which works without the finiteness hypothesis.

We establish bounds on the cardinality of the subset $m a t h c a l P$ generated as above by an $n$ -element set $m a t h c a l C$ .

We note connections with the theory of interval graphs and hypergraphs, which lead to other ways of answering Wehrung's question.

This page was built for publication: A type of algebraic structure related to sets of intervals