% LaTeX2e file for a 12-page document
%
% P.J. Tanenbaum, _Bound Graph Polysemy_
%
\documentclass[12pt]{article}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000),
\#R43
\hfill}
\thispagestyle{empty}
\textwidth 6in
\textheight 8.5in
\oddsidemargin .2in
\evensidemargin .2in
%
\newcommand{\setofall}[2]{\{#1 \;|\; #2\}}
\newcommand{\isomorphic}{\cong}
\newcommand{\E}{\mbox{$\cal E$}}
\newcommand{\N}{\mbox{N}}
\newcommand{\height}{\mbox{height}}
\newcommand{\dual}[1]{#1^d}
\newcommand{\rclass}[3]{{#1}_{#2}(#3)}
\newcommand{\downset}[2]{\rclass{#1}{\leq}{#2}}
\newcommand{\upset}[2]{\rclass{#1}{\geq}{#2}}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
%
% The proof environment and the \halmos macros
%
\newenvironment{proof}{{\sc Proof.}}{\halmos*}
\makeatletter
\newcommand{\halmos}{\@ifstar{\rule{1ex}{.9em}}
{\raisebox{.3em}{\framebox[1ex]{\rule{0ex}{.3em}}}
}}
\begin{document}
\begin{center}
{\Large Bound Graph Polysemy} \\
\bigskip
{\large Paul J. Tanenbaum} \\
\medskip
U.S. Army Research Laboratory \\
Aberdeen Proving Ground, Maryland 21005-5068 U.S.A. \\
\texttt{pjt@arl.army.mil} \\
\bigskip
Submitted: January 26, 2000; Accepted: August 15, 2000
\end{center}
\begin{abstract}
{\em Bound polysemy}
is the property of any pair $(G_1, G_2)$ of graphs
on a shared vertex set $V$
for which there exists a partial order on $V$
such that any pair of vertices has an upper bound
precisely when the pair is an edge in $G_1$
and a lower bound
precisely when it is an edge in $G_2$.
We examine several special cases
and prove a characterization
of the bound polysemic pairs
that illuminates a connection with the squared graphs.
\end{abstract}
\begin{center}
2000 {\em Mathematics Subject Classification}.
Primary 05C62, 06A07.
\end{center}
\section{Introduction}
McMorris and Zaslavsky
\cite{mz:bgpos:82}
define an {\em upper bound graph}
as any graph whose vertices may be partially ordered
in such a way that distinct vertices have an upper bound
if and only if they are adjacent.
This class of graphs has been studied widely
\cite{bj:ubgpos:88,bj:gbulbgop:89,chhl:sg:88,et:ubgcubg:98,mm:surubg:83}
since its introduction.
An excellent current survey of the field may be found in
\cite{mm:tigt:99}.
It is straightforward to see that
the {\em lower bound graphs},
defined analogously,
constitute precisely the same class.
In general,
a poset realizes two graphs simultaneously:
one is its upper bound graph
and another, its lower bound graph.
These graphs may be thought of as two meanings of the poset,
two answers to the question,
``What is this poset trying to tell me?''
We call a pair of graphs $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$
on a common vertex set {\em bound polysemic}
provided there exists
a partial order $\leq$ on V such that
distinct $u, v \in V$
have an upper bound in $(V, \leq)$
if and only if
$uv \in E_1$
and a lower bound
if and only if
$uv \in E_2$.
If such a partial order exists,
the poset $(V, \leq)$ is called a {\em bound polysemic realization}
of $(G_1, G_2)$.
Polysemic pairs of graphs
are introduced in
\cite{t:sirpg:99},
which addresses
intersection polysemy:
the pairs of intersection graphs that arise from families of sets
and of those sets' complements.
Notions of polysemy for posets
are explored in
\cite{t:sriico:96}
and
\cite{tw:sdrmp:96}.
Although they do not highlight
the polysemy phenomenon,
Lundgren, Maybee, and McMorris
\cite{lmm:tgicgbg:88}
and Bergstrand and Jones
\cite{bj:gbulbgop:89}
investigate a closely related problem.
Call a pair of graphs $G_1$ and $G_2$
for which $|V(G_1)| = |V(G_2)|$
{\em unlabeled bound polysemic}
provided that they are isomorphic, respectively,
to graphs $H_1$ and $H_2$
that are themselves bound polysemic.
A result in
\cite{lmm:tgicgbg:88}
amounts to
a characterization of the unlabeled bound polysemic pairs.
In some contexts
where it is important to contrast it with
unlabeled bound polysemy,
we refer to bound polysemy as {\em labeled}.
Consider the morphisms that carry adjacency in the graphs
to boundedness (above and below, respectively) in the poset,
and assume without loss of generality that the graphs
have the same vertex set.
In the case of unlabeled polysemy,
the two morphisms are independent of one another,
whereas in the labeled case
a single morphism does double duty.
We think of the two cases in terms of labeling
because if one tagged the vertices with their images
under these morphisms,
precisely the labeled case would result in a consistent assignment of
tags.
We present here a characterization of the labeled bound polysemic pairs,
which hints at a connection to the squared graphs.
The remainder of this section
gives some basic definitions.
Section~\ref{sec:bkgrd}
surveys several results by way of background.
Section~\ref{sec:unlab}
discusses known results for unlabeled bound polysemy.
Section~\ref{sec:spec}
addresses several special cases of bound polysemy.
Section~\ref{sec:genl}
proves more general results,
including our characterization of the bound polysemic pairs.
And
Section~\ref{sec:conc}
concludes with some open problems.
All graphs considered here are finite and simple.
The {\em open neighborhood} of a vertex $v$ in a graph $(V,E)$
is the set $\N(v) = \setofall{u \in V}{uv \in E}$,
and the {\em closed neighborhood}
is the set $\N[v] = \N(v) \cup \{v\}$.
A {\em clique} in a graph is any complete induced subgraph
and need not be maximal with that property.
Cliques are often identified with their vertex sets.
A vertex $v$ is {\em simplicial} in some graph
provided that $\N(v)$ is a clique.
An {\em edge clique cover} of a graph $G$
is a set $\E$ of cliques of $G$
such that every edge $uv$ of $G$,
seen as a 2-set,
is contained in some member of $\E$.
All posets $P = (X, \leq)$ considered here
are finite and reflexive.
Where several partial orders are being discussed,
we sometimes append subscripts
to their symbols,
as $\leq_P$,
to avoid ambiguity.
The {\em height} of a poset
is the maximum cardinality $h$ of any chain
$x_1 < x_2 < \cdots < x_h$ in the poset.
A poset is {\em bipartite} provided that its height is at most 2.
The {\em upset} of an element $x$ in a poset $P = (X, \leq)$
is the set $\upset{X}{x} = \setofall{y \in X}{y \geq x}$.
The set $\max(P)$ of {\em maximals} of $P$
contains precisely those elements
$x \in X$ for which $\upset{X}{x} = \{x\}$.
The {\em downset} $\downset{X}{x}$ of $x$
and the minimals $\min(P)$ of $P$
are defined analogously.
An element $y$ of $P$ {\em covers} another element $x$
provided that $x < y$ and there exists no $z \in X$ with
$x < z < y$.
The {\em dual} of a poset $P = (X, \leq)$
is the poset $\dual{P} = (X, \geq)$
obtained by reversing the sense of every comparability of $P$.
Poset duality runs throughout this topic:
pairs of dual concepts include
upsets and downsets,
minimality and maximality,
and
boundedness above and below.
And by dualizing posets we obtain an immediate proof
that bound polysemy
is a symmetric relation on the graphs with a given vertex set.
The {\em comparability graph} of a poset $(X, \leq)$
has vertex set $X$
and an edge $xy$ for each comparability $x < y$.
A poset is {\em connected} precisely when its comparability graph
is connected.
A {\em fence} is a poset whose comparability graph is a path.
For further definitions, notation, and background information,
see for instance \cite{t:cposdt:92}
and \cite{w:igt:96}.
\section{Background}
\label{sec:bkgrd}
Among the previous results that we use are
four characterizations of the upper bound graphs.
The first one is an easy observation.
The other, more interesting, characterizations
are taken from the literature.
\begin{observation}
The upper (resp. lower) bound graph of a poset
is exactly the intersection graph of the upsets (resp. downsets)
of the poset.
\label{obs:upset}
\end{observation}
\begin{theorem}[McMorris and Zaslavsky]
A graph is an upper bound graph
if and only if
it has an edge clique cover
$\E = \{Q_1, \ldots, Q_r\}$
for which there exists a
system $\{v_1, \ldots, v_r\}$
of distinct representatives
such that $v_i \in Q_j$ precisely when $i = j$.
\halmos
\label{thm:mz}
\end{theorem}
The next characterization makes use of the notion of
an {\em ordered edge cover}
of a graph $G$---%
an edge clique cover $\{Q_1, \ldots, Q_n\}$ of $G$
together with a labeling $\{v_1, \ldots, v_n\}$ of $V(G)$
such that
each $v_i$ is in $Q_i$
and if $v_i \in Q_j$,
then $i \leq j$ and $Q_i \subseteq Q_j$.
\begin{theorem}[Lundgren and Maybee \cite{lm:cubg:83}]
A graph $G$ is an upper bound graph
if and only if
it has an ordered edge cover.
\halmos
\label{thm:lm}
\end{theorem}
The proof of Theorem~\ref{thm:mz}
proceeds by establishing a straightforward identity between
the graph's distinct representatives
and their corresponding cliques on the one hand,
and the poset's maximals
and their respective downsets on the other.
In much the same way,
Theorem~\ref{thm:lm} may be proven
\cite{lmm:tgicgbg:88}
by identifying
the vertex labeling and cliques of the graph
with a linear extension and all the downsets of the poset.
The third characterization
was published independently in
\cite{bj:ubgpos:88}
and
\cite{chhl:sg:88}.
\begin{theorem}[Bergstrand and Jones, Cheston et al.]
A graph is an upper bound graph
if and only if
each of its edges is in the closed neighborhood
of some simplicial vertex.
\halmos
\label{thm:simp}
\end{theorem}
Another class of graphs that has been characterized
in terms of edge clique covers is the squared graphs.
A graph $G = (V, E)$ is {\em squared}
provided that there exists a graph $S$ on $V$
such that $u, v \in V$ are adjacent in $G$
if and only if $d_S(u, v) \leq 2$.
Such a graph $S$ is called a {\em square root} of $G$.
This notion of multiplication
is motivated by the identification
of a graph with its adjacency matrix.
Mukhopadhyay \cite{m:srg:67}
characterized the squared graphs as follows.
\begin{theorem}[Mukhopadhyay]
A graph on $V = \{v_1, \ldots, v_n\}$ has a square root
if and only if
it has an edge clique cover
$\E = \{Q_1, \ldots, Q_n\}$
with the properties that
\begin{enumerate}
\item for $1 \leq i \leq n$,
$v_i \in Q_i$
and
\item for $1 \leq i < j \leq n$,
$v_i \in Q_j$ if and only if $v_j \in Q_i$.
\halmos
\end{enumerate}
\label{thm:sqrt}
\end{theorem}
\section{The Unlabeled Case}
\label{sec:unlab}
Recall that unlabeled bound polysemy
consists in a pair of graphs that are
isomorphic, respectively,
to the upper and lower bound graphs of a single poset.
Lundgren, Maybee, and McMorris
\cite{lmm:tgicgbg:88}
give a characterization of these pairs.
\begin{theorem}[Lundgren, Maybee, and McMorris]
Given graphs $G_1$ and $G_2$ with the same number of vertices,
the following are equivalent:
\begin{enumerate}
\item $G_1$ and $G_2$ are unlabeled bound polysemic.
\item $G_1$ is (isomorphic to)
the intersection graph
of some ordered edge cover of $G_2$.
\item $G_2$ is (isomorphic to)
the intersection graph
of some ordered edge cover of $G_1$.
\halmos
\end{enumerate}
\label{thm:lmm}
\end{theorem}
%
This result follows
from Observation~\ref{obs:upset} and Theorem~\ref{thm:lm}.
Its third condition,
for instance,
translates to the assertion that
$G_1$ has an upper bound realization
whose downsets, under intersection, yield $G_2$.
Bergstrand and Jones
\cite{bj:gbulbgop:89}
provide the first examples of
graphs
that we would describe as unlabeled bound polysemic with themselves.
A representative member $G$ of one family of such graphs
is shown in Figure~\ref{fig:unlab}.
%
\begin{figure}[th]
\setlength{\unitlength}{4mm}
\newcommand{\diameter}{.35}
\begin{center}
\begin{picture}(25,10)(0,0)
%
% K_u
%
\put( 5, 7){\circle*{\diameter}} % u
\put( 9, 7){\circle*{\diameter}} % v
\put( 9,10){\circle*{\diameter}} % p_1'
\put( 5,10){\circle*{\diameter}} % u'
\put( 5, 7){\line( 1, 0){4}}
\put( 5, 7){\line( 4, 3){4}}
\put( 5, 7){\line( 0, 1){3}}
\put( 9,10){\line( 0,-1){3}}
\put( 9,10){\line(-1, 0){4}}
\put( 9, 7){\line(-4, 3){4}}
%
% K_v
%
\put( 4, 4){\circle*{\diameter}} % q_1'
\put(10, 4){\circle*{\diameter}} % q_2'
\put( 7, 2){\circle*{\diameter}} % v'
\put( 9, 7){\line(-5,-3){5}}
\put( 9, 7){\line(-2,-5){2}}
\put( 9, 7){\line( 1,-3){1}}
\put( 5, 7){\line( 5,-3){5}}
\put( 5, 7){\line( 2,-5){2}}
\put( 5, 7){\line(-1,-3){1}}
\put(10, 4){\line(-6, 0){6}}
\put(10, 4){\line(-3,-2){3}}
\put( 7, 2){\line(-3, 2){3}}
%
% The pendants
%
\put( 2, 8){\circle*{\diameter}} % p_1
\put( 2, 8){\line( 3,-1){3}}
\put(12, 7){\circle*{\diameter}} % q_1
\put(12, 7){\line(-3, 0){3}}
\put(12, 6){\circle*{\diameter}} % q_2
\put(12, 6){\line(-3, 1){3}}
% Label things
\put(4.5, 7.8){\makebox(0,0){$u$}}
\put(9.6, 7.8){\makebox(0,0){$v$}}
\put(4.5,10.2){\makebox(0,0)[r]{$u'$}}
\put(9.6,10.2){\makebox(0,0)[l]{$p_1'$}}
\put(1.2, 8.2){\makebox(0,0){$p_1$}}
\put(12.9, 7.0){\makebox(0,0){$q_1$}}
\put(12.9, 5.8){\makebox(0,0){$q_2$}}
\put(7.4, 1.7){\makebox(0,0)[l]{$v'$}}
\put(3.2, 3.7){\makebox(0,0){$q_1'$}}
\put(10.9, 3.6){\makebox(0,0){$q_2'$}}
%
\put(7.0, 0.5){\makebox(0,0)[t]{(a) $G$}}
%
% UB Rep. of G
%
\put(16, 7){\circle*{\diameter}} % p_1
\put(18, 7){\circle*{\diameter}} % u'
\put(20, 7){\circle*{\diameter}} % v'
\put(22, 7){\circle*{\diameter}} % q_1
\put(24, 7){\circle*{\diameter}} % q_2
\put(16, 4){\circle*{\diameter}} % p_1'
\put(18, 4){\circle*{\diameter}} % u
\put(20, 4){\circle*{\diameter}} % v
\put(22, 4){\circle*{\diameter}} % q_1'
\put(24, 4){\circle*{\diameter}} % q_2'
\put(16, 4){\line( 2, 3){2}}
\put(18, 4){\line(-2, 3){2}}
\put(18, 4){\line( 0, 1){3}}
\put(18, 4){\line( 2, 3){2}}
\put(20, 4){\line(-2, 3){2}}
\put(20, 4){\line( 0, 1){3}}
\put(20, 4){\line( 2, 3){2}}
\put(20, 4){\line( 4, 3){4}}
\put(22, 4){\line(-2, 3){2}}
\put(24, 4){\line(-4, 3){4}}
% Label things
\put(16, 7.8){\makebox(0,0)[b]{$p_1$}}
\put(18, 7.8){\makebox(0,0)[b]{$u'$}}
\put(20, 7.8){\makebox(0,0)[b]{$v'$}}
\put(22, 7.8){\makebox(0,0)[b]{$q_1$}}
\put(24, 7.8){\makebox(0,0)[b]{$q_2$}}
\put(16, 3.2){\makebox(0,0)[t]{$p_1'$}}
\put(18, 3.2){\makebox(0,0)[t]{$u$}}
\put(20, 3.2){\makebox(0,0)[t]{$v$}}
\put(22, 3.2){\makebox(0,0)[t]{$q_1'$}}
\put(24, 3.2){\makebox(0,0)[t]{$q_2'$}}
\put(20, 0.5){\makebox(0,0)[t]{(b) A realization $P$ of $(G, G)$}}
\end{picture}
\end{center}
\caption{\label{fig:unlab}
A graph that is unlabeled bound polysemic with itself}
\end{figure}
%
Any graph in this family consists of cliques $K_u$ and $K_v$
that intersect in an edge $uv$
and that each have at least one other vertex,
together with $|K_u| - 3$ pendant vertices
$p_1, \ldots, p_{|K_u| - 3}$ adjacent to $u$
and $|K_v| - 3$ pendant vertices
$q_1, \ldots, q_{|K_v| - 3}$ adjacent to $v$.
It is clear that $G$ is the upper bound graph
of the poset $P$ in Figure~\ref{fig:unlab}b:
the annotation in the figure
encodes the morphism carrying adjacency to boundedness above.
And since $P$ is isomorphic to its own dual,
we have also that $G$ is isomorphic to the lower bound graph of $P$.
So $P$ is an unlabeled bound polysemic realization of $G$.
Although $G$ is unlabeled bound polysemic (with itself),
it is not bound polysemic.
To see this, consider any upper bound realization $P'$ of $G$.
Each of $q_1$ and $q_2$ must have an upper bound in $P'$ with $v$
and with no other vertex,
so each is comparable to $v$ and to no other.
Thus $v <_{P'} q_1, q_2$.
But then $v$ is a lower bound for $q_1$ and $q_2$.
So every lower bound graph of $P'$ must include edge $q_1 q_2$,
which $G$ lacks.
It follows that no upper bound realization of $G$
is also a lower bound realization.
\section{Special Cases of Labeled Bound Polysemy}
\label{sec:spec}
We begin our investigation of (labeled) bound polysemy
with results for several special cases.
In contrast to the examples
described in Section~\ref{sec:unlab}---%
graphs that are unlabeled bound polysemic with themselves---%
our first theorem characterizes
the analogous class in the labeled case.
In order to establish that characterization,
we use the following lemma.
\begin{lemma}
If a connected poset $P$ has the property that
any pair of elements has an upper bound
if and only if it has a lower bound,
then $P$ has a maximum and a minimum.
\label{lem:fence}
\end{lemma}
\begin{proof}
Note that the connectedness of $P$
implies that for any elements $a$ and $b$ of $P = (X, \leq)$
there is a fence $F = (Y, \leq_F)$
induced in $P$ with $a$ and $b$ as its endpoints.
We show by induction on the cardinality of $F$
that there exist $\alpha_F, \omega_F \in X$
such that
$\alpha_F \leq f \leq \omega_F$ for all $f \in F$.
In particular, then,
$a$ and $b$ have both an upper and a lower bound.
The base cases $|F| = 0, 1, 2$ are trivial.
For the inductive step,
let $|F| > 2$
and assume that $b$ is minimal in $F$
(the dual case may be argued analogously).
Let $F' = F - b$
and consider $\alpha_{F'}, \omega_{F'} \in X$
as are guaranteed to exist by the inductive hypothesis.
Since $b <_F f_i$ for some $f_i \in Y$,
we also have $b < f_i \leq \omega_{F'}$,
so $b$ and $\alpha_{F'}$ have an upper bound.
This means that they also have a lower bound $\alpha$.
So we choose
$\omega_F = \omega_{F'}$
and
$\alpha_F = \alpha$,
and they have the required property.
Thus, every pair of elements of $P$ has both an upper bound
and a lower bound,
so $P$ must have a maximum and a minimum.
\end{proof}
\begin{theorem}
A graph is bound polysemic with itself
if and only if it is a disjoint union of cliques.
\label{thm:self}
\end{theorem}
\begin{proof}
It is straightforward to see that
any disjoint union $G$ of cliques is bound polysemic with itself.
For each clique,
construct a linear order on its vertices.
Then the sum of these chains realizes $(G, G)$.
Conversely,
let $G = (V, E)$ be any graph
and $P$ be a bound polysemic realization of $(G, G)$.
It is clear that any pair of elements of $P$
has an upper bound if and only if it has a lower bound,
so by Lemma~\ref{lem:fence}
distinct maximals (resp. minimals)
must be in separate components of $P$.
So $G$ must be a disjoint union of cliques.
\end{proof}
\begin{corollary}
Every edgeless graph is bound polysemic with itself
but with no other graph.
\label{cor:edgeless}
\end{corollary}
\begin{proof}
That $G = (V, \emptyset)$ is bound polysemic with itself
follows immediately from Theorem~\ref{thm:self}.
In particular,
the only upper bound realization of $G$
is the antichain on $V$,
so it is clear that no graph on $V$ with at least one edge
is bound polysemic with $G$.
\end{proof}
\begin{theorem}
No graph with more than one vertex
is bound polysemic with its complement.
\end{theorem}
\begin{proof}
Let $P = (V, \leq)$ be an upper bound realization
of a graph $G = (V, E)$ with $n > 1$ vertices.
If $P$ is an antichain,
then $E$ is empty
and the conclusion follows from
Corollary~\ref{cor:edgeless}.
On the other hand,
if there exist $u \leq v$ in $P$,
then they have an upper bound, so $uv \in E$.
But they have a lower bound, too,
even though $uv \not\in \overline{E}$.
So no upper bound realization of $G$
is also a lower bound realization of $\overline{G}$.
\end{proof}
\begin{theorem}
An $n$-vertex graph $G$ is bound polysemic with $K_n$
if and only if
$G$ is an upper bound graph with a vertex of degree $n - 1$.
\end{theorem}
\begin{proof}
Suppose $G$ and $K_n$ to be bound polysemic.
We show that $\Delta(G) = n - 1$.
Any lower bound realization of $K_n$ has a minimum,
since distinct minimals of a poset
cannot have a lower bound
and thus cannot be adjacent in a lower bound graph.
But a minimum of a poset
has an upper bound with every element,
so the minimum of any realization of $(G, K_n)$
has degree $n - 1$ in $G$.
Conversely,
let $G$ be an upper bound graph
and suppose there exists
a vertex $v$ of degree $n - 1$ in $G$.
If $G \isomorphic K_n$,
then the result follows from Theorem~\ref{thm:self}.
Otherwise, $v$ is not simplicial, so by Theorem~\ref{thm:simp}
there exists an upper bound realization $P'$ of $G - v$.
Then the poset $P$ obtained from $P'$
by adding $v$ as a minimum
is an upper bound realization of $G$.
And since $v$ is a lower bound for every pair of elements,
$P$ is also a lower bound realization of $K_n$.
\end{proof}
\begin{theorem}
A graph $G = (V, E_G)$ is bound polysemic
with a tree $T = (V, E_T)$
if and only if
$G$ is complete
and
$T$ is a star.
\label{thm:tree}
\end{theorem}
\begin{proof}
Let $T$ be a star
and select $v \in V$ with degree $\Delta(T)$.
Then the poset $P$ for
which $\min(P) = \{v\}$
and $\max(P) = V \setminus \{v\}$
is an upper bound realization of $T$.
In the trivial case of $|V| = 2$,
$P$ and $\dual{P}$ are the only upper bound realizations of $T$.
For $|V| \neq 2$,
$P$ itself is the only upper bound realization of $T$.
This follows from the facts
that no distinct $x, y \in V \setminus \{v\}$
can even have an upper bound---%
so they certainly cannot be comparable---%
and that if any $x$ were incomparable to $v$,
then $x$ and $v$ would have some upper bound $y \neq v$,
which would imply $xy \in E(G)$.
Note too
that the lower bound graph of $P$,
and of $\dual{P}$ in the case $|V| = 2$,
is the complete graph on $V$.
Conversely,
suppose $T$ is not a star.
Then $|V| = n \geq 4$,
so $T$ has a leaf $u$,
and the neighbor $v$ of $u$
has degree strictly less than $n - 1$.
Thus there exists $w \in V$ not adjacent to $v$
and the $u$-$w$ path has length at least 4,
so $T$ contains an induced $P_4$.
But neither vertex of the internal edge $e$
of an induced $P_4$
can be simplicial,
and $T$ is $K_3$-free.
So $e$ is not in the closed neighborhood of any simplicial vertex,
and it follows from Theorem~\ref{thm:simp} that
$T$ is not an upper bound graph.
\end{proof}
\section{General Results}
\label{sec:genl}
In their proof of Theorem~\ref{thm:mz},
McMorris and Zaslavsky use a construction that demonstrates
that any upper bound realization may be assumed
without loss of generality to be bipartite.
When we consider bound polysemy,
the situation becomes only slightly more complicated.
To begin with,
take the example illustrated in Figure~\ref{fig:ht3}.
%
\begin{figure}[th]
\setlength{\unitlength}{4mm}
\newcommand{\diameter}{.35}
\begin{center}
\begin{picture}(25,10)(0,0)
%
% G_1
%
\put( 4, 8){\circle*{\diameter}} % a
\put( 7, 6){\circle*{\diameter}} % b
\put( 6, 3){\circle*{\diameter}} % c
\put( 2, 3){\circle*{\diameter}} % d
\put( 1, 6){\circle*{\diameter}} % e
\put( 7, 6){\line(-3, 2){3}}
\put( 7, 6){\line(-1, 0){6}}
\put( 7, 6){\line(-5,-3){5}}
\put( 7, 6){\line(-1,-3){1}}
\put( 6, 3){\line(-5, 3){5}}
\put( 6, 3){\line(-1, 0){4}}
\put( 2, 3){\line(-1, 3){1}}
% Label things
\put(3.4, 8.4){\makebox(0,0){$a$}}
\put(7.3, 6.7){\makebox(0,0){$b$}}
\put(6.2, 2.2){\makebox(0,0){$c$}}
\put(1.8, 2.2){\makebox(0,0){$d$}}
\put(1.1, 6.8){\makebox(0,0){$e$}}
%
\put(4.0, 0.5){\makebox(0,0)[t]{(a) $G_1$}}
%
% G_2
%
\put(13, 8){\circle*{\diameter}} % a
\put(16, 6){\circle*{\diameter}} % b
\put(15, 3){\circle*{\diameter}} % c
\put(11, 3){\circle*{\diameter}} % d
\put(10, 6){\circle*{\diameter}} % e
\put(11, 3){\line(-1, 3){1}}
\put(11, 3){\line( 2, 5){2}}
\put(11, 3){\line( 5, 3){5}}
\put(11, 3){\line( 1, 0){4}}
\put(13, 8){\line( 2,-5){2}}
\put(13, 8){\line( 3,-2){3}}
\put(15, 3){\line( 1, 3){1}}
% Label things
\put(12.3, 8.3){\makebox(0,0){$a$}}
\put(16.3, 6.7){\makebox(0,0){$b$}}
\put(15.2, 2.2){\makebox(0,0){$c$}}
\put(10.8, 2.2){\makebox(0,0){$d$}}
\put( 9.9, 6.7){\makebox(0,0){$e$}}
%
\put(13.0, 0.5){\makebox(0,0)[t]{(b) $G_2$}}
%
% The bound polysemic realization
%
\put(19.0, 5.5){\circle*{\diameter}} % a
\put(21.5, 3.0){\circle*{\diameter}} % b
\put(21.5, 5.5){\circle*{\diameter}} % c
\put(21.5, 8.0){\circle*{\diameter}} % d
\put(24.0, 5.5){\circle*{\diameter}} % e
\put(21.5, 3.0){\line( 0, 1){5}}
\put(21.5, 3.0){\line(-1, 1){2.5}}
\put(21.5, 8.0){\line( 1,-1){2.5}}
% Label things
\put(19.0, 6.3){\makebox(0,0){$a$}}
\put(22.3, 3.0){\makebox(0,0){$b$}}
\put(22.3, 5.1){\makebox(0,0){$c$}}
\put(20.7, 8.0){\makebox(0,0){$d$}}
\put(24.5, 4.8){\makebox(0,0){$e$}}
%
\put(21.5, 0.5){\makebox(0,0)[t] {(c) A realization $P$}}
\end{picture}
\end{center}
\caption{\label{fig:ht3}
A bound polysemic pair with no bipartite realization}
\end{figure}
%
It may easily be verified
that the poset $P$
in Figure~\ref{fig:ht3}c
is a bound polysemic realization of $(G_1, G_2)$,
the pair in Figure~\ref{fig:ht3}a and b.
How much flexibility does one have
in constructing a realization of $G_1$ and $G_2$?
Since neither $c$ nor $e$ is adjacent to $a$ in $G_1$
and $c$ is not adjacent to $e$ in $G_2$,
$\{a, c, e\}$ must be an antichain.
Furthermore,
$b$ must have lower bounds with each of $a$, $c$, and $d$,
and it is the only element that can possibly be comparable to $a$.
So $b$ must be below the other three.
Dually,
$d$ is the only element that can be comparable to $e$,
and must be above $b$, $c$, and $e$.
Thus, $P$ is the unique bound polysemic realization of $(G_1, G_2)$,
and, in particular,
$G_1$ and $G_2$ have no bipartite realization.
Our next two results show that,
while bound polysemic realizations of height less than 3
are something of a special case,
height at most 3 may always be assumed.
\begin{theorem}
A bound polysemic pair has a bipartite realization
if and only if
no triple of vertices induces a triangle in both graphs.
Furthermore,
if no such triple exists,
then every realization is bipartite.
\end{theorem}
\begin{proof}
Let $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$
be bound polysemic.
It is a simple matter to verify that
if some distinct $u, v, w \in V$
induce a triangle in both graphs,
then no realization of $(G_1, G_2)$ is bipartite.
Contrapositively,
if they have a bipartite realization,
then no such triple exists.
On the other hand,
if any realization $P = (V, \leq)$
has height at least 3,
then there exist $u < v < w$ in $V$,
so $\{u, v, w\}$ induces a triangle in each graph
and every realization has height at least 3.
\end{proof}
\begin{theorem}
For any poset $P = (X, \leq)$,
let $P' = (X, \leq')$ be the height-3 poset for which
\begin{displaymath}
\leq' \;=\; \bigcup_{y \in \max(P)}
\setofall{(x, y)}{x \leq y}
\;\cup\; \bigcup_{y \in \min(P)}
\setofall{(y, x)}{x \geq y}.
\end{displaymath}
Then $P$ and $P'$ have the same upper bound graph
and the same lower bound graph.
\end{theorem}
\begin{proof}
It is clear that
if $a, b \in X$ have an upper bound in $P$,
then they have one that is maximal,
so they also have an upper bound in $P'$.
Conversely, any upper bound for elements $a$ and $b$ of $P'$
is also an upper bound of $a$ and $b$ in $P$.
So the two posets have the same upper bound graph
and, dually, the same lower bound graph.
\end{proof}
We now present our main result---%
a characterization
of the bound polysemic pairs
that blends the flavors of Theorems~\ref{thm:mz} and \ref{thm:sqrt}.
\begin{theorem}
Graphs $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$
are bound polysemic
if and only if
there exist edge clique covers
$\E_1 = \{Q_{1,1}, \ldots, Q_{1,r}\}$ of $G_1$
and
$\E_2 = \{Q_{2,1}, \ldots, Q_{2,s}\}$ of $G_2$
and disjoint systems $R_1 = \{v_{1,1}, \ldots, v_{1,r}\}$
and $R_2 = \{v_{2,1}, \ldots, v_{2,s}\}$
of distinct representatives
of $\E_1$ and $\E_2$, respectively,
with the properties that
\begin{enumerate}
\item $v_{k,i} \in Q_{k,j}$ precisely when $i = j$,
\label{prop:bound}
\item $\displaystyle \bigcup_{i=1}^r Q_{1,i}
= \displaystyle \bigcup_{i=1}^s Q_{2,i}$, and
\label{prop:union}
\item $Q_{1,i} \cap Q_{2,j}$ is nonempty only if
$v_{1,i} \in Q_{2,j}$ and $v_{2,j} \in Q_{1,i}$.
\label{prop:intersection}
\end{enumerate}
\label{thm:char}
\end{theorem}
\begin{proof}
Property~\ref{prop:bound} is simply
the necessary and sufficient condition
in Theorem~\ref{thm:mz}
for $G_1$ and $G_2$ to be (upper or lower) bound graphs,
independent of one another.
Properties~\ref{prop:union} and \ref{prop:intersection}
together with the requirement that the
two systems $R_1$ and $R_2$ be disjoint
give us the polysemy,
as we now prove.
Our approach is similar to the one used
for Theorems~\ref{thm:mz} and \ref{thm:lm}---%
we establish
for some poset $P = (V, \leq)$
the following identity:
\begin{equation}
\begin{array}{rcl}
R_1 & \leftrightarrow & \max(P) \setminus \min(P) \\
Q_{1,i} & \leftrightarrow & \downset{V}{v_{1,i}} \\
R_2 & \leftrightarrow & \min(P) \setminus \max(P) \\
Q_{2,i} & \leftrightarrow & \upset{V}{v_{2,i}} \\
\end{array} .
\label{eqn:ident}
\end{equation}
We begin by showing that the conditions are necessary
for any realization $P$.
Define $\E_1$, $\E_2$, $R_1$, and $R_2$
as in (\ref{eqn:ident}).
It is clear that $R_1$ and $R_2$ are disjoint.
It also follows immediately,
since $\leq$ is reflexive and no maximal (resp. minimal)
can be in the downset (resp. upset) of any other,
that property~\ref{prop:bound} holds.
Furthermore, $v \in V$
is in some downset in $\E_1$ (resp. upset in $\E_2$)
only if $v$ is not isolated in $P$,
which, in turn, is the case only if
$v$ is in one of the upsets in $\E_2$ (resp. downsets in $\E_1$).
So property~\ref{prop:union} holds.
And finally, if there exists any $v \in Q_{1,i} \cap Q_{2,j}$,
then $v_{2,j} \leq v \leq v_{1,i}$;
so property~\ref{prop:intersection} holds by transitivity.
Conversely,
suppose the edge clique covers $\E_1$ and $\E_2$ and
their respective systems $R_1$ and $R_2$
of distinct representatives exist.
We construct a bound polysemic realization $P = (V, \leq)$
of $(G_1, G_2)$ by defining
\begin{equation}
\begin{array}{ccl}
\leq &=& \displaystyle\bigcup_{i = 1}^r
\setofall{(v, v_{1,i})}{v \in Q_{1,i}}
\;\cup\; \displaystyle\bigcup_{i = 1}^s
\setofall{(v_{2,i}, v)}{v \in Q_{2,i}} \\[4ex]
&& \;\cup\;
\setofall{(v, v)}{v \in V \setminus (R_1 \cup R_2)} .
\end{array}
\label{eqn:leq}
\end{equation}
It is clear from its definition and property~\ref{prop:bound}
that $\leq$ is reflexive.
Property~\ref{prop:bound} also ensures that
if $u \leq v$ and either $u \in R_1$ or $v \in R_2$,
then $u = v$.
So if both $u \leq v$ and $v \leq u$, then $u = v$.
In other words, $\leq$ is antisymmetric.
Is it transitive?
If there exist distinct $u, v, w \in V$
with $u \leq v$ and $v \leq w$,
then $w \in R_1$
and $u \in R_2$.
So $v \in Q_{1,i} \cap Q_{2,j}$,
where $w = v_{1,i}$ and $u = v_{2,j}$.
But then it follows from property~\ref{prop:intersection} that
$w \in Q_{2,j}$
and
$u \in Q_{1,i}$,
and either one of these memberships ensures that $u \leq w$.
So $\leq$ is a partial order.
It remains to demonstrate that $G_1$ and $G_2$ are
the upper and lower bound graphs of $P$, respectively.
We prove the case for $G_1$---%
the other may be obtained from a dual argument.
As a preliminary step,
we prove that $\max(P) \setminus \min(P) \subseteq R_1$.
The opposite containment is immediate,
so the two sets are in fact equal.
To see this,
consider any nonminimal maximal $v$.
There must exist $u \neq v$ for which
$(u, v)$ is a member of
the first or second term of (\ref{eqn:leq}).
If the comparability is in the first term,
then $v \in R_1$ trivially.
If the comparability appears in the second term only,
then $v$ is in some $Q_{2,i}$,
so it follows from property~\ref{prop:union} that
$v$ is also in some $Q_{1,j}$,
and thus,
from property~\ref{prop:bound} that
$v = v_{i,j} \in R_1$.
Finally,
is $G_1$ indeed the upper bound graph of $P$?
Any edge $uv$ of $G_1$ is in at least one clique $Q_{1,i} \in \E_1$.
As a result,
$u$ and $v$ have $v_{1,i}$ as an upper bound in $P$.
Conversely, if distinct $u, v \in V$ have an upper bound,
then there exists $w \in \max(P) \setminus \min(P) = R_1$,
say $w = v_{1,i}$,
such that $u \leq w$ and $v \leq w$.
If the comparability $(u, w)$
is a member of the first term of (\ref{eqn:leq}),
then $u \in Q_{1,i}$.
Otherwise, the comparability is in the second term,
so $u = v_{2,j}$ for some $j$
and $w \in Q_{1,i} \cap Q_{2,j}$.
Thus, by property~\ref{prop:intersection}, $u$ is again in $Q_{1,i}$.
By a parallel argument, $v$, too, is in $Q_{1,i}$,
so $u$ and $v$ are adjacent in $G_1$.
\end{proof}
The similarity of the statements
of Theorems~\ref{thm:char} and \ref{thm:sqrt}
suggests that bound polysemy and squared graphs
are related concepts.
The connection between these concepts
is captured in the following theorem.
\begin{theorem}
If graphs $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$
have a bound polysemic realization $P$
that is bipartite,
then $G_3 = (V, E_1 \cup E_2)$
is a squared graph
with a square root equal to
the underlying graph of the Hasse diagram of $P$.
\end{theorem}
\begin{proof}
We may call $G_3$ the {\em either bound graph} of $P$,
since any distinct elements of $V$ are adjacent in $G_3$
if and only if
they have either an upper or a lower bound in $P$.
It is immediate for any poset,
regardless of height,
that
its comparability graph
is a square root of its either bound graph.
It only remains to demonstrate that
the extra condition that $P$ be bipartite
is sufficient to ensure that
the underlying graph $H$ of the Hasse diagram of $P$
is also a square root of $G_3$.
Note that the closed neighborhood in $H$ of any $w \in V$ is
\begin{displaymath}
N_H[w] = \left\{
\begin{array}{ll}
\downset{V}{w} , & w \in \max(P) \\
\upset{V}{w} , & w \in \min(P) \\
\end{array}
\right. .
\end{displaymath}
Note too that $d_H(u, v) \leq 2$
if and only if either
(1) $u$ and $v$ are comparable,
(2) they are minimals below some common maximal, or
(3) they are maximals above some common minimal.
But these three cases are equivalent, respectively, to
($1'$) $u$ and $v$ have both an upper and a lower bound,
($2'$) they have an upper bound, and
($3'$) they have a lower bound.
\end{proof}
The following theorem is a further parallel
to a result from \cite{mz:bgpos:82}.
It shows that the bound polysemic pairs---%
like the upper bound graphs---%
cannot be characterized in terms of forbidden subgraphs.
\begin{theorem}
For any graphs $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$
on a common vertex set,
there exists a bound polysemic pair $\{G_1', G_2'\}$
such that $G_1$ is an induced subgraph of $G_1'$
and $G_2$ is an induced subgraph of $G_2'$.
\label{thm:4bid}
\end{theorem}
\begin{proof}
For any edge clique covers
$\E_1 = \{Q_{1,1}, \ldots, Q_{1,r}\}$ of $G_1$
and
$\E_2 = \{Q_{2,1}, \ldots, Q_{2,s}\}$ of $G_2$,
we enlarge our set of vertices to
\begin{displaymath}
V' = V \cup \{q_{1,1}, \ldots, q_{1,r}\}
\cup \{q_{2,1}, \ldots, q_{2,s}\} ,
\end{displaymath}
where none of the $q_{k,i}$ is in $V$.
Next we define a partial order $P = (V', \leq)$,
in which
$\{q_{1,1}, \ldots, q_{1,r}\}$,
$V$, and
$\{q_{2,1}, \ldots, q_{2,s}\}$
are antichains
and every $v \in V$
is covered by exactly those $q_{1,i}$ for which $v \in Q_{1,i}$
and covers exactly those $q_{2,i}$ for which $v \in Q_{2,i}$.
Finally, let $G_1'$ and $G_2'$
be the upper and lower bound graphs, respectively, of $P$.
Then $G_1'$ and $G_2'$ are bound polysemic by construction
and each $G_k$ is the subgraph of $G_k'$ induced by $V$.
\end{proof}
\section{Open Problems}
\label{sec:conc}
We have seen that
$((V, \emptyset), (V, \emptyset))$,
$(K_{1,n-1}, K_n)$,
and the pair in Figure~\ref{fig:ht3}
each have a unique bound polysemic realization.
Other such pairs may be obtained from
the graphs with unique upper bound realizations,
which are characterized by McMorris and Myers \cite{mm:surubg:83}.
It remains an open problem to completely characterize
all the bound polysemic pairs that have unique representations.
An interesting algorithmic problem
is the recognition of bound polysemy.
Although Theorem~\ref{thm:4bid} precludes one line of attack,
Bergstrand and Jones
\cite{bj:ubgpos:88}
overcame an analogous situation,
using Theorem~\ref{thm:simp}
to obtain an $O(n^3)$ algorithm to recognize upper bound graphs.
Another open problem is the extension of our results
by generalizing the posets to directed graphs.
The analog of
a poset's upper (resp. lower) bound graph
is a digraph's {\em competition} (resp. {\em common enemy})
{\em graph}.
It would be interesting to investigate what one might call
{\em competition polysemy}.
\newpage
%
% We have reached the end of the document.
% Here's the list of references.
%
\ifx\undefined\bysame
\newcommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\fi
\begin{thebibliography}{10}
\bibitem{bj:ubgpos:88}
D.~J. Bergstrand and K.~F. Jones, {\em On upper bound graphs of partially
ordered sets}, Congr. Numer. {\bf 66} (1988), 185--193.
\bibitem{bj:gbulbgop:89}
\bysame, {\em Graphs that are both the upper and lower bound graphs of a
poset}, Ars Combin. {\bf 28} (1989), 109--121.
\bibitem{chhl:sg:88}
G.~A. Cheston, E.~O. Hare, S.~T. Hedetniemi, and R.~C. Laskar, {\em Simplicial
graphs}, Congr. Numer. {\bf 67} (1988), 105--113.
\bibitem{et:ubgcubg:98}
H.~Era and M.~Tsuchiya, {\em On upper bound graphs whose complements are also
upper bound graphs}, Discrete Math. {\bf 179} (1998), 103--109.
\bibitem{lm:cubg:83}
J.~R. Lundgren and J.~S. Maybee, {\em A characterization of upper bound
graphs}, Congr. Numer. {\bf 40} (1983), 189--193.
\bibitem{lmm:tgicgbg:88}
J.~R. Lundgren, J.~S. Maybee, and F.~R. McMorris, {\em Two-graph inversion of
competition graphs and upper bound graphs}, Congr. Numer. {\bf 67} (1988),
136--144.
\bibitem{mm:tigt:99}
T.~A. McKee and F.~R. McMorris, {\em Topics in intersection graph theory}, SIAM
Monographs on Discrete Mathematics and Applications, Society for Industrial
and Applied Mathematics, Philadelphia, 1999.
\bibitem{mm:surubg:83}
F.~R. McMorris and G.~T. Myers, {\em Some uniqueness results for upper bound
graphs}, Discrete Math. {\bf 44} (1983), 321--323.
\bibitem{mz:bgpos:82}
F.~R. McMorris and T.~Zaslavsky, {\em Bound graphs of a partially ordered set},
J. Combin. Inform. System Sci. {\bf 7} (1982), 134--138.
\bibitem{m:srg:67}
A.~Mukhopadhyay, {\em The square root of a graph}, J. Combin. Theory {\bf 2}
(1967), 290--295.
\bibitem{t:sriico:96}
P.~J. Tanenbaum, {\em Simultaneous representation of interval and
interval-containment orders}, Order {\bf 13} (1996), 339--350.
\bibitem{t:sirpg:99}
\bysame, {\em Simultaneous intersection representation of pairs of graphs}, J.
Graph Theory {\bf 32} (1999), 171--190.
\bibitem{tw:sdrmp:96}
P.~J. Tanenbaum and S.~Whitesides, {\em Simultaneous dominance representation
of multiple posets}, Order {\bf 13} (1996), 351--364.
\bibitem{t:cposdt:92}
W.~T. Trotter, {\em Combinatorics and partially ordered sets: Dimension
theory}, Johns Hopkins Series in Mathematical Sciences, Johns Hopkins Univ.
Press, Baltimore, 1992.
\bibitem{w:igt:96}
D.~B. West, {\em Introduction to graph theory}, Prentice Hall, Upper Saddle
River, NJ, 1996.
\end{thebibliography}
\end{document}