\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}
\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}\,;
Readable at \url{http://math.berkeley.edu/~gbergman/papers/}.
The latter version may be revised more frequently than the former.
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{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 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 orderability property.
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} supersedes
that given by 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 this recursive process
terminates (i.e., gives a family closed under those partial operations)
before the cardinality of the list goes above $\binom{2n}{2}+2.$
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.)$
\section{Other solutions to question~\eqref{d.FW_q}, using
results in the literature}\label{S.int_grph}
Given a set $\cC$ of subsets of a set $\Omega,$
the graph having 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} 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}.
In fact, 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.$
However, criteria for a finite graph to be an interval graph
do not answer the finite-$\!\cC\!$ case of
question~\eqref{d.FW_q}:
If the intersection graph of $\cC$ is
an interval graph, this only tells us that it is 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 $\{x,y\},$ $\{y,z\},$ $\{x,z\},$
which are not simultaneously convex under any ordering of $\{x,y,z\}.$
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