\documentclass{amsart}
\usepackage{amsmath,amsfonts,amsthm,amssymb,indentfirst,epic,xurl,graphics,needspace}
% xurl makes \url willing to break lines at hyphens
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.15in}
\setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{0in}
\sloppy
\setlength{\mathsurround}{.167em}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{question}[theorem]{Question}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{convention}[theorem]{Convention}
% \numberwithin{equation}{section} USE THESE IN FUTURE?
% \numberwithin{theorem}{section}
\newcommand{\R}{\mathbb{R}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cP}{\mathcal{P}}
\renewcommand{\r}{\mathrm}
\raggedbottom
\begin{document}
\begin{center}
\texttt{Comments, corrections,
and related references welcomed, as always!}\\[.5em]
{\TeX}ed \today
\vspace{2em}
\end{center}
\title%
{A type of algebraic structure related to sets of intervals}
\thanks{%
Archived at \url{http://arxiv.org/abs/2011.07399}\,.
After publication, any updates, errata, related references,
etc.\ found will be recorded at
\url{http://math.berkeley.edu/~gbergman/papers/}.\\
\hspace*{1.5em}Data sharing not applicable, as no datasets were
generated or analyzed in this work.
}
\subjclass[2010]{Primary: 06A05, 08A05, 08A55.
% total_ords str_th_alg_strs partl_algs
Secondary: 03C20, 03E25, 05C25, 05C62.
% ultrapr ax_ch& grphs&alg geom+cap_reps_of_grphs
}
\keywords{total ordering on a set making a given family of subsets
convex; interval graph}
\author{George M. Bergman}
\address{Department of Mathematics\\
University of California\\
Berkeley, CA 94720-3840, USA}
\email{gbergman@math.berkeley.edu}
\begin{abstract}
F.~Wehrung has asked: Given a family $\cC$ of subsets of
a set $\Omega,$ under what conditions will there exist
a total ordering on $\Omega$ with respect to which every member
of $\cC$ is convex?
We look at the family $\cP$ of
subsets of $\Omega$ generated by $\cC$ under certain
partial operations which preserve
convexity; we determine the possible structures of $\cP$
if $\cC,$ and hence $\cP,$ is finite, and note a condition
on that structure that is necessary and sufficient
for there to exist an ordering of $\Omega$ of the desired sort.
From this we obtain a criterion which works without the
finiteness hypothesis on $\cC.$
We establish bounds on the cardinality of
the set $\cP$ generated by an $\!n\!$-element set $\cC.$
We end by noting some other ways of answering Wehrung's
question, using results in the literature.
\end{abstract}
\maketitle
% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\section{Introduction}\label{S.intro}
If $(\Omega,\leq)$ is a totally ordered set, we shall call a subset
$A$ of $\Omega$ {\em convex} if for
$p,\,q,\,r\in\Omega$ with $p\leq q\leq r,$ the conditions
$p,\,r\in A$ imply $q\in A.$
(I use the word ``interval'' in the title, since
it concisely suggests ``convex subset of a totally ordered set'',
but in general, I shall write ``convex set''.
The word ``interval'' will, however, come up in \S\ref{S.int_grph},
in connection with results in the literature.)
This note answers the question:
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.FW_q}
(F.\,Wehrung, personal correspondence related to~\cite{FW_r-l};
slightly reworded.)
Let~$\Omega$ be a set (usually finite), and
$\cC$ a set of subsets of $\Omega.$
When does there exist a total order on~$\Omega$ with respect to
which every member of~$\cC$ is convex?
\end{minipage}\end{equation}
In \S\ref{S.inf0,$ it is a
difference of overlapping sets,
$[0,\,n-1]\setminus[-n+i,\,i-1]=A_n\setminus A_i.$
The symmetric argument shows that we can get
$[-n+1,\,j],$ completing the proof.
\end{proof}
Let us observe that for $n\leq 2,$ the members
of {\em every} family $\cC$ of $n$ subsets of a set $\Omega$
are convex under some ordering of $\Omega.$
This is immediate for $n=0$ and $n=1.$
To see the case $n=2,$ let $\cC=\{A_1,\,A_2\}.$
If $A_1$ and $A_2$ are disjoint or one contains
the other, it is again easy to see how to get such an ordering.
If they overlap, then by choosing any ordering in
which all elements of $A_1\setminus A_2$ lie above
those of $A_1\cap A_2,$ and these in turn lie above
all elements of $A_2\setminus A_1,$ while every element not
in $A_1\cup A_2$ lies above or below all elements
of $A_1\cup A_2,$ we again get the desired convexity conditions.
For $n=0,\,1,\,2,$ the upper bounds given by
Proposition~\ref{P.size} are $2,$ $3$ and $9,$ while
those given by Proposition~\ref{P.size_cnvx} are $2,$ $3$ and $8.$
Thus, these functions differ first at $n=2.$
By the above orderability observation for $n=2,$
the upper bound given by Proposition~\ref{P.size_cnvx} holds
for $n=2$ in the context of Proposition~\ref{P.size}.
A consequence of Proposition~\ref{P.size_cnvx} is that given
a set $\cC$ of $n$ subsets of a finite set $\Omega,$ one can
determine in polynomial time whether there exists an ordering
of $\Omega$ making all elements of $\cC$ convex.
The idea is that starting with a list of the $n$ sets
in $\cC,$ together with the sets $\Omega$ and $\emptyset,$
one searches the list for overlapping pairs
$A,$ $B,$ and when one finds such a pair, adds to
the list their union,
their intersection, and their relative complements,
and repeats this process recursively.
Within polynomial time, one will know whether or
not this recursive process terminates
before the cardinality of the list goes above $\binom{2n}{2}+2$
(i.e., whether we get a family closed under those partial operations
without getting above that cardinality).
If it doesn't so terminate,
then by Proposition~\ref{P.size_cnvx}
there can be no ordering of the desired sort.
If it does, then one has an enumeration of $\cP,$
and one can work out its adjacency structure
and apply Theorem~\ref{T.cnvx}\,(a)\!$\iff$\!(b)
to determine whether there exists such an ordering.
The time needed will be polynomial in $n$ and the number of
elements in $\Omega.$
(If, rather, $\Omega$ is infinite, then whether one can do the same
in a time that is polynomial in $n$ will depend on what sort of
descriptions we have of $\Omega$ and the subsets
of $\Omega$ that form~$\cC.$
If we assume the operations of the Boolean algebra of
subsets of $\Omega$ ``given'', then we have polynomial time in $n.)$
\section{Other solutions to question~\eqref{d.FW_q}, based on
results in the literature}\label{S.int_grph}
Given a set $\cC$ of subsets of a set $\Omega,$
the graph which has the members of $\cC$ as vertices, and
an edge between $A,B\in\cC$ if and only if $A\cap B\neq\emptyset,$
is called the {\em intersection graph} of $\cC.$
There has been considerable study of the intersection graphs of finite
sets of intervals of the real line.
Graphs that can be so represented
are called {\em interval graphs}, and several
characterizations of such graphs have been established
(see~\cite{Wiki_int_graph}, and for some details,
\cite[Theorem~9.4.4]{graph}, \cite[Chapter~3]{Fishburn} and~\cite{hsu}).
The literature varies, inter alia, as to whether intervals are assumed
to be closed or open \cite[Remark~9.4.2, point~2]{graph},
but it is not hard to show that a finite graph is
an interval graph in either sense if and only if it satisfies
the formally weaker condition that for {\em some}
totally ordered set $(\Omega,\leq),$ the graph can be represented
as the intersection graph of a set of convex subsets of $\Omega.$
Criteria for a finite graph to be an interval graph
do not, themselves, answer the finite-$\cC\!$ case of
question~\eqref{d.FW_q}:
If the intersection graph of a set $\cC$ of sets is
an interval graph, this only tells us that the graph is
{\em isomorphic} to
the intersection graph of {\em some} set of convex subsets
of some totally ordered set.
Observe, for example, that the complete graph with
three vertices is the intersection graph of the family of three sets
$\{1\}\subset\{1,2\}\subset\{1,2,3\},$ which are convex under the
standard ordering of the integers, but is also the
intersection graph of $\{1,2\},$ $\{1,3\},$ $\{2,3\},$
which are not simultaneously convex under any ordering of $\{1,2,3\}.$
However, Dave Witte Morris (personal communication)
has pointed out that one can get around this difficulty by
bringing in the singleton subsets of $\Omega$ alongside the elements
of $\cC$ (assuming for the moment that $\Omega$ is finite).
We develop the result below.
Here we take an {\em interval} to mean
a set $[s,t]=\{x\in\R\mid s\leq x\leq t\}$ where $s