\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.00in}
\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{https://arxiv.org/abs/2011.07399}\,.
After publication, any updates, errata, related references,
etc.\ found will be recorded at
\url{/~gbergman/papers/}.\\
\hspace*{1.5em}Data sharing not applicable, as no datasets were
generated or analyzed in this work.
}

\subjclass[2020]{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?
% \P \ %

We look at the family $\cP$ of
subsets of $\Omega$ generated by $\cC$ under certain
partial operations which, when $\Omega$ is given with
a partial ordering, preserve
convexity; we determine the possible structures of $\cP$
under these operations
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.$
% \P \ %

Bounds are obtained on the cardinality of
the set $\cP$ generated under
these operations by an $\!n\!$-element set $\cC.$
% \P \ %

We end by noting some other ways of answering Wehrung's
question, using results in the literature.
The bibliography lists still more related 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.inf<fin}, we show that given a set
$\cC$ of subsets of a set $\Omega,$ there exists a total ordering $\leq$
on $\Omega$ having the
desired property for $\cC$ if and only if for every finite subset
$\cC'\subseteq\cC,$ there exists a total
ordering $\leq_{\cC'}$ on $\Omega$ having that property for $\cC'.$
Thus, the general problem reduces to the
corresponding problem for finite $\cC.$

In \S\ref{S.patchw} we note some natural partial operations on the
set of convex subsets of a totally ordered set $\Omega,$
which can be described solely in set-theoretic
terms, and we name an arbitrary set $\cP$ of
subsets of a set $\Omega$ which is closed under
these partial operations a ``patchwork''.
Thus, a set $\cC$ of subsets of $\Omega$ has
all its members convex under some total
ordering $\leq$ on $\Omega$ if and only if the patchwork $\cP$
that it generates has the same property.
Moreover, the patchwork generated by a finite set $\cC$
of subsets of $\Omega$ is
finite; so question~\eqref{d.FW_q} for finite sets $\cC$
comes down to the same question for finite patchworks~$\cP.$

In \S\ref{S.fin_cP} we determine the structures of all
{\em finite} patchworks $\cP$ of subsets of a set $\Omega,$
and note for which of these
there exist orderings of $\Omega$ making all members of $\cP$ convex.
In \S\ref{S.nonfin}, we combine this result with that
of \S\ref{S.inf<fin} to
get a condition on a not necessarily finite patchwork
that is necessary and sufficient for the existence of such an ordering.

In \S\ref{S.size} we examine how many elements the
patchwork $\cP$ generated by an $\!n\!$-element set $\cC$ can have.

After an earlier draft of this note was sent
out, it was pointed out to me that there
are results in the literature that can be used to answer
question~\eqref{d.FW_q} in other ways.
These are noted in~\S\ref{S.int_grph}.
So perhaps the main value of this paper is the detailed
structure it reveals of the family $\cP$ arising from a family $\cC$
for which question~\eqref{d.FW_q} has a positive answer -- and
possibly also the corresponding structural information
when~\eqref{d.FW_q} is not assumed to have a positive answer.
(Whether that case has interesting applications I do not know.)

One of the referees
has pointed out that the sort of structure I call a patchwork is named
a ``weakly partitive family'' in \cite{ref_8}, \cite{ref_3},
\cite{ref_1}.

We remark that the arguments of \S\ref{S.fin_cP} below that determine
the possible structures of a finite patchwork
are rather lengthy and intricate; but the reasoning is elementary.
In contrast, the argument of \S\ref{S.inf<fin} that reduces
the general question to the finite case
calls on the Compactness Theorem of model theory,
or, alternatively, on ultrafilters;
so that proof, though brief, is the
one non-elementary piece of reasoning in this note.

\section{Reduction to the case of finite $\cC$}\label{S.inf<fin}

\begin{lemma}\label{L.inf<fin}
Let $\Omega$ be a set, and $\cC$ a set of subsets of $\Omega.$
Then the following conditions are equivalent.\\[.2em]
%
\textup{(i)} \ \ There exists a total order on~$\Omega$ with respect
to which every member of~$\cC$ is convex.\\[.2em]
%
\textup{(ii)} \ For each finite subset $\cC'\subseteq\cC,$
there exists a total order on~$\Omega$ with respect to
which every member of~$\cC'$ is convex.
\end{lemma}

\begin{proof}
(i)$\implies$(ii) is clear, since an ordering that works
for $\cC$ works for any $\cC'\subseteq\cC.$

The reader familiar with the Compactness Theorem of model theory
\cite[Corollary~V.5.6]{PMC.UA} will see that %
that theorem implies the reverse implication.
(One uses a language with a
constant for each element of $\Omega,$ a unary relation
for each member of $\cC,$ and a binary relation ``\!${\leq}$\!''.)
I sketch below a variant of this argument
that uses ultrafilters \cite[{\S}V.5]{PMC.UA} rather than
the Compactness Theorem.

Assume~(ii).
Let $X$ be the set of all finite subsets $\cC'\subseteq \cC,$
and let us choose for each $\cC'\in X$ a total ordering
$\leq_{\cC'}$ on $\Omega$ under which all
members of $\cC'$ are convex.
Since the ordering of $X$ by inclusion is upward directed,
the nonempty up-sets of $X$ generate a proper filter $\mathcal{F}$
on $X,$ which can be extended to an ultrafilter $\mathcal{U}.$
For every pair of distinct elements $a,b\in\Omega,$ either the set
$\{\cC'\mid a\leq_{\cC'}b\}$ or its complement
$\{\cC'\mid b\leq_{\cC'}a\}$ belongs to $\mathcal{U};$ let us write
$a\leq b$ in the former case, $b\leq a$ in the latter.

From the fact that each $\leq_{\cC'}$ is a total ordering
on $\Omega,$ it is easily deduced that $\leq$ is a total ordering
on $\Omega.$
To show that every $A\in\cC$ is convex under that ordering,
suppose $a\leq b\leq c,$ and $a,c\in A.$
The definition of $\leq$ and the inequalities $a\leq b\leq c$
show that $\{\cC'\in X\mid a\leq_{\cC'}b\leq_{\cC'}c\}\in\mathcal{U},$
while the definition of $\mathcal{F}$ shows
that $\{\cC'\in X\mid A\in\cC'\}\in\mathcal{F}\subseteq\mathcal{U};$
hence the intersection of these two sets is nonempty.
Taking $\cC'$ in that intersection, we see that
since $A\in\cC'$ is convex under $\leq_{\cC'},$ we indeed have $b\in A,$
as required
\end{proof}

\section{Patchworks}\label{S.patchw}

The concept we will define next is motivated by
the following easily verified result.

\begin{lemma}\label{L.ops}
If $(\Omega,\,\leq)$ is a totally ordered set, and $A,~B$
are convex subsets of $\Omega$ which have nonempty intersection, and
neither of which contains the other, then $A\cap B,$
$A\cup B,$ and $A\setminus B$ are also convex.

Also, $\emptyset$ and $\Omega$ are convex.
\qed
\end{lemma}

(Each of the conclusions of the first sentence of Lemma~\ref{L.ops}
needs less than the full set of assumptions on $A$ and $B.$
But the cases where the unnecessary assumptions fail are
trivial, so we lose nothing in using this formulation.)

\begin{definition}\label{D.patchw}
Let $\Omega$ be a set.

We will say that subsets $A,\,B\subseteq\Omega$ {\em overlap}
if they have nonempty intersection, and neither contains the other.

For any set $\Omega,$ a {\em patchwork} of subsets of $\Omega$
\textup{(}which may be shortened to ``a patchwork on $\Omega$'', or
simply ``a patchwork'' when the context makes $\Omega$ clear\textup{)}
will mean a set $\cP$ of subsets of $\Omega$ such that
for every pair of {\em overlapping} sets
$A,\,B\in\cP,$ the set $\cP$ also contains $A\cap B,$
$A\cup B,$ and $A\setminus B,$ and such that
$\emptyset$ and $\Omega$ also belong to $\cP.$

If $\cP$ is a patchwork on $\Omega,$
members of $\cP$ will be called {\em $\!\cP\!$-sets}.
\end{definition}

We note

\begin{lemma}\label{L.finite}
The patchwork $\cP$ on a set $\Omega$ generated by a
finite set $\cC$ of subsets of $\Omega$
\textup{(}i.e., the closure of $\cC$ under the partial
operations of Definition~\ref{D.patchw}\textup{)} is finite.
\end{lemma}

\begin{proof}
$\cP$ is contained in the Boolean ring of subsets of $\Omega$
generated by $\cC,$ and finitely generated Boolean rings are finite.
\end{proof}

\section{The case of finite $\cP.$}\label{S.fin_cP}

\begin{convention}\label{C.cP_fin}
Throughout this section, $\Omega$ will be a fixed
set, and $\cP$ a {\em finite} patchwork on $\Omega.$
\end{convention}

A key to analyzing the structure of $\cP$ is
to look at those of its members to which its
partial operations {\em cannot} be applied:

\begin{definition}\label{D.aut}
A $\!\cP\!$-set $A$ will be called {\em autonomous}
if it is nonempty, and does not overlap any member of~$\cP$
\textup{(}cf.~Definition~\ref{D.patchw}\textup{)}.
We will generally shorten ``autonomous $\!\cP\!$-set'' to
``autonomous set''.

If $A\in\cP$ is autonomous,
then the set of maximal autonomous {\em proper} subsets of $A$
will be called the {\em cohort} under $A.$
Elements of $A$ that are not in the union of the cohort
under $A$ \textup{(}if any\textup{)}
will be called {\em non-cohort elements} of $A.$
\end{definition}

Note that

\begin{lemma}\label{L.2aut}
Any two autonomous members of $\cP$
are either disjoint, or one contains the other.
\end{lemma}

\begin{proof}
By the definition of ``autonomous'' this is, in fact, true of any
two $\!\cP\!$-sets at least {\em one} of which is autonomous.
\end{proof}

By Lemma~\ref{L.2aut} the autonomous members of $\cP$
form a tree under inclusion, branching
downward from the top element, $\Omega.$
It follows from the finiteness of $\cP$
that for every proper subset $A$ of $\Omega,$ there is
a {\em least} autonomous $\!\cP\!$-set $B$ properly containing~$A.$

Note that every {\em minimal}
autonomous set $A$ consists entirely of non-cohort elements.
Non-minimal autonomous $\!\cP\!$-sets necessarily have nonempty cohorts
under them; we shall see that
they may or may not also have non-cohort elements.
Each element of $\Omega$ is a non-cohort element of a
unique autonomous set, namely, the least autonomous
set containing it.

Not every union of autonomous sets need be a $\!\cP\!$-set, but
the converse is true:

\begin{lemma}\label{L.cup_aut}
Let $A$ be a $\!\cP\!$-set.
Then\\[.2em]
%
\textup{(i)} \ \ $A$ is a union of autonomous sets; in fact
it is the disjoint union of the maximal
elements of the set of autonomous sets which it contains.

Moreover, if $A\neq\Omega,$ then letting $B$ be the least
autonomous set {\em properly} containing $A,$ we have\\[.2em]
%
\textup{(ii)} \ The maximal autonomous sets contained in $A$
\textup{(}cf.~\textup{(i))}
all belong to the cohort under $B.$\\[.2em]
%
\textup{(iii)} If $A'$ is a $\!\cP\!$-set which overlaps
$A,$ then the least
autonomous set properly containing $A'$ is also $B.$\\[.2em]
%
\textup{(iv)} If $A$ is not autonomous, then
it can be written as a disjoint union of two nonempty $\!\cP\!$-sets,
each of which is the union of a subset of the cohort under $B.$
\end{lemma}

\begin{proof}
(i):  If $A$ is autonomous this is
trivial:\ it is the union of the $\!1\!$-element family $\{A\}.$
If $A$ is not autonomous,
assume inductively that all $\!\cP\!$-sets properly contained in $A$
are unions of autonomous sets.
Since $A$ is not autonomous, it overlaps some $\!\cP\!$-set $A'.$
Then $A\cap A'$ and $A\setminus A'$ are $\!\cP\!$-sets
properly contained in $A,$ so by the inductive hypothesis,
they are unions of autonomous sets, hence so is their union,~$A.$
That $A$ is the union of the {\em maximal} autonomous sets
that it contains follows, since $\cP$ is finite; and
by Lemma~\ref{L.2aut}, these sets are disjoint.

(ii): Let $C$ be a maximal autonomous subset of $A.$
Then $C$ is a proper autonomous subset of $B;$ we
need to show it is maximal among such subsets.
If not, suppose $D$ were an autonomous set with
$C\subset D \subset B.$
By the maximality of $C$ in $A,$ we have $D\not\subseteq A;$
by minimality of $B$ among autonomous sets properly containing $A,$
we have $A\not\subseteq D;$ so, as $A\cap D\supseteq C\neq\emptyset,$
the sets $A$ and $D$ overlap, contradicting the assumption
that $D$ is autonomous.
So no such $D$ exists, as desired.

(iii): We shall show that $B$ contains $A'.$
This implies that $B$ contains the least autonomous set
containing $A'.$
Moreover, reversing the roles of $A$ and $A',$ it follows
that the least autonomous set containing
$A'$ contains $B;$ so those two autonomous sets must be the same,
as desired.

To see that $B$ contains $A',$
note that $A\cup A'$ is a $\!\cP\!$-set which is
not disjoint from $B,$ so by the autonomy of $B,$
it must either be contained in $B$ or properly contain $B.$
If the latter were true, then $A'$ would have elements outside
$B,$ and also contain the nonempty set $B\setminus A,$ so it would
overlap $B,$ which is impossible since $B$ is autonomous.
So $A\cup A'$ must be contained in $B;$
in particular, $A'$ is contained in $B,$ as claimed.

(iv): Since $A$ is nonautonomous, we can choose a
$\!\cP\!$-set $C$ which it overlaps.
Thus, by~(iii), the least autonomous set containing $C$ is $B,$
so by~(i) and~(ii), $A$ and $C$ are both unions
of members of the cohort under $B.$
Writing $A$ as the union of the disjoint nonempty $\!\cP\!$-sets
$A\cap C,$ and $A\setminus C,$ we have the desired decomposition.
\end{proof}

The above results suggest
the question: Given an autonomous set with nonempty cohort under it,
{\em which} unions of subsets of this cohort can be $\!\cP\!$-sets?
We will use the following concept.

\begin{definition}\label{D.adj}
Two $\!\cP\!$-sets $A$ and $B$ will be called {\em adjacent}
if they are disjoint, and their union is again a $\!\cP\!$-set.

The {\em adjacency graph} of a set of $\!\cP\!$-sets
will mean the graph having the members of this set as
vertices, and having an edge between a pair of such
vertices if and only if they are adjacent as $\!\cP\!$-sets.
\end{definition}

The word ``adjacent'' is motivated by the case where
$\cP$ consists of sets convex under a total ordering $\leq$ on $\Omega,$
but our definition is not limited to that case;
and even in that case, two sets $A,\,B\in\cP$
that are adjacent as convex subsets of $\Omega$ need not be
adjacent under our present definition, if our patchwork
$\cP$ doesn't happen to include $A\cup B.$

If we had given the above definition earlier, we could,
in Lemma~\ref{L.cup_aut}(iii), have changed
``a $\!\cP\!$-set which overlaps $A$'' to
``a nonempty $\!\cP\!$-set which overlaps $A$ or is adjacent to $A$'',
since the proof uses only the fact that the union $A\cup A'$ is a
$\!\cP\!$-set distinct from both $A$ and $A'.$
Thus we have

\begin{lemma}\label{L.adj_in_coh}
If $A$ and $A'$ are adjacent nonempty $\!\cP\!$-sets, then
the least autonomous set properly containing $A$ and
the least autonomous set properly containing $A'$ are the same.

In particular, any two adjacent
{\em autonomous} $\!\cP\!$-sets belong to the same cohort.\qed
\end{lemma}

We can now prove

\begin{lemma}\label{L.adj-graph}
A subset $A$ of $\Omega$ is a $\!\cP\!$-set if and only
if it can be written as the union of a family of
autonomous sets whose adjacency graph is connected.
\end{lemma}

\begin{proof}
The statement is trivial if $A$ is an autonomous
set or $\emptyset,$ so assume that neither of these is the case.

To get the ``if'' direction, suppose $A$ is the union of
a family of more than one autonomous sets, and has
connected adjacency graph.
The desired implication is
true if the graph in question has exactly $2$ vertices,
by the definition of adjacency;
so assume it has $\geq 3$ vertices.
Let us also assume inductively that the corresponding implication
is true for every set $A'$ that can be
written as the union of a family of fewer
autonomous sets than we are using for~$A.$

Let us now choose a vertex $B$ in the graph for $A$
such that the subgraph obtained by removing $B,$ i.e.,
the adjacency graph of the family with union $A\setminus B,$
is still connected.
% Every finite connected graph with at least two vertices has
% a vertex which can be removed without disconnecting the graph
(Such a vertex exists in any finite connected graph $G$ with
at least two vertices~\cite[Theorem~3.2.10]{graph}.
Indeed, choosing any vertex $x,$ a vertex $y$ at maximum distance
from $x$ has the desired property, since for any other vertex $z,$
a shortest path from $x$ to $z$ cannot pass through $y,$ whence in
$G\setminus\{y\},$ every vertex $z$ lies in the connected
component of~$x.)$
Thus, by our inductive assumption, $A\setminus B$ is a $\!\cP\!$-set.
Let $C$ be a vertex of the graph for $A$ which is adjacent to $B.$
Since the graph for $A$ has $\geq 3$ vertices,
it has vertices other than $B$ and $C.$
Hence neither of the $\!\cP\!$-sets $A\setminus B$ or $B\cup C$
contains the other, moreover, they overlap in $C;$ so their union,
$A,$ is a $\!\cP\!$-set, as desired.

Conversely, suppose $A$ is a $\!\cP\!$-set which is neither autonomous
nor empty, and $B$ the least autonomous set containing $A.$
By Lemma~\ref{L.cup_aut}(i) and~(ii), $A$ is the union
of some subset of the cohort under $B;$ we wish to show that
the adjacency graph of that subset
is connected.
Again, this is clear if that graph has $\leq 2$ vertices,
so suppose it has at least $3,$ and assume by induction
that every proper subset of
that set whose union is a $\!\cP\!$-set does
have connected adjacency graph.

Since $A$ is non-autonomous,
Lemma~\ref{L.cup_aut}(iv) gives us a decomposition of our expression
for $A$ into two disjoint subfamilies, whose unions are
$\!\cP\!$-sets $A_1$ and $A_2.$
By our inductive assumption, the graphs corresponding
to these $\!\cP\!$-sets are connected, so to show that the
graph corresponding to $A$ is connected, it will suffice
to find a connected subgraph thereof
whose vertex-set meets both those subgraphs.
Again invoking our inductive assumption, we will have this if
we can find a proper $\!\cP\!$-subset $A_3\subset A$
which is a union of members of the cohort under $B,$
and which meets both $A_1$ and $A_2.$

Since the graph associated with $A$ had at least $3$ vertices,
the subgraph associated with one of $A_1,$ $A_2$ must have more than one
vertex; i.e., one of those two $\!\cP\!$-subsets,
say $A_1,$ must be non-autonomous.
Let $C$ be a $\!\cP\!$-set which overlaps $A_1.$
By Lemma~\ref{L.cup_aut}(iii), $C$ is also a union of
members of the cohort under $B.$
If $C$ also has nonempty intersection with $A_2,$
then we see that $A\cap C$ will be a $\!\cP\!$-subset $A_3$
of the sort we need.
On the other hand, if $C\cap A_2=\emptyset,$ then the
fact that $C\not\subseteq A_1$ implies $C\not\subseteq A,$
so $A\setminus C$ is a $\!\cP\!$-set, and will serve as our $A_3.$
\end{proof}

(Remark:  In the above result, if $A$ is not autonomous, then
it will have a {\em unique} expression of the indicated sort.
If it {\em is} autonomous, then as noted, its expression as the
union of the singleton $\{\!A\}$ is always of the indicated sort;
in this case $A$ may or may not have another such expression.
Namely, we will see later that an autonomous
set $A$ may or may not be the union of
the cohort under it, and that if it is, the adjacency graph
for that decomposition may or may not be connected.)

To lead up to our criterion for the existence of an
ordering of $\Omega$ under which all $\!\cP\!$-sets are convex,
we look next at two conditions which (it is not hard to see)
are incompatible with the existence of such an ordering.

\begin{lemma}\label{L.adj_to_3}
If an autonomous set $A$ is adjacent to {\em more than two}
other autonomous sets, then every two autonomous
sets adjacent to $A$ are adjacent to one another.

In fact, when this is true, then
in the adjacency graph of the cohort containing $A,$ the connected
component containing $A$ has an edge between every two vertices.
\end{lemma}

\begin{proof}
Let $B$ be the least autonomous set properly containing $A.$
In view of Lemma~\ref{L.adj_in_coh}, all the autonomous sets
referred to in the lemma are members of the cohort under~$B.$

To get the first assertion of the lemma, we first consider any
two autonomous sets $C\neq C'$ adjacent to $A.$
By the adjacency assumption, $A\cup C$ and $A\cup C'$
are $\!\cP\!$-sets, and they clearly overlap,
so their union $A\cup C\cup C'$ is a $\!\cP\!$-set.
Now by our hypothesis there is at least one other autonomous
set $C''$ adjacent to $A,$ so $A\cup C''$ is a $\!\cP\!$-set
which overlaps $A\cup C\cup C';$
hence $(A\cup C\cup C')\setminus (A\cup C'') = C\cup C'$
is a $\!\cP\!$-set, i.e., $C$ and $C'$ are adjacent, as claimed.

To get the second assertion, let us first show that
in the situation of the above paragraph, if $C$
is adjacent to yet another member $D$ of the cohort under $B,$
then $A$ is also adjacent to $D.$
Indeed, since $C$ is adjacent to the three
sets $A,$ $C'$ and $D,$ the first assertion of the lemma shows
that these are adjacent to one another,
in particular, $A$ and $D$ are adjacent.
By induction, all members of the connected component in question
are adjacent to $A,$
so by yet another application of the first assertion
of the lemma, they are all adjacent to one another.
\end{proof}

\begin{lemma}\label{L.cycle}
Suppose $A_1,\dots,A_n$ $(n\geq 3)$ are distinct autonomous sets
forming a ``cycle of adjacency'', i.e.,
such that $A_i$ is adjacent to $A_{i+1}$ $(1\leq i<n),$
and $A_n$ to $A_1.$
Then, again, in the adjacency graph of the cohort containing
the $A_i,$ the connected component containing
these elements has an edge between every two vertices.
\end{lemma}

\begin{proof}
First suppose $n\geq 4.$
Then $A_1\cup A_2\cup A_3$ and
$A_3\cup\dots\cup A_n\cup A_1$ will be overlapping $\!\cP\!$-sets,
hence their intersection, $A_1\cup A_3$ is a $\!\cP\!$-set; i.e.,
$A_1$ and $A_3$ are adjacent.
Hence $A_3$ is adjacent to at least the three sets
$A_1,$ $A_2$ and $A_4,$ so the preceding lemma is applicable.

On the other hand, suppose $n=3.$
If the connected component in question
is simply $\{A_1,\,A_2,\,A_3\},$ we are done.
If not, then by connectedness,
some other member $C$ of that connected component
must be adjacent to one of the $A_i.$
This again makes that $A_i$ adjacent to three distinct
members of the component, so again, the preceding lemma is applicable.
\end{proof}

We can now prove

\begin{theorem}\label{T.i-iii}
Let $\cP$ be a finite patchwork, and $B\in\cP$ an autonomous set.
Then exactly one of the following statements is true.\\[.2em]
%
\textup{(i)}~ The cohort under $B$ has at least $3$ members,
every two members of that cohort are adjacent,
and the union of the cohort is all of $B.$ \\[.2em]
%
\textup{(ii)}\, The cohort under $B$ has at least $2$ members,
the adjacency graph of that cohort is a path
\textup{(}i.e., consists of elements $A_1,\dots,A_n$ for some $n\geq 2,$
with $A_i$ and $A_j$ adjacent if and only if $|i-j|=1),$
and again, the union of the cohort is all of $B.$\\[.2em]
%
\textup{(iii)}  No two members of the cohort under $B$ are adjacent.
\textup{(}In this case, $B$ may or may not contain non-cohort elements.
If it does,
the cohort under $B$ may be empty or nonempty.\textup{)}\vspace{.2em}
\end{theorem}

\begin{proof}
Consider the adjacency graph of the cohort under $B.$
If this has any edges, then the members of that cohort
comprising a nontrivial connected component of that
graph will have as union a $\!\cP\!$-subset $A\subseteq B$
by Lemma~\ref{L.adj-graph}.
This $A$ must be autonomous, since if it overlapped another
$\!\cP\!$-set $A',$ then by Lemma~\ref{L.cup_aut}(iii)
$A\cup A'$ would still be a $\!\cP\!$-subset of $B,$
hence its adjacency graph would again correspond to a
subgraph of the cohort of $B,$ which, by Lemma~\ref{L.adj-graph},
would be a larger connected subgraph of that graph, a contradiction.

So such an $A$ will be an autonomous $\!\cP\!$-subset of $B$ which
properly contains members of the cohort under $B;$ hence $A$
must equal $B.$
This shows that if the adjacency graph of the cohort under $B$ has
any edges, then it is connected, and $B$ is the union of
that cohort, i.e., has no non-cohort elements.

By Lemmas~\ref{L.adj_to_3} and~\ref{L.cycle}, if the above
adjacency graph has either any ``branching'' or any cycles,
it must have an edge between every pair of points, and since
it will also have at least three vertices, it will fall under case~(i).
On the other hand, a connected graph with at least one edge
which has neither branching nor cycles is a path, so if that is so,
we are in case~(ii).
Finally, if the adjacency graph of $B$ has no edges, we are
in case~(iii).

(As noted earlier, a minimal autonomous set $B$ has empty cohort under
it, and so necessarily has non-cohort elements.
For an example of an autonomous set having both a nonempty cohort under
it and
non-cohort elements, the reader can examine the case where $\Omega$ is a
totally ordered set, and $\cP$ is the patchwork
generated by an interval $B$
in $\Omega$ and one or more pairwise disjoint subintervals of $B$
whose union is not all of $B.)$
\end{proof}

We can now answer question~\eqref{d.FW_q} for finite patchworks.

\begin{theorem}\label{T.cnvx}
The following three conditions on a finite patchwork
$\cP$ are equivalent:\\[0.2em]
%
\textup{(a)} $\Omega$ admits a total ordering $\leq$
under which all $\!\cP\!$-sets are convex.\\[0.2em]
%
\textup{(b)} No three nonempty $\!\cP\!$-sets
are pairwise adjacent.\\[0.2em]
%
\textup{(c)} Every autonomous $\!\cP\!$-set $B\subseteq\Omega$
falls under case~\textup{(ii)} or \textup{(iii)} of
Theorem~\ref{T.i-iii}.
\end{theorem}

\begin{proof}
(a)$\implies$(b) is intuitively clear.
To supply some details: if a convex set $A\subseteq\Omega$ is adjacent
to each of a pair of disjoint convex sets $A'$ and $A'',$ then one
of $A'$ and $A''$ must lie above it and the other below it under $\leq,$
otherwise $A'$ and $A''$ could not be disjoint.
Since $A'$ and $A''$ have the nonempty
set $A$ between them, their union is not
convex, so they are not adjacent.

(b)$\implies$(c) is immediate: If some $B$
fell under case~(i) of Theorem~\ref{T.i-iii}, the
cohort under it would include three pairwise adjacent sets.

To prove (c)$\implies$(a) we shall, assuming~(c),
construct recursively an ordering $\leq$ as in~(a).

Given an autonomous set $B\subseteq\Omega,$ assume recursively
that for each $A$ in the cohort under $B,$ we have constructed
a total ordering on $A$ under which all $\!\cP\!$-sets contained
in $A$ are convex.
(If $B$ is minimal, the cohort under it is empty, and this assumption is
vacuous.)

If $B$ falls under case~(ii) of Theorem~\ref{T.i-iii},
then writing the members of the cohort under $B$ as
$A_1,\dots,A_n,$ as in that theorem, we order their union
$B$ so that $A_1,\dots,A_n$ form {\em successive} intervals of $B$
(either putting $A_i$ below $A_{i+1}$ for all $i<n,$ or
putting $A_i$ above $A_{i+1}$ for all such $i),$
with each $A_i$ ordered internally
by the order previously constructed for it.

On the other hand, if $B$ falls under case~(iii),
we can order it by arranging the members of the cohort under
it (if any)
in any order, simply making each a convex subset of $B,$ again
with the internal ordering previously constructed,
and likewise put the non-cohort elements of $B$
(if any) in any order above, below or between those
intervals.

We see that for every $\!\cP\!$-set $A,$ if $B$ is the least
autonomous $\!\cP\!$-set containing it,
then $A$ becomes convex under the ordering so constructed on $B,$
and remains so as we extend this ordering to larger autonomous sets.
Hence when our construction reaches
the top set, $\Omega,$ we have established~(a).
\end{proof}

Going back to Theorem~\ref{T.i-iii}, let us turn that result
upside down, and
describe, somewhat informally, how to construct all finite patchworks:

Start with any partially ordered set $T$ having the form of a finite
downward-branching tree, with greatest element denoted $\Omega.$
Choose any graph structure on the elements of $T$
such that edges, if any, occur only among elements of $T$
that lie immediately below a common element, and such that for
each element, the resulting
graph structure on the set of all elements immediately
below it is either a complete graph, a path, or edgeless.
Now assign to each element of $T$ such that the graph
structure we have given to the set of elements immediately below it
is edgeless a set that is to be its set of non-cohort
elements, assigning to distinct elements of $T$ disjoint sets,
and requiring the set so assigned to every
element of $T$ with $\leq 1$ elements of $T$ immediately
below it to be nonempty.
Let each element of $T$ become the name of the union
of the sets of non-cohort elements assigned to it {\em and}
to all elements of $T$ anywhere below it, and call the
sets so named {\em autonomous sets}.
(Apologies for this informal step of turning
abstract elements into names for sets!)
In particular, $\Omega$ is the name assigned to the set of
{\em all} elements that have been introduced as non-cohort elements at
any step.
Finally, let the members of $\cP$ be the unions of those families
of autonomous sets which, under our graph structure on $T,$
form connected subgraphs.

\section{The case of not necessarily finite $\cP$}\label{S.nonfin}

Returning to Theorem~\ref{T.cnvx}, we can combine it with
Lemma~\ref{L.inf<fin} and deduce:

\begin{theorem}\label{T.cnvx-inf}
Let $\Omega$ be a set, and $\cP$ a
\textup{(}not necessarily finite\textup{)} patchwork
of subsets of $\Omega.$
Then \textup{(}as in Theorem~\ref{T.cnvx}\,\textup{)},
the following conditions are equivalent.\\[.2em]
%
\textup{(a)} $\Omega$ admits a total ordering $\leq$
under which all $\!\cP\!$-sets are convex.\\[0.2em]
%
\textup{(b)} No three nonempty $\!\cP\!$-sets are pairwise adjacent.
\end{theorem}

\begin{proof}
(a)$\implies$(b) is clear, as in the proof of Theorem~\ref{T.cnvx}.

Conversely, assume~(b) holds.
Then the same condition holds for all finite
sub-patchworks $\cP'\subseteq\cP,$ hence by
Theorem~\ref{T.cnvx}, for each such $\cP'$ there exists
an ordering $\leq_{\cP'}$ making all elements of $\cP'$ convex.
Since every finite subset $\cC'\subseteq\cP$ generates a finite
sub-patchwork $\cP',$ an ordering $\leq_{\cP'}$ which makes
all members of $\cP'$ convex will do the same for
$\cC';$ so we can now apply
Lemma~\ref{L.inf<fin} (with $\cP$ in the role of $\cC)$
to get an ordering $\leq$ as in~(a), completing the proof.
\end{proof}

We could not bring condition~(c) of Theorem~\ref{T.cnvx}
into Theorem~\ref{T.cnvx-inf}, because
as one goes from one finite patchwork $\cP_0$
on $\Omega$ to a larger one, sets that
were autonomous can cease to be so, and this may leave us with no
proper autonomous sets in the infinite patchwork $\cP.$
For two contrasting examples, let $\Omega$ be the real line,
let $\cP_1$ consist of $\emptyset,$ $\Omega,$ and all the
half-open intervals
$[a,\,b)$
$(a<b\in\R),$
and let $\cP_2$ consist of all finite unions of members of $\cP_1.$
Both these families are patchworks, and it is easy to see
that neither has any autonomous elements other than $\Omega.$
The sets in $\cP_1$ are convex under
the standard ordering on $\Omega,$ but
there can be no ordering under which the sets in $\cP_2$
are convex, since
condition~(b) fails: {\em every} two disjoint nonempty
members of $\cP_2$ are adjacent in $\cP_2,$ so any three such
sets show the failure of~(b).
So despite having the same (trivial) family of autonomous sets,
one of these patchworks does, and the other does not, satisfy
the conditions of the above theorem.

It would be interesting to know whether the kind of structures
we have called patchworks are useful in other contexts
than the study of convex subsets of ordered sets.

We remark that in defining the concept of a patchwork,
rather than making it a
family of subsets of a set $\Omega,$ we could, with slightly
greater formal generality, have made it a family of elements
of a general Boolean ring.
The ``set of subsets of a set'' version seemed most natural for our
purposes, but the more general version might be useful in some other
contexts.

\section{The cardinality of a patchwork generated by $n$ elements}\label{S.size}
We noted in Lemma~\ref{L.finite} that every finitely generated
patchwork is finite.
Let us get some sharper bounds.

The proof of the next
result uses an observation that we have not yet
stated explicitly: any patchwork $\cP$ is closed under
pairwise intersections, and hence under all finite intersections.
Indeed, by definition $\cP$ is closed under intersections of
overlapping elements, while if two elements are comparable,
their intersection is one of them, while if they are disjoint,
their intersection is $\emptyset\in\cP.$
% This gives us all pairwise intersections, and hence, as noted, all
% finite intersections.

\begin{proposition}\label{P.size}
If $n$ is a nonnegative integer, $\Omega$ a set, and $\cP$
a patchwork generated by $n$ subsets of $\Omega,$ then $\cP$
has at most $2^{2^n-1}+1$ elements.
Moreover, for all $n\neq 2,$ there exist examples achieving this bound.
\end{proposition}

\begin{proof}
Let $\mathcal{B}(n)$ be the free Boolean ring on $n$ generators
\cite[Theorem~26, p.260, and Corollary~1]{frBA}.
This can be described as the Boolean ring of all subsets
of the set $2^n$ of subsets of $\{1,\dots,n\};$ its free
generators are the sets $X_1,\dots,X_n,$ where $X_i$ is
the set of those subsets containing $i.$
Thus $\mathcal{B}(n)$ has cardinality $2^{2^n}.$
The {\em nonunital} subring $\mathcal{B}(n)^\r{o}$
of $\mathcal{B}(n)$ generated by
the $X_i$ consists of those members
of $\mathcal{B}(n)$ which, like $X_1,\dots,X_n,$ do
not have as a member the empty subset of $\{1,\dots,n\};$
so it has cardinality $2^{2^n-1}.$

(Some readers might find it more comfortable to think of
what I am calling $2^n,$ not as the set of subsets
of $\{1,\dots,n\},$ but as the set of length-$\!n\!$
strings of $\!0\!$'s and $\!1\!$'s; so that elements of
$\mathcal{B}(n)$ become, not sets of sets, but sets of words.
What I have said above, and will do below,
is easily translated into that viewpoint.)

If $\cP$ is the patchwork on a set $\Omega$ generated by
$n$ subsets $A_1,\dots,A_n,$ let us map the free Boolean
ring $\mathcal{B}(n)$ homomorphically into the Boolean ring of all
subsets of $\Omega$ by sending each free generator $X_i$ to $A_i.$
It is not hard to see that the partial binary operations on subsets
of $\Omega$ used in Definition~\ref{D.patchw} carry the image of
$\mathcal{B}(n)^\r{o}$ into itself, so the elements of $\cP$
obtained from $A_1,\dots,A_n$ using those operations will lie
in that image, as will the element $\emptyset.$
The one member of $\cP$ that may not be contained in
that image is $\Omega,$ so counting this,
we see that $\cP$ must have cardinality $\leq 2^{2^n-1}+1.$

To get an example where this value is achieved,
let us take $\Omega$ to be $2^n,$ meaning, as above, the set
of all subsets of $\{1,\dots,n\},$ and examine
the patchwork $\cP$ on $\Omega$ generated by the $X_i.$

Since every pair $X_i,$ $X_j$ $(i\neq j)$ overlaps, $\cP$ will contain
all the sets $X_i\setminus X_j$ $(i\neq j).$
I now claim that for any $a\in 2^n$
which contains some but not all of $1,\dots,n,$
the singleton $\{a\}$ is a $\!\cP\!$-set.
Indeed, it is the intersection of
those sets $X_i\setminus X_j$ such that $i\in a$ but $j\notin a.$
The singleton whose unique member is the whole set
$\{1,\dots,n\}$ is also in $\cP,$ being the intersection
of the $X_i$ themselves.
On the other hand, $\emptyset\in\Omega$
is not contained in any of the $X_i,$
so the singleton $\{\emptyset\}$ is not a $\!\cP\!$-set.

This gives us $2^n-1$ singleton autonomous sets; let us
now look at adjacency relationships among them.
I claim that if two elements $a\neq\,b\in\Omega$
are nonempty, and differ only in the presence or
absence of a single one of $1,\dots,n,$ then
$\{a,\,b\}\in\cP,$ i.e., $\{a\}$ and $\{b\}$ are adjacent.
Indeed, of the $n-1$
members of $\{1,\dots,n\}$ at which $a$ and $b$ agree,
they must agree in {\em containing} at least one, otherwise one
of $a$ or $b$ would be empty.
If they also agree in {\em not} containing at least one, then,
imitating the trick of the preceding paragraph, we can obtain
$\{a,\,b\}$ as an appropriate intersection
of sets $X_i\setminus X_j,$ while if they contain
all $n-1$ elements at which they agree, then,
again using the idea of the preceding paragraph, we find that
$\{a,\,b\}$ will be an intersection of sets $X_i.$
Using these adjacency relations,
we can get a chain of adjacency from any
nonempty $a$ to the element $\{1,\dots,n\};$ so the
adjacency graph of these $2^n-1$ singleton autonomous
sets is connected.
Moreover, the $n$ elements of cardinality $n-1$ are all adjacent
to $\{1,\dots,n\},$ so if $n\geq 3,$ Lemma~\ref{L.adj_to_3} tells
us that every two of these singletons are adjacent; so the union of
every subfamily of these singletons is
a $\!\cP\!$-set, giving $2^{2^n-1}$ elements.
Bringing in $\Omega$ itself
(which is not such a union, because it contains
not only the $2^{n-1}$ nonempty subsets of $\{1,\dots,n\}$ but also
the empty subset), we have the asserted $2^{2^n-1}+1$ elements.

We assumed in the next-to-last sentence that $n\geq 3.$
Looking at lower values,
if $n=1,$ so that $\{1,\dots,n\}$ has a unique nonempty
subset $a=\{1\},$ we have $2^{2^n-1}+1 = 3,$ and
$\cP$ indeed has $3$ elements,
$\emptyset\subset\{a\}\subset\{\{\emptyset\},a\}=\Omega.$
If $n=0,$ so that $\Omega=\{\{\emptyset\}\},$ the empty
set $\cC$ of subsets of $\Omega$ generates the patchwork
$\{\emptyset,\,\Omega\},$ which has cardinality $2 = 2^{2^n-1}+1.$

The case $n=2,$ on the other hand will fall under the next result.
(See discussion after the proof thereof.)
\end{proof}

\begin{proposition}\label{P.size_cnvx}
If $n$ is a nonnegative integer, $\Omega$ a set, and $\cP$
a patchwork generated by $n$ subsets of $\Omega$ whose members
are all convex under some ordering $\leq$ on $\Omega,$
then $\cP$ has at most $\binom{2n}{2} + 2 = 2n^2-n+2$ elements; and
for all $n$ there exist examples achieving this bound.
\end{proposition}

\begin{proof}
To prove the stated bound, suppose $(\Omega,\leq)$ is a totally ordered
set, and let us define a ``cut'' $\chi$ in $\Omega$ to be a pair
$(\chi^\ell,\,\chi^u)$ (the superscripts standing
for ``lower'' and ``upper'') such that $\Omega$ is the disjoint
union of $\chi^\ell$ and $\chi^u,$ and every element of $\chi^\ell$
is less than every element of $\chi^u.$
(So such a cut is equivalent to an isotone map
from $\Omega$ to $\{0,1\}.$
Note that $\chi^\ell$ or $\chi^u$ may be empty.)
Let us call a cut $\chi$ ``higher than'' a cut
$\chi'$ if $\chi^\ell\supset{\chi'}^\ell.$
Clearly, the cuts are totally ordered under this relation.

Observe that every nonempty convex subset $A$
of $\Omega$ is determined by two cuts, $\chi_{A\uparrow}$
and $\chi_{A\downarrow},$ the former characterized by the property that
$\chi_{A\uparrow}^u$ consists of the elements of $\Omega$ that are
greater than all elements of $A$ (equivalently, that
$\chi_{A\uparrow}^\ell$ consists of the elements that are less than
or equal to at least one
element of $A),$ the latter by the property that
$\chi_{A\downarrow}^\ell$ consists of the elements that are
less than all elements of $A$ (equivalently, that
$\chi_{A\downarrow}^u$ consists of the elements greater than or
equal to at least one element of $A).$
Thus, $A=\chi_{A\uparrow}^\ell\cap \chi_{A\downarrow}^u.$

Given overlapping convex sets $A$ and $B,$ it is not hard to see
that for each of $A\cup B,$ $A\cap B,$ $A\setminus B$ and
$B\setminus A,$ the two cuts determining the set in question
are taken from among the
four cuts $\chi_{A\downarrow},$ $\chi_{A\uparrow},$
$\chi_{B\downarrow},$ and $\chi_{B\uparrow}.$
(Which pair of cuts correspond to each of these depends on whether
$A$ extends upward from $A\cap B$ and $B$ downward therefrom,
or vice versa.
For instance, in the former case, $A\setminus B$ is determined by
the two cuts $\chi_{A\uparrow}$ and $\chi_{B\uparrow};$
i.e., $A\setminus B = \chi_{A\uparrow}^\ell\cap\chi_{B\uparrow}^u.)$

Hence if we start with a set $\cC$ of $n$ convex sets, those of them
that are nonempty determine at most $2n$ distinct cuts, and
applying our four partial binary operations recursively,
we get a set of nonempty convex sets each of which is determined by
one of the $\leq\binom{2n}{2}$ unordered pairs of distinct
cuts from this set.
Bringing in the sets $\Omega$ and $\emptyset$ (which may or
may not have belonged to $\cC,$ or, in the case of $\Omega,$
arisen via our partial operations), we see that the patchwork
generated by $\cC$ can have at most $\binom{2n}{2}+2$ elements.

Let us now show that for every $n,$ this upper bound is achieved.
For integers $i\leq j,$ let us here write $[i,j]$ for
$\{k\in\mathbb{Z}\mid i\leq k\leq j\}.$
Let $\Omega$ be the set $[-n,\,n],$
under the usual ordering of the integers, and
let $\cC$ consist of the $n$ convex subsets
$A_i = [-n+i,\,i-1]$ $(i=1,\dots,n),$ each of which has $n$ elements.
We shall show below that the closure
$\cP$ of $\cC$ under the partial {\em binary}
operations in the definition of a patchwork consists of
all the nonempty convex subsets of $[-n+1,\,n-1].$
Note that the latter $\!2n{-}1\!$-element ordered set
admits $2n$ cuts (one
``below'' the least element, $2n-2$ between successive
elements, and one ``above'' the greatest element),
hence it has $\binom{2n}{2}$ nonempty convex subsets.
Once we know that our partial binary operations give
us all these sets, then bringing in $\Omega$
(which, since it contains $-n$
and $n,$ is not in that closure) and $\emptyset,$
it will follow that the patchwork generated by $\cC$
indeed has $\binom{2n}{2}+2$ elements.

To show that we get all convex sets
$[i,\,j]$ with $-n+1\leq i\leq j\leq n-1,$
it will suffice to show that we get those of
the forms $[i,\,n-1]$ and $[-n+1,\,j],$
since $[i,\,j]=[i,\,n-1]\cap [-n+1,\,j].$
To get $[i,\,n-1],$ note that if $i<0,$ that set is the
union of the overlapping sets $[i,\,i+n-1]=A_{i+n}$ and
$[0,n-1]=A_n;$
if $i=0,$ it is $[0,\,n-1]=A_n,$ and if $i>0,$ 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
all elements 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,$ $9,$ while
those given by Proposition~\ref{P.size_cnvx} are $2,$ $3,$ $8,$
so these bounds differ first at $n=2.$
By the orderability result of the preceding paragraph for $n=2,$
the bound given by Proposition~\ref{P.size_cnvx} holds
for that case even 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 that recursive construction has
given us an enumeration of $\cP,$
and we 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 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 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, however, 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<t\in\R.$
(Because intervals are by definition nonempty, we shall, in
defining the set $\cC^+$ below, not only append to $\cC$ all singletons,
but also remove $\emptyset$ if it belonged to $\cC.)$

\begin{proposition}[D.\,W.\,Morris]\label{P.DWM}
Let $\Omega$ be a finite set, $\cC$ a set of subsets
of $\Omega,$ and $\cC^+$ the set
consisting of all members of $\cC$ other than $\emptyset,$
and also all singletons $\{a\}$ $(a\in\Omega).$
Then the following two conditions are equivalent:\\[.2em]
%
\textup{(i)}  There exists a total ordering $\leq$ of $\Omega$ under
which all members of $\cC$ are convex.\\[.2em]
%
\textup{(ii)}  The intersection graph of $\cC^+$ is an
interval graph \textup{(}i.e., is isomorphic
to the intersection graph of a set of
intervals of the real line\textup{)}.\vspace{.2em}

Thus, applying to $\cC^+$ any of
the criteria in~\cite{Wiki_int_graph} for a finite graph
to be an interval graph, one gets criteria for the
members of $\cC$ to be convex under some ordering of $\Omega.$
\end{proposition}

\begin{proof}
First assume we have an ordering $\leq$ as in~(i), and list
the elements of $\Omega$ in order as $a_1<\dots<a_n.$
Choose real numbers $s_1<t_1<s_2<t_2<\dots<s_n<t_n.$
These determine disjoint intervals $I_i=[s_i,t_i]\subseteq\R,$
$(i=1,\dots,n),$ ordered like the elements of $\Omega.$

To each nonempty convex subset $A$ of $\Omega,$ we can now associate
an interval $f(A)\subseteq\R$: the convex
closure of $\bigcup_{a_i\in A} I_i.$
It is straightforward to verify that for nonempty convex
subsets $A$ and $B$ of $\Omega,$ we have $A\cap B\neq\emptyset$ if
and only if $f(A)\cap f(B)\neq\emptyset.$
(The forward implication is immediate; conversely, if
$A$ and $B$ are disjoint, one can see from their
convexity that $f(A)$ and $f(B)$ will be disjoint.)
Applying $f$ to the members of $\cC^+,$ all of which
are convex in $(\Omega,\leq),$ we get the desired representation
of the intersection graph of $\cC^+$ as an interval graph.

Conversely, suppose the intersection graph of $\cC^+$ is
an interval graph,
i.e., that there exists a map $f$ carrying members of $\cC^+$
to intervals in the real line, such that
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.nonempty}
$f(A)\cap f(B)\neq\emptyset$ \quad if and only if \quad
$A\cap B\neq\emptyset.$
\end{minipage}\end{equation}
%
Since distinct singletons $\{a\}$ and $\{b\}$ $(a, b\in\Omega)$
are disjoint,~\eqref{d.nonempty} implies that
the $f(\{a\})$ $(a\in\Omega)$ will
be disjoint intervals, hence this family
of intervals has a natural ordering based on the ordering of $\R.$
In other words, there is a way of listing
the elements of $\Omega$ as $a_1,\dots,a_n$ so that, writing
$f(\{a_i\})=[s_i,t_i],$ we have $s_1<t_1<s_2<t_2<\dots<s_n<t_n.$
Hence let us order $\Omega$ by setting $a_1<\dots<a_n.$

For each $a\in\Omega$ and nonempty $A\in\cC,$ note that
%
\begin{equation}\begin{minipage}[c]{35pc}\label{d.in_iff}
$a\in A\ \iff\ \{a\}\cap A\neq\emptyset
\ \iff\ f(\{a\})\cap f(A)\neq\emptyset,$
\end{minipage}\end{equation}
%
where the second equivalence holds by~\eqref{d.nonempty}.
Now the convexity of $f(A),$
together with the fact that the $f(\{a_i\})$ $(i=1,\dots,n)$
form an ordered string of disjoint intervals, shows that
those $f(\{a_i\})$ that are contained in $f(A)$ form a consecutive
substring of this string of intervals, whence by~\eqref{d.in_iff}
the set of $a\in A$ is a consecutive string under our
ordering of $\Omega;$ so every nonempty $A\in\cC$ is
indeed convex under that ordering.
$\cC$ might also contain $\emptyset,$ which we
had to exclude from $\cC^+;$ but $\emptyset$ is vacuously convex,
so our proof of~(i) is complete.
\end{proof}

Note that since we have been considering finite graphs only,
in the above result we had to take not only
$\cC,$ but also $\Omega$ to be finite; something I avoided
doing in earlier sections so that we could
make use of Lemma~\ref{L.inf<fin}.
However, given a not necessarily finite set $\Omega$ and a finite
set $\cC$ of subsets of $\Omega,$ we can proceed as follows.
For $a,b\in\Omega,$ let $a\sim b$ if and only
if the set of members of $\cC$ containing $a$ is the same
as the set of those containing $b.$
This is an equivalence relation on $\Omega$
with $\leq 2^{\r{card}(\cC)}$ equivalence classes.
Let $\Omega_0\subseteq\Omega$ be a set of
representatives of these finitely many equivalence classes,
noting that for $A\neq B$ in $\cC,$ we have
$A\cap\Omega_0\neq B\cap\Omega_0,$
and let $\cC_0=\{A\cap\Omega_0\mid A\in\cC\},$
a set of subsets of $\Omega_0.$
Then, on the one hand, if every member of $\cC$ is convex
under an ordering of $\Omega,$ every
member of $\cC_0$ is clearly convex
under the induced ordering of $\Omega_0.$
On the other hand, if there is an ordering $\leq_0$ of $\Omega_0$
under which all members of $\cC_0$ are convex,
we can construct an ordering $\leq$ of $\Omega$ by putting an
arbitrary internal total ordering on
each equivalence class under $\sim,$
and arranging those classes one above
another as their representatives are arranged in $\Omega_0.$
Then we see that all members of $\cC$ will be convex under the
resulting ordering.

Proposition~\ref{P.DWM} gives criteria for
the members of $\cC_0$ to be convex under an ordering of $\Omega_0,$
and as we have seen, this is equivalent to the existence of
an ordering of $\Omega$ under which the members of $\cC$ are convex.

Finally, we can apply Lemma~\ref{L.inf<fin} to get criteria
for such an ordering to exist in the case of infinite~$\cC.$

Two variants of the approach of
Proposition~\ref{P.DWM} were pointed out by
Martin Milani\v{c} (personal communication):

On the one hand, one may consider a family $\cC$ of subsets of
a set $\Omega$ as
determining a {\em bipartite} graph, where one family of vertices
corresponds to the points of $\Omega$ and the other
to the elements of $\cC,$ and an edge connects the vertex
corresponding to $p\in\Omega$ with the one corresponding to
$S\in\cC$ if and only if $p\in S.$
Results are known on when such a bipartite graph corresponds
to a family $\cC$ of convex sets under an ordering on
$\Omega$~\cite[\S\,9.7.2]{gr_clss}.

On the other hand, a pair $(\Omega,\,\cC)$ can be regarded
as a {\em hypergraph},
with $\Omega$ the set of vertices, and $\cC$ the set of hyperedges.
The question of when the hyperedges of a hypergraph are intervals
under some ordering of the vertex-set is studied
in~\cite{int_hyp}; see also~\cite[\S\,8.7]{gr_clss}.

\section{Acknowledgements}\label{S.Ackn}
I am indebted to Friedrich Wehrung for raising the
question~\eqref{d.FW_q} and for helpful comments on the first
version of this note,
to Dave Witte Morris and Martin Milani\v{c}
for the material of~\S\ref{S.int_grph}, and to the
referees for much useful information and advice.

The subject of this paper is far from my areas of expertise, and I
am not in a position to absorb the large amount of related literature
that has been brought to my attention.
One of the referees recommends \cite{ref_5}
as an exposition of work that has been done in this area.
I list below, after the references actually cited in this note,
as {\em Further Related Literature},
a number of other relevant works kindly
pointed out to me by that referee, by
Martin Milani\v{c}, and by Jean-Paul Doignon.

\begin{thebibliography}{00}

\bibitem{graph} R. Balakrishnan and K. Ranganathan,
{\em A textbook of graph theory,}
Second edition. Universitext. Springer, New York, 2012.
MR2977757

\bibitem{gr_clss} Andreas Brandst\"{a}t, Van Bang Le and
Jeremy P. Spinrad,
{\em Graph classes: a survey,}
SIAM Monographs on Discrete Mathematics and Applications, 1999.
xii+304\,pp.
MR1686154

\bibitem{ref_1} B-M. Bui-Xuan, M. Habib, M. Rao,
{\em Tree-representation of set families and applications to
combinatorial decompositions},
European J. Combin. {\bf 33} (2012) 688-711.
MR2889509

\bibitem{ref_3} M. Chein, M. Habib, M. C. Maurer,
{\em Partitive hypergraphs},
Discrete Math. {\bf 37} (1981), no. 1, 35-50.
MR0676409

\bibitem{PMC.UA} P. M. Cohn,
{\em Universal Algebra,}
second edition, Reidel, 1981.
MR0620952

\bibitem{ref_5} A. Ehrenfeucht, T. Harju, G. Rozenberg,
{\em The theory of 2-structures. A framework for decomposition
and transformation of graphs},
World Scientific Publishing Co., Inc., River Edge, NJ, 1999.
MR1712180

\bibitem{Fishburn} Peter C. Fishburn,
{\em Interval orders and interval graphs.
A study of partially ordered sets,}
Wiley-Interscience Series in Discrete Mathematics.
1985. xi+215 pp.
% ISBN: 0-471-81284-6
MR0776781

\bibitem{frBA} Steven Givant and Paul Halmos,
{\em Introduction to Boolean algebras,}
Undergraduate Texts in Mathematics, Springer, 2009. xiv+574 pp.
MR2466574

\bibitem{ref_8} M. Habib,
{\em Substitution des structures combinatoires},
Th\'{e}orie et algorithmes.
Doctoral Dissertation,
Univ. P. et M. Curie, Paris, 1981.

% \bibitem{MT} Wilfrid Hodges,
% {\em Model theory,}
% Encyclopedia of Mathematics and its Applications, {\bf 42},
% Cambridge University Press. xiv+772\,pp.
% MR1221741

\bibitem{hsu} Wen Lian Hsu,
{\em A simple test for interval graphs,}
pp.\,11-16 in
{\em Graph-theoretic concepts in computer science,}
({\em Wiesbaden-Naurod, 1992}),
Lecture Notes in Comput. Sci.,
657, Springer, Berlin, 1993.
MR1244121

\bibitem{int_hyp} Arnold L. Rosenberg,
{\em Interval hypergraphs}, pp.\,27-44 in
{\em Graphs and algorithms
\textup{(}Boulder, CO, 1987\textup{)}},
Contemp. Math., 89, Amer. Math. Soc., Providence, RI, 1989.
MR1006474

\bibitem{FW_r-l} Friedrich Wehrung,
{\em Right-orderability versus left-orderability for monoids,}
Semigroup Forum {\bf 102} (2021) 885-899.
MR4261323
% \url{https://doi.org/10.1007/s00233-021-10185-y}\,.
% Preprint at \url{https://hal.archives-ouvertes.fr/hal-02872310/}\,.

\bibitem{Wiki_int_graph}
Wikipedia, {\em Interval graph}, % section on {\em Characterizations},
\url{https://en.wikipedia.org/wiki/Interval_graph#Characterizations}\,.

\vspace{.7em}
\needspace{3em}
\hspace*{15em} FURTHER RELATED LITERATURE
\vspace{.5em}

\bibitem{mlnc_7} Kellogg S. Booth and George S. Lueker,
{\em Testing for the consecutive ones property, interval graphs,
and graph planarity using PQ-tree algorithms},
Journal of Computer and System Sciences,
{\bf 13} (1976) 335-379.
\url{https://doi.org/10.1016/S0022-0000(76)80045-1}.
MR0433962

\bibitem{ref_2} A. Boussa\"{\i}ri, P. Ille and R. E. Woodrow,
{\em  Primitive bound of a 2-structure},
J. Comb., {\bf 7} (2016) 543-594.
MR3538155

\bibitem{mlnc_9} Lin Chen and Yaacov Yesha,
{\em Parallel recognition of the consecutive ones property with
applications},
Journal of Algorithms, {\bf 12} (1991) 375-392.
\url{https://doi.org/10.1016/0196-6774(91)90010-V}.
MR1114917

\bibitem{ref_4} B. Courcelle and C. Delhomm\'{e},
{\em The modular decomposition of countable graphs.
Definition and construction in monadic second-order logic},
Theoretical Computer Science, {\bf 394} (2008) 1-38.
MR2399790

\bibitem{mlnc_13} E. Dahlhaus,
{\em Improved efficient parallel algorithms to recognize interval
graphs and interval hypergraphs},
Proceedings of the Thirtieth Hawaii
International Conference on System Sciences, Wailea, HI, USA, 1997,
pp.\,172-181, vol.1.
\url{https://doi.org/10.1109/HICSS.1997.667212}.
% no MR

\bibitem{Dgn_5} Jes\'{u}s A. de Loera, Xavier Goaoc,
Fr\'{e}d\'{e}ric Meunier and Nabil H. Mustafa,
{\em The discrete yet ubiquitous theorems of
Carath\'{e}odory, Helly, Sperner, Tucker, and Tverberg},
Bull.\,A.\,M.\,S. (N.\,S.), {\bf 56} (2019) 415-511.
\url{https://doi.org/10.1090/bull/1653}.
MR3974609

\bibitem{mlnc_15} Guoli Ding,
{\em On interval clutters},
Discrete Mathematics, {\bf 254} (2002) 89-102.
\url{https://doi.org/10.1016/S0012-365X(01)00354-5}.
MR1909862

\bibitem{mlnc_6} Michael Dom,
{\em Algorithmic aspects of the consecutive-ones property},
Bull. Eur. Assoc. Theor. Comput. Sci. EATCS,
{\bf 98} (2009) 27-59.
\url{https://eatcs.org/images/bulletin/beatcs98.pdf}.
MR2568235

\bibitem{mlnc_14} Pierre Duchet,
{\em Classical Perfect Graphs: An introduction with emphasis
on triangulated and interval graphs},
Ed.: C. Berge, V. Chv\'{a}tal,
North-Holland Mathematics Studies,
North-Holland, Volume 88, 1984, pp.\,67-96.
https://doi.org/10.1016/S0304-0208(08)72924-4.
MR0778751

\bibitem{mlnc_4} Kapali P. Eswaran,
{\em Faithful Representation of a Family of Sets by a Set of Intervals},
SIAM Journal on Computing, {\bf 4} (1975) 56-68.
\url{https://doi.org/10.1137/0204005}.
MR0378509

\bibitem{Dgn_1} S. Foldes and S. Radeleczki,
{\em On interval decomposition lattices},
Discussiones Mathematicae-General Algebra and Applications,
{\bf 24} (2004) 95-114.
MR2118158

\bibitem{ref_6} R. Fra\"{\i}ss\'{e},
{\em L'intervalle en th\'{e}orie des relations; ses
g\'{e}n\'{e}ralisations;
filtre intervallaire et cl\^{o}ture d'une relation},
Orders: description and roles.
(L'Arbresle, 1982), 313-341,
North-Holland Math. Stud., 99, North-Holland, Amsterdam, 1984.
MR0779858

\bibitem{ref_7} T. Gallai,
{\em Transitiv orientbare Graphen},
Acta Math. Acad. Sci. Hungar., {\bf 18} (1967) 25-66
English translation by F. Maffray and M. Preissmann in
J. J. Ramirez-Alfonsin and B. Reed (Eds),
{\em Perfect graphs,} Wiley 2001, pp.25-66.
MR0221974.

\bibitem{mlnc_1} F. Glover,
{\em Maximum Matching in a Convex Bipartite Graph,}
Naval Research Logistics Quarterly, {\bf 14} (1967) 313-316.
% https://leeds-faculty.colorado.edu/glover/fred%20pubs/7%20-%20Max%20Match%20Conv%20BiPart%20Graph.pdf
% (no MR review)

\bibitem{mlnc_17} Martin Charles Golumbic,
{\em Algorithmic aspects of intersection graphs and representation
hypergraphs}, Graphs and Combinatorics, {\bf 4} (1988) 307-321.
\url{https://doi.org/10.1007/BF01864170}.
MR0965386

\bibitem{Dgn_2} Martin Charles Golumbic,
{\em Algorithmic graph theory and perfect graphs},
Second Edition, Annals of Discrete Mathematics, v.57, 2004,
Elsevier Science B.V., Amsterdam.
MR2063679

\bibitem{mlnc_8} Michel Habib, Ross McConnell, Christophe Paul and
Laurent Viennot,
{\em Lex-BFS and partition refinement, with applications to transitive
orientation, interval graph recognition and consecutive ones testing},
Theoretical Computer Science, {\bf 234} (2000) 59-84.
\url{https://doi.org/10.1016/S0304-3975(97)00241-7}.
MR1745069

\bibitem{ref_9} P. Ille,
{\em L'ensemble des intervalles d'une multirelation
binaire et r\'{e}flexive},
Z. Math. Logik Grundlag. Math.,
{\bf 37} (1991) 227-256.
MR1155394

\bibitem{Dgn_3} R. M. McConnell and F. de Montgolfier,
{\em Algebraic operations on PQ trees and modular decomposition trees},
pp.\,421-432 in,
{\em Graph-theoretic concepts in computer science,}
Springer, Berlin, Lecture Notes in Computer Science,
v.\,3787, 2005.
MR2213890

\bibitem{mlnc_11} John I. Moore,
{\em Interval hypergraphs and $\!D\!$-interval hypergraphs},
Discrete Mathematics, {\bf 17} (1977) 173-179.
\url{https://doi.org/10.1016/0012-365X(77)90148-0}.
MR0437403

\bibitem{mlnc_10} N. S. Narayanaswamy and R. Subashini,
{\em A new characterization of matrices with the consecutive
ones property},
Discrete Applied Mathematics,
{\bf 157} (2009) 3721-3727.
\url{https://doi.org/10.1016/j.dam.2009.08.001}.
MR2556511

\bibitem{Dgn_6} Maurice Queyranne and Fabio Tardella,
{\em Carath\'{e}odory, Helly and Radon
numbers for sublattice and related convexities,}
Math. Oper. Res. {\bf 42} (2017) 495-516.
MR3652003

\bibitem{mlnc_16} A. Quilliot and Sun Xiao Chao,
{\em Algorithmic characterizations of interval ordered
hypergraphs and applications},
Discrete Applied Mathematics, {\bf 51} (1994) 159-170.
\url{https://doi.org/10.1016/0166-218X(94)90105-8}.
MR1279631

\bibitem{mlnc_2} Jeremy P. Spinrad,
{\em Efficient graph representations,}
Fields Institute Monographs, 19. American Mathematical Society,
2003. xiii+342 pp.
MR1971502

\bibitem{mlnc_5,Dgn_4} William T. Trotter and John I. Moore,
{\em Characterization problems for graphs, partially ordered sets,
lattices, and families of sets},
Discrete Math., {\bf 16} (1976) 361-381.
https://doi.org/10.1016/S0012-365X(76)80011-8
MR0450140

\bibitem{mlnc_3} Alan Tucker,
{\em A structure theorem for the consecutive 1's property},
