\documentclass[11pt]{article}

\usepackage{amsmath,amssymb}

\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9.0in}
\setlength{\oddsidemargin}{0.in}
\setlength{\evensidemargin}{0.in}
\setlength{\textwidth}{6.5in}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{example}[theorem]{Example}
\newtheorem{problem}{Problem}[section]

%\newcommand {\square} 
%  {{\vcenter {\hrule height .2mm 
%   \hbox{\vrule width .2mm height 2mm \kern 2mm
%   \vrule width .2mm} \hrule height .2mm}}}
\newcommand{\eps}{\varepsilon}
%\newcommand{\qed}{\hfill\rule[-1pt]{5pt}{9pt}}
\newcommand{\qed}{\hfill $\square$}
\newenvironment{proof}{\noindent{\bf Proof.}\hspace*{1em}}{\qed\medskip}
\newcommand{\eproof}{\qed\medskip}

\newcommand{\A}{{\mathcal A}}
\newcommand{\B}{{\mathcal B}}
\newcommand{\LL}{{\mathcal L}}
\newcommand{\mug}{\mu^{\rm g}}
\newcommand{\Vol}{{\rm Vol}}
\newcommand{\Rnp}{{\mathbb R}_+^n}
\newcommand{\supp}{{\rm supp}}
\newcommand{\sm}{\setminus}
\newcommand{\Stab}{{\rm Stab}}
\newcommand{\FStab}{{\rm FStab}}
\newcommand{\bx}{{\bf x}}
\newcommand{\by}{{\bf y}}
\newcommand{\bz}{{\bf z}}
\newcommand{\bw}{{\bf w}}
\newcommand{\bv}{{\bf v}}
\newcommand{\be}{{\bf e}}
\newcommand{\ol}{\overline}
\newcommand{\bbR}{{\mathbb R}}
\newcommand{\conv}{{\rm conv}}

\title{\bf Convex Bodies, Graphs and Partial Orders}

\author{                B\'ela Bollob\'as\thanks{
                          Author's email address: 
			  bollobas@msci.memphis.edu} \\
                        Department of Mathematical Sciences \\
                        University of Memphis \\
                        Memphis TN 38152-6429, U.S.A. \\
                        and \\
                        Trinity College \\
                        Cambridge CB2 1TQ \\
                        U.K.
\and    
                        Graham R.\ Brightwell \thanks{
                          Author's email address: 
			  g.r.brightwell@lse.ac.uk.  Part of this work was
 			  carried out while this author was at the 
			  University of Memphis.} \\
                        Department of Mathematics \\
                        London School of Economics \\
                        Houghton St. \\
                        London WC2A 2AE \\
                        U.K.
}       


\date{}

\begin{document}
\maketitle

%\vfill

\begin{abstract}
A {\em convex corner} is a compact convex down-set of full dimension
in $\Rnp$.  Convex corners arise in graph theory, for instance as
stable set polytopes of graphs.  They are also natural objects of
study in geometry, as they correspond to 1-unconditional norms in an
obvious way.  In this paper, we study a parameter of convex corners,
which we call the {\em content}, that is related to the volume.  This
parameter has appeared before, either implicitly or in special cases,
both in geometry and in combinatorics, and a major aim of the paper is
to expose connections between work in these two areas.

We define the {\em content} $\mu(S)$ of a convex corner $S$ in $\Rnp$
recursively by
$$
\mu (S) = \max _{\bx\in S} \sum _{i=1}^n x_i \mu(S_i),
$$
where $S_i$ is the projection of $S$ on to the $i^{\rm th}$ co-ordinate
plane, and $\mu(\{0\}) = 1$ for the zero-dimensional convex corner 
$\{ 0\}$.

As part of his proof of Saint-Raymond's Inequality --
$\Vol(S)\Vol(S^\circ) \ge 1/n!$ -- Meyer~\cite{Mey} effectively showed
that $\mu(S) \le n! \Vol(S)$ for any convex corner $S$.
Sidorenko~\cite{Sid} showed that, if $S$ is the stable set polytope of
the comparability graph of a partial order $P$, then $\mu(S)$ is the
number of linear extensions of $P$ and thus, via a result of
Stanley~\cite{Sta}, the content $\mu(S)$ is equal to $n! \Vol(S)$.  We
show that, if $S$ is a 0-1 polytope, then $\mu(S) = n! \Vol(S)$ if and
only if $S$ is the stable set polytope of a strongly perfect graph.

The other ingredient in Meyer's proof is that 
$\mu(S)\mu(S^\circ) \ge n!$ for any convex corner $S$ and its polar
$S^\circ$.  We extend this result by working with the 
{\em pointwise product} of convex corners.  The pointwise product of
two sets $A$ and $B$ is 
$A\circ B = \{ \bx \circ \by : \bx \in A, \by \in B \}$, where
$(\bx \circ \by)_i = x_iy_i$.  We show that, if $A$, $B$ and $C$ are
convex corners such that the pointwise product $A\circ B$ is contained
in $C$, then we have $\mu(A) \le \mu(B^\circ) \mu(C)$.  This leads to
the following generalization of Saint-Raymond's Inequality: if 
$A_1, \dots ,A_r$ are any bounded sets in $\Rnp$, such that 
$A_1 \circ \dots \circ A_r$ is contained in the $\ell_1$ unit ball,
then $\mu(A_1^\circ) \dots \mu(A_r^\circ) \ge n!$ and so
$\Vol(A_1^\circ) \dots \Vol(A_r^\circ) \ge (n!)^{-r+1}$.

We prove various other results concerning content and volume of convex
corners, and give counterexamples to two conjectures of Bollob\'as and
Leader~\cite{BoLe} about pointwise products.  We conclude with a
number of open problems.  
\end{abstract}

\section{Introduction and Definitions} \label{Intro}

In a 1991 paper~\cite{Sid}, Sidorenko introduces the function
$\mug(G)$, defined for a graph $G$ recursively by setting 
$\mug(G) = 1$ if $G$ has one node, and
$$
\mug(G) = \max _{I\in {\cal I}} \sum _{v\in I} \mug (G-v),
$$
where $\cal I$ denotes the set of independent sets in $G$.  (To be
more accurate, our $\mug(G)$ is Sidorenko's $\mu(\ol{G})$.)  We
shall call $\mug(G)$ the {\em graph-content} of $G$.  Sidorenko proves
that, in the case where $G$ is the comparability graph of a partial
order $P$, $\mug(G)$ is equal to the number of linear extensions of
$P$.

A very similar concept had been used in 1986 by Meyer~\cite{Mey} in a
completely different context, namely to provide a simple proof of
Saint-Raymond's Inequality, which can be stated as follows.

\begin{theorem} \label{1.1}
If $T$ is the unit ball of a 1-unconditional norm in $\bbR^n$,
$T^*$ is the unit ball of the dual norm, $S=T\cap \Rnp$ and 
$S^\circ = T^*\cap \Rnp$, then $\Vol(S)\Vol(S^\circ) \ge 1/n!$.
\end{theorem}

The first proof of Theorem~\ref{1.1} was given by
Saint-Raymond~\cite{StR} in 1980.  Besides Meyer's proof, other short
proofs were found by Reisner~\cite{Rei} and by Bollob\'as, Leader and
Radcliffe~\cite{BLR}.

Meyer's approach amounts to considering a parameter $\mu(S)$, which we
call the {\em content} of $S$, with a recursive definition very
similar to that of $\mug$ above, showing that $\mu(S) \le n!\Vol(S)$,
$\mu(S^\circ) \le n!\Vol(S^\circ)$, and $\mu(S)\mu(S^\circ) \ge n!$.
Theorem~\ref{1.1} evidently follows from these three inequalities.
Meyer does not define the content explicitly, and the three inequalities
here are woven together in his proof.

It turns out that Sidorenko's parameter $\mug(G)$ is equal to the
content of the {\em stable set polytope} of the graph $G$, so
Meyer's and Sidorenko's work reflect different aspects of the same theory.  
Another concept that turns out to be related is the
{\em pointwise product} of bodies in $\Rnp$,
studied by Bollob\'as and Leader~\cite{BoLe0},~\cite{BoLe}.  

Our purpose in this paper is to initiate study of the content for its 
own sake.  We clarify the relationships among results of Meyer, 
Sidorenko and others, and, building on their work, we give a number of
results (none of which is especially difficult to prove within its
context), directed at bringing out the strong
connections between the theories of volume products, perfect
graphs, and partial orders.  Our aim is to emphasize the interplay
between these areas, and to answer the questions that seem to us to arise 
naturally.

Before going into more detail, we need a number of definitions.  We
then state the main results of the paper, along with further
discussion. 

\subsection{Definitions} \label{Definitions}

In this paper, we study concepts from several different areas of
mathematics, and so there are a large number of basic terms, and a few
results, that we feel obliged to introduce in detail.  However, most
of the definitions below are fairly standard, the principal exceptions
being those of content and of pointwise product.

\medskip

A {\em convex corner} in $\Rnp$ is a compact
convex subset $S$ of $\Rnp$, with non-empty interior, which is a
down-set, i.e., if $x_i \le y_i$ for $i=1, \dots, n$, and 
$\by\in S$, then $\bx\in S$.

A norm $\| . \|$ on $\bbR^n$ is {\em 1-unconditional} (with 
respect to the standard basis of $\bbR^n$) if it has the property 
that
$$
\| (x_1, \dots ,x_n)\| = \| (|x_1|, \dots ,|x_n|)\|
$$
 for every vector $\bx = (x_1, \dots ,x_n)$.  The unit ball of a
1-unconditional norm is called a {\em 1-unconditional body}.  It is
easy to see that the intersection of a 1-unconditional body in
$\bbR^n$ with the closed positive quadrant is a convex corner.
Conversely, if $S$ is a convex corner, then 
$\{ (x_1, \dots ,x_n) \in \bbR^n : (|x_1|, \dots ,|x_n|) \in S\}$ is a
1-unconditional body.  Thus convex corners correspond naturally to
1-unconditional norms.  We work with convex corners throughout, but of
course many of our results can be restated in terms of 1-unconditional
bodies or norms.  For more information about the geometry of
finite-dimensional normed spaces, a good reference is the book by
Lindenstrauss and Tzafriri~\cite{LiTz}.  The term ``convex corner'' was
used by Csisz\'ar, K\"orner, Lov\'asz, Marton and
Simonyi~\cite{CKLMS}.

For $S$ a subset of $\Rnp$, we define the {\em polar} $S^\circ$ of $S$ to be
$$
\{ \by \in \Rnp : \bx \cdot \by \le 1 \hbox{ for
all } \bx \in S \}.
$$
It is easy to see that, if $S$ is bounded, and not contained in any
face $\{ \bx : x_i = 0\}$, then $S^\circ$ is a convex corner.
Furthermore, if $S$ is the convex corner associated with a
1-unconditional norm, then $S^\circ$ is the convex corner associated
with the dual norm.  It is clear that, if $S$ is a convex corner, then
$(S^{\circ})^\circ = S$.  In the literature of combinatorial
optimization (when $S$ will normally be a polytope), $S^\circ$ is
often called the {\em antiblocker} or {\em blocking polytope}, and is
typically denoted $S^*$.  See for instance the book of Gr\"otschel,
Lov\'asz and Schrijver~\cite{GLS}. 

A point $\bx$ in a convex corner $S$ is {\em maximal} if, whenever
$\by \in S$, with $x_i \le y_i$ for every $i$, we have 
$\by = \bx$.

The {\it support} $\supp(\bz)$ of a vector 
$\bz\in \bbR^n$ is the set of co-ordinates $j$ such that
$z_j\not=0$.  For $S$ a convex corner in $\Rnp$, and 
$i\in [n]\equiv \{ 1,\dots ,n\}$, we define $S_i$ to be the set of
points in $S$ whose support does not include $i$. So $S_i$ is an
$(n-1)$-dimensional convex corner in the $i^{\rm th}$ co-ordinate
plane.  More generally, if $A\subseteq [n]$, then we define $S_A$ to
be the set of points in $S$ whose support is contained in $A$; $S_A$
is a convex corner in the lower-dimensional space defined by $A$. We
shall use subscripts in this way throughout: a subscript $i$ will
indicate reduction by ignoring the $i^{\rm th}$ co-ordinate, a
subscript $A$ will indicate restriction to the subspace defined by the
co-ordinates in set $A$.

An exception to this rule is that we use $\be_i$ to denote the 
$i^{\rm th}$ standard basis vector in $\bbR^n$.  For every subset $A$
of $[n]$, we denote by $\be_A$ the indicator vector of the set $A$.

\medskip

We are now ready to define the {\em content} $\mu(S)$ of a convex
corner $S$, recursively.  First we define the content of $\{0\}$ (the
unique zero-dimensional convex corner) to be 1. Now, for $n\ge 1$, and
$S$ a convex corner in $\Rnp$, we set 
$$
\mu(S) = \max _{\bx \in S} \sum _{i=1}^n x_i \mu (S_i).
$$

We give some examples, starting with the convex
corners $B_p^n$ obtained by intersecting the unit balls of the various
spaces $\ell_p^n$ with the positive quadrant:
$$
B_p^n = \{ \bx \in \Rnp : x_1^p + \dots + x_n^p \le 1 \},
$$
for $1\le p<\infty$.  Similarly, $B_\infty^n = [0,1]^n$, the intersection
of the $\ell_\infty^n$ unit ball with the positive quadrant.  We also
define $B_p^n$ as above for $0<p<1$, but this is not a convex set.  For
$1\le p \le \infty$, the polar of $B_p^n$ is $B_q^n$, where
$\frac{1}{p} + \frac{1}{q} = 1$.  

For $S=B_p^n$, $1\le p\le \infty$, the maximization in the definition
of the content $\mu(S)$ occurs at the point on the boundary of $S$
where all co-ordinates are equal -- indeed this is true whenever the
symmetry group of $S$ is transitive on the co-ordinate axes -- namely
$x_i = n^{-1/p}$ for all $i$, and $S_i$ is isomorphic to $B_p^{n-1}$
for all $i$, so $\mu(S) = n^{1-1/p} \mu(S_i)$ and thus, by induction, 
$\mu(B_p^n) = (n!)^{1-1/p}$.  For comparison, the volume of $B^n_p$,
for $1\le p < \infty$, is given by
$$
\Vol(B^n_p) = \left( \frac{\Gamma(1/p)} {p}\right) ^n 
\frac{1}{\Gamma (1+n/p)}.
$$

Another important special case is where the convex corner $S$ is a
polytope, in which case the definition of $\mu$ involves maximizing a
linear function over a convex polytope, so the maximum is attained at
a vertex.  If, in addition, all vertices of $S$ are 0-1 vectors, we
call $S$ a {\em 0-1 convex corner}; in this case the set of vertices
of $S$ corresponds to a collection ${\cal J}$ of subsets of $[n]$, and
we have 
$$ 
\mu(S) = \max _{J \in {\cal J}} \sum _{j\in J} \mu (S_j).
$$

For instance, consider the 0-1 convex corner
$$
T^n_t = \{ \bx \in [0,1]^n : \sum x_i \le t \},
$$
for $n,t\in {\mathbb N}$.  For $n\le t$, $T^n_t = B_\infty^n$, so 
$\mu(T^n_t) = n!$.  For $n\ge t$, the maximization in the definition
of $\mu(T^n_t)$ is achieved at a vertex, and all vertices $\bx$ have
$t$ co-ordinates equal to~1 and the rest~0, so
$\mu(T^n_t) = t \mu((T^n_t)_1) = t \mu(T^{n-1}_t)$, so 
$\mu(T^n_t) = t! t^{n-t}$.

%The vertices of $(T_t^n)^\circ$ are those vectors with some number
%$m>t$ of the co-ordinates equal to $1/t$, and the rest~0, together
%with the co-ordinate vectors $\be_i$.  For $n\le t$, 
%$(T_t^n)^\circ = B_1^n$, so $\mu((T_t^n)^\circ) =1$, while for $n>t$
%the maximization occurs at the vertex with all co-ordinates equal to
%$1/t$, and we have 
%$\mu((T_t^n)^\circ) = \frac{n}{t} \mu((T_t^{n-1})^\circ)$ and so
%$\mu((T_t^n)^\circ) = \frac{n!}{t!} t^{-(n-t)}$.  

\medskip

Let $G$ be a graph with node set $[n]$ (we use the term {\em node}
rather than the more widely accepted {\em vertex} to avoid confusion
with the vertices of polytopes).  The {\em stable set polytope}
$\Stab(G)$ of $G$ is the 0-1 convex corner whose vertices correspond
to the stable sets (independent sets) of $G$:
$$
{\Stab}(G) = \conv \{ \be_I : I \in {\cal I}(G)\}.
$$ 
where ${\cal I}(G)$ is the family of stable sets of $G$.  
Observe that $\mu(\Stab(G))$ is exactly $\mug(G)$, as defined 
in~\S\ref{Intro}.  

The polar of a stable set polytope is a well-studied concept in the
context of combinatorial optimization. Clearly we have, for $G$ an
$n$-node graph, that
$$
(\Stab (G))^\circ = \{ \bx \in \Rnp : \sum _{i\in I} x_i \le 1
\mbox{ for all } I \in {\cal I}(G) \},
$$
and indeed we may restrict attention to the {\em maximal} independent
sets in the above description.  In particular, if $C$ is a clique in a
graph $G$, then the vector $\be_C$ is in $(\Stab(G))^\circ$. In
other words, all vertices of the stable set polytope of the complement
$\ol G$ are in $(\Stab(G))^\circ$.  Thus we have that
$$
\Stab(\ol G) \subseteq (\Stab(G))^\circ.
$$
We do not always have equality above: the easiest example is when 
$G = \ol G = C_5$, the cycle on 5 nodes, when the vector
$(\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2})$ is in
$(\Stab(C_5))^\circ$ but not in $\Stab(C_5)$.  

A graph $G$ is {\em perfect} if, for every induced subgraph $H$ of
$G$, the chromatic number of $H$ is equal to the size of its largest
clique.  Lov\'asz~\cite{Lov} proved the {\em Perfect Graph Theorem}, 
stating that, if a graph is perfect, then so is its complement; as
part of that proof, he obtained the following alternative
characterization of perfect graphs.   

\begin{theorem} \label{4.2}
$\Stab(\ol G) = (\Stab(G))^\circ$ if and only if
$G$ is perfect. 
\end{theorem}

The polytope $\Stab(\ol G)^\circ$ is called the 
{\em fractional stable set polytope} of $G$, and is sometimes denoted
$\FStab(G)$.  An equivalent formulation of Theorem~\ref{4.2} is
to say that $\Stab(G) = \FStab(G)$ if and only if $G$ is perfect.
See Gr\"otschel, Lov\'asz and Schrijver~\cite{GLS} or Toft~\cite{Toft}
for further information on perfect graphs and related topics.

A {\em strongly perfect graph} is a graph $G$ with the property that,
for every induced subgraph $H$ of $G$, there is an independent set in
$H$ meeting every maximal clique of $H$. (Note that a graph is perfect
if and only if, for every induced subgraph $H$, there is an
independent set meeting every {\em maximum size} clique, so a strongly
perfect graph is certainly perfect.)  Strongly perfect graphs were
introduced by Berge and Duchet~\cite{BeDu} in 1984, and further
investigated in papers of Chv\'atal~\cite{Chv}, Ho\`ang, Maffray and
Preissman~\cite{HMP}, and Ho\`ang~\cite{Hoa}.  Attention has
principally focussed on relations between the class of strongly
perfect graphs and other classes of perfect graphs.

\medskip

For a partial order $P=(X,<)$, the {\em comparability graph} $C(P)$ of
$P$ is the graph on $X$ obtained by setting $x$ and $y$ adjacent if
they are comparable in $P$, i.e., if either $x<y$ or $y<x$.  The
complement of $C(P)$ is the {\em incomparability graph} $I(P)$ of $P$.
An independent set in $C(P)$ is a set of mutually incomparable
elements of $P$ -- an {\em antichain}.  Comparability graphs of
partial orders are strongly perfect, since the set $M(Q)$ of maximal
elements of any induced subposet $Q \subseteq P$ is an independent set
meeting all maximal chains in $Q$ (i.e., all maximal cliques in
$C(Q)$.  That incomparability graphs are perfect follows either from
the Perfect Graph Theorem or from Dilworth's Theorem.

There are many graphs that are strongly perfect but are not
comparability graphs; the simplest are the 6-node graph $H$ obtained
by attaching a pendant node to each node of a triangle, and the
complement of $H$.  The interesting problem of determining the class
of minimal non-strongly perfect graphs seems to be open. This class
certainly includes:
\begin{itemize}
\item odd cycles $C_{2n+1}$ of length at least 5, 
\item the complements $\ol{C_n}$ of cycles of length $n\ge 5$, 
\item graphs obtained from a triangular prism ($\ol{C_6}$) 
by replacing each of the three edges not in triangles by odd-length paths.
\end{itemize}

The {\em intersection} $P\cap Q$ of partial orders $P=(X,<_P)$ and
$Q=(X,<_Q)$ on the same set $X$ is defined by setting $x<y$ in 
$P\cap Q$ if both $x<_P y$ and $x<_Q y$. 
A {\em linear extension} of a partial order $P=(X,<)$ is a linear
(total) order $\prec$ on $X$ consistent with $<$, i.e., such that
$x\prec y$ whenever $x<y$.  The number of linear extensions of $P$ is
denoted $e(P)$.

\medskip

We next introduce an operation on convex corners, or more generally on
subsets of $\bbR^n$, which has attracted some interest, and for which
content seems to be a useful tool.  For vectors $\bx$ and $\by$ in
$\bbR^n$, define the {\em pointwise product} of $\bx$ and $\by$ to be
the vector $\bx \circ \by$ with $(\bx \circ \by)_i = x_iy_i$.  The
pointwise product of three or more vectors is defined in a similar
way, e.g., $\bx \circ \by \circ \bz = (\bx \circ \by) \circ \bz$, with
the $i^{\rm th}$ co-ordinate being simply $x_iy_iz_i$. It is immediate
that, for instance, 
$(\bx \circ \by) \cdot \bz = \bx \cdot (\by \circ \bz)$.

Now, for sets $S$ and $T$ in $\Rnp$, we define the pointwise product 
of $S$ and $T$ to be the set
$$
S\circ T = \{ \bx \circ \by : \bx \in S, \by \in T \}.
$$

Study of the pointwise product $S\circ T$ for its own sake was
initiated by Bollob\'as and Leader~\cite{BoLe0}; various properties of
the product are discussed in that paper and in its more extended
version~\cite{BoLe}. The pointwise product also
appears in the paper by Csisz\'ar, K\"orner, Lov\'asz, Marton and
Simonyi~\cite{CKLMS}, who use the notation $S\circ T$, and doubtless
explicitly or implicitly in many other works.

Note that, even if $S$ and $T$ are 0-1 convex corners, $S\circ T$ 
need not be convex; for instance, if $S = T = B_1^n$, then 
$$
S\circ T = B_{1/2}^n \equiv 
\{ \bx \in \Rnp : \sum_{i=1}^n x_i^{1/2} \le 1\},
$$ 
a non-convex set.  

For $S$ a convex corner and $r\in {\mathbb N}$, let $S^{1/r}$ be the
set of vectors $(x_1, \dots, x_n)$ such that 
$(x_1^r, \dots, x_n^r) \in S$.  For instance 
$(B_p^n)^{1/r} = B_{rp}^n$.  It is easy to verify that, for any convex
corner $S$, the pointwise product of $r$ copies of $S^{1/r}$ is $S$.

\medskip

 From convex corners $S\subseteq (\Rnp)_A$ and $T\subseteq (\Rnp)_B$, 
where $A$ and $B$ are disjoint sets whose union is $[n]$, 
we can form a convex corner in $\Rnp$ in several ways.  The 
{\em $\ell_\infty$-sum} of $S$ and $T$ is just the cartesian product of
$S$ and $T$, while the {\em $\ell_1$-sum} is the convex hull
$\conv(S\cup T)$.  

For a convex corner $S$ in $\Rnp$, let
$$
V(S)= \max _{\bx \in S} \prod _{i=1}^n x_i.
$$

Thus $V(S)$ is the volume of the largest $n$-dimensional cuboid
contained in $S$.  The {\em entropy} of a convex corner (with respect
to the uniform distribution) is defined as $-\log _2 V(S)$. See, for
instance, Csisz\'ar, K\"orner, Lov\'asz, Marton and
Simonyi~\cite{CKLMS}.  As part of their work on entropy of stable set
polytopes of comparability graphs, Kahn and Kim~\cite{KaKi} proved the
following result, showing that $V(S)$ approximates $\Vol (S)$ to
within an exponential factor -- to be more precise, within a factor of
$e^n$.

\begin{theorem} \label{KaKi}
For any convex corner $S$,  
$\displaystyle{\Vol(S) \le \frac{n^n}{n!} V(S)}$.
\end{theorem} 

The example of the unit simplex $B_1^n$ shows that Theorem~\ref{KaKi}
is best possible.

\subsection{Main Results} \label{MainResults}

Here, we present the main results concerning content, both from this
paper and from other sources.  As we explained earlier, the following
two results, giving perhaps the most important properties of the
content, are essentially due to Meyer~\cite{Mey}.

\begin{theorem} \label{2.2}
For any convex corner $S$ in $\Rnp$, 
$\mu(S) \le n! \Vol (S)$. 
\end{theorem} 

\begin{theorem} \label{2.7} 
For any convex corner $S$ in $\Rnp$,
$\mu(S) \mu(S^\circ) \ge n!$.
\end{theorem} 
 
In \S\ref{skew}, we give the (quite simple) proof of
Theorem~\ref{2.2}, and extend it by defining a class of (not
necessarily convex) polyhedra called {\em skew-cubes}, and showing
that $\mu(S)/n!$ is equal to the volume of the largest skew-cube
contained in $S$.  We also show that $\mu(S) = n!\Vol(S)$ if and only
if $S$ is a skew-cube.  In \S\ref{char-skew} we give various
characterizations of skew-cubes, and in \S\ref{lbc} we briefly discuss
how far from equality we can get.

In \S\ref{sec:Polar}, we investigate Theorem~\ref{2.7} in a similar
way: we give a proof, discuss cases of equality, and investigate how
far from equality we can get. 

The next two inequalities follow immediately on combining
Theorems~\ref{2.2} and~\ref{2.7}.

\begin{corollary} \label{2.9}
For any convex corner $S$ in $\Rnp$,
$\mu(S) \ge 1 / \Vol (S^\circ)$. 
\qed
\end{corollary}

We shall show (Theorem~\ref{6.11}) that we only have equality in
Corollary~\ref{2.9} for a very small class of convex corners; if
$\mu(S) \Vol (S^\circ) = 1$ then, after scaling so that all the unit
vectors $\be_i$ are on the boundary, $S$ is a 0-1 polytope.  We
describe in \S\ref{problems} a class of 0-1 polytopes for which we do
have equality in Corollary~\ref{2.9}, and conjecture that this is the
entire class of extremal examples.

\begin{corollary} \label{2.20} 
For any convex corner $S$ in $\Rnp$,
$\Vol (S) \Vol (S^\circ) \ge 1/n!$. 
\qed
\end{corollary}

Of course, this is just a restatement of Saint-Raymond's Inequality,
Theorem~\ref{1.1}, for which the cases of equality were determined by
Meyer~\cite{Mey} and Reisner~\cite{Rei}.  Throughout the paper, we
prove various strengthenings of Corollary~\ref{2.20}, such as this
result from \S\ref{sec:Polar}.

\begin{theorem} \label{2.21}
For any convex corner $S$ in $\Rnp$, there are convex polytopes 
$R\subseteq S$ and $R'\subseteq S^\circ$, each with at most $2^n$
vertices, such that $\Vol(R) \Vol(R') \ge 1/n!$.
\end{theorem} 

In the case where $S$ is the stable set polytope $\Stab(G)$ of a graph
$G$ with node set $[n]$, so that $\mu(S) = \mug(G)$, Theorem~\ref{2.2}
translates to the following.

\begin{theorem} \label{4.1} 
For any graph $G$, $\mug(G) \le n! \Vol(\Stab(G))$. 
\qed
\end{theorem}

In \S\ref{0-1}, we shall prove the following result, which includes a 
characterization of the extremal graphs in Theorem~\ref{4.1}.

\begin{theorem} \label{5.3}
A 0-1 convex corner $S$ satisfies $\mu(S) = n! \Vol(S)$ if and only if
it is the stable set polytope of a strongly perfect graph.
\end{theorem}

Theorem~\ref{2.7} can also be interpreted in the case when
$S=\Stab(G)$, especially when $G$ is perfect, so that 
$S^\circ = \Stab(\ol{G})$.  These themes are explored in
\S\ref{graphs}.

As we have seen, the comparability graph $C(P)$ of any partial order
$P$ is strongly perfect, so $\mug(C(P)) = n! \Vol(C(P))$.  In fact, as
we now discuss, both sides of this identity have earlier been shown to
be equal to $e(P)$, the number of linear extensions of $P$.  One part
of this is a 1986 result of Stanley~\cite{Sta}.

\begin{theorem} \label{4.9}
For any partial order $P$,
$e(P) = n! \Vol(\Stab(C(P)))$.
\end{theorem}
 
To see the direct connection between $e(P)$ and $\mug(C(P))$, observe
that the set $M(P)$ of maximal elements of a partial order $P$ is an
independent set in $C(P)$, and that we can partition the set of linear
extensions of $P$ according to which element of $M(P)$ is top.
Moreover, the number of linear extensions with a given maximal element
$m$ top is equal to $e(P-m)$, and so we have
$$ 
e(P) = \sum _{m\in M(P)} e(P-m).  
$$ 
Comparing with the definition of $\mug$ gives that
$e(P) \le \mug(C(P))$, for every partial order $P$.
To obtain the reverse inequality, Sidorenko~\cite{Sid} proved the next
result. 

\begin{theorem} \label{4.7}
For any partial order $P$, and any antichain $A$ in $P$, 
$e(P) \ge \sum _{x\in A} e(P-x)$.
\end{theorem} 

As noted by Sidorenko, Theorem~\ref{4.7} implies that
$$
e(P) = \max _A \sum _{x\in A} e(P-x),
$$
where the maximum is over all antichains $A$ of $P$.  Since the
one-element partial order has just one linear extension, we have
the next result, again due to Sidorenko.

\begin{theorem} \label{4.8} 
For any partial order $P$, 
$e(P) = \mug(C(P))$.
\end{theorem}

Given our results, Sidorenko's Theorem~\ref{4.8} and Stanley's
Theorem~\ref{4.9} are equivalent.  However, their proofs are quite
different.  Sidorenko proves Theorem~\ref{4.7} using a very elegant
argument about a certain flow through the elements of a partial
order.  Stanley proves Theorem~\ref{4.9} by giving a measure-preserving
bijection between $\Stab(C(P))$ and the {\em order polytope} of
$P$.  

We prove almost no new results about partially ordered sets in this
paper.  However it was consideration of the results of Stanley and
Sidorenko that led us to work on content, and the applications to
partial orders remain a major source of motivation.  Moreover, as we
shall see, Stanley's theorem is useful to us in that it provides a
relatively practical method for finding or approximating the volumes
of bodies that happen to be stable set polytopes of comparability
graphs: counting linear extensions is \#P-complete in general (this was
proved by Brightwell and Winkler~\cite{BrWi}), but in practice it is
usually much easier than calculating volumes directly.

\medskip

In \S\ref{ppcc}, we are concerned with the pointwise product of convex
corners.  In \S\ref{fgS-R}, we prove the following inequality.

\begin{theorem} \label{6.3}
Let $A$, $B$ and $C$ be convex corners in $\Rnp$.
If $A\circ B \subseteq C$, then $\mu(A) \le \mu(B^\circ) \mu(C)$.
\end{theorem}

Note that this is a generalization of Theorem~\ref{2.7}, which is the
special case with $A=B_\infty^n$ and $B=C$.  Thus, in view of
Theorem~\ref{2.2}, it can be seen as a more general version of
Saint-Raymond's Theorem.  Theorem~\ref{6.3} also generalizes results
of Sidorenko~\cite{Sid}, who deals with the special case where the
convex corners are stable set polytopes of graphs, and in particular
$B$ is the stable set polytope of the incomparability graph of a
partial order $P$ (so that $\mu(B^\circ)$ is the number of linear
extensions of $P$).  Although there is not much more to the proof of
Theorem~\ref{6.3} than to that of Theorem~\ref{2.7}, the extra
generality enables us to work with pointwise products of more than two
bodies.  In particular, we use Theorem~\ref{6.3} to prove the
following result, which is an extension of Saint-Raymond's Theorem to
pointwise products of several bodies, and might well be considered as
the most attractive result in this paper.

\begin{theorem} \label{6.20}
If $A_1, \dots, A_r$ are convex corners in $\Rnp$ such that
$A_1 \circ \dots \circ A_r \subseteq B_1^n$, then
$$
\Vol(A_1^\circ) \dots \Vol(A_r^\circ) \ge \frac{1}{n!^{r-1}}.
$$
\end{theorem} 

We also determine the class of $r$-tuples of convex corners 
$(A_1, \dots, A_r)$ for which equality holds in Theorem~\ref{6.20},
generalizing the results of Meyer~\cite{Mey} and Reisner~\cite{Rei}
for the case $r=2$.  

A major motivation for Bollob\'as and Leader~\cite{BoLe} in their
investigation of the pointwise product was the idea of generalizing  
the notion of the polar: to say that $A\circ B \subseteq B_1^n$ is
equivalent to saying that $A\subseteq B^\circ$, so one might hope to
replace theorems about a body and its polar by theorems with the
condition that $A\circ B$ is contained in some other body $C$. 
For instance, they prove the following pair of inequalities. 

\begin{theorem} \label{BoLe}
{\rm (a)} \quad If $A$ and $B$ are down-sets in $\Rnp$, then
$$
\Vol(A) \Vol(B) \ge \Vol(A\circ B).
$$
\noindent {\rm (b)} \quad If $A$, $B$ and $C$ are convex corners in $\Rnp$ with
$A\circ B \subseteq C$, then 
$$
\Vol(A) \Vol(B) \le (\Vol(C^{1/2}))^2.
$$
\end{theorem}

Theorem~\ref{BoLe}(b) extends Santal\'o's Theorem~\cite{San}
for unconditional bodies, which states that, for a convex corner $S$
in $\Rnp$, $\Vol (S) \Vol (S^\circ) \le (\Vol (B_2^n))^2$.  (The full
version of Santal\'o's Theorem is that 
$\Vol(T)\Vol(T^*) \le (\Vol(C_2^n))^2$, whenever $T$ and $T^*$ are the
unit balls of dual norms on $\bbR^n$, and $C_2^n$ is the $\ell_2$ unit
ball.  For a short proof, see Meyer and Pajor~\cite{MePa}.)

Theorem~\ref{BoLe}(a) is another
generalization of Saint-Raymond's Inequality, since if $B=A^\circ$,
then $A\circ B = B_1^n$, of volume $1/n!$.  One possible drawback of
this result is that $A\circ B$ is not in general convex, and its
volume may not really be the object of interest.  

In~\cite{BoLe}, Bollob\'as and Leader conjecture (Conjecture~7
of~\cite{BoLe}) that, if $A$, $B$ and $C$ are convex corners such that
$A\circ B \subseteq C$, with $A$ and $B$ maximal and $C$ minimal
subject to this condition, then $A\circ B = C$.  They prove that this
holds, even without the assumption of minimality of $C$, for a large
family of bodies $C$, including all the $B_p^n$ ($1\le p\le\infty$) --
this generalizes Lozanovskii's Theorem~\cite{Loz}, which is the result
for $C=B_1^n$ -- and also in the case where $A$ satisfies a
``smoothness'' condition and $C$ is ``strictly unconditional''.  An
equivalent version of the conjecture is that, if $S$, $T$ and $U$ are
convex corners that are maximal subject to the condition that 
$S\circ T \circ U \subseteq B_1^n$, then $S\circ T \circ U = B_1^n$ --
to see the equivalence, take $S=A$, $T=B$ and $U=C^\circ$, and use
Lozanovskii's Theorem.

Bollob\'as and Leader also conjecture (Conjecture~17 of~\cite{BoLe})
that, under the same conditions, $\Vol (A) \Vol(B) \ge \Vol(C)$
(compare with Theorem~\ref{BoLe}(a)).  By Saint-Raymond's
Inequality, this would imply that, if $S$, $T$ and $U$ are maximal
convex corners subject to $S\circ T \circ U \subseteq B_1^n$, then
$\Vol(S) \Vol(T) \Vol(U) \ge 1/n!$.

In \S\ref{ppssp}, we prove the following result, providing a
counterexample to all these conjectures, showing in particular that
some smoothness condition is vital for Conjecture~7 of~\cite{BoLe},
even for $n=3$.  

\begin{theorem} \label{counterexample} 
There are convex corners $S_1$, $S_2$ and $S_3$ in ${\mathbb R}_+^3$
with the following properties. 
\begin{itemize} 
\item $S_1 \circ S_2 \circ S_3 \subseteq B_1^3$, and the $S_i$ are
each maximal subject to this condition.  
\item $S_1 \circ S_2 \circ S_3 \not= B_1^3$.  
\item $\Vol(S_i) = \frac{1}{2}$ for each $i$, so
that $\Vol(S_1) \Vol(S_2) \Vol(S_3) < \frac{1}{3!}$.  
\end{itemize}
Indeed, we can take, for $i=1,2,3$, $S_i = \Stab(G_i)$, where 
$G_1$, $G_2$ and $G_3$ are the graphs on $\{1,2,3\}$ with edge sets 
$\{12\}$, $\{13\}$ and $\{23\}$ respectively.  
\end{theorem}

The maximality of the $S_i$ is the most difficult part of the theorem
to verify: we deduce it from a general result (Theorem~\ref{6.9})
characterizing the $r$-tuples of graphs $(G_1,\dots,G_r)$ on $[n]$
such that each polytope $S_i=\Stab(G_i)$ is maximal subject to 
$S_1\circ \dots \circ S_r \subseteq B_1^n$.

In \S\ref{addendum}, we go on to show that Bollob\'as and Leader's
Conjecture~17 is not even approximately true: for larger values of $n$,
there are convex corners $S,T,U$, maximal subject to $S\circ T\circ U$
being contained in $B_1^n$, with $\Vol(S)\Vol(T)\Vol(U)$ around
$\frac{1}{n!}n^{-n/6}$. 

In the light of the example in Theorem~\ref{counterexample}, we regard
the condition that $A_1\circ \dots \circ A_r = B_1^n$ as the most
appropriate extension of the condition that $A_1$ and $A_2$ are polar
bodies.  In \S\ref{addendum}, we prove the inequalities in the next
result.  For $r=2$, the condition is equivalent to saying that $A_1$
and $A_2$ are polars; thus both lower bounds for $r=2$ amount to
Saint-Raymond's Inequality, while the upper bounds for $r=2$ are
exactly Santal\'o's Inequality for unconditional bodies.

\begin{theorem} \label{product-inequalities}
Suppose that $A_1, \dots, A_r$ are convex corners in $\Rnp$ such that
$A_1\circ \dots \circ A_r = B_1^n$. Then
\begin{equation}
\tag{1} \frac{1}{n!} \le \Vol(A_1) \dots \Vol(A_r) \le (\Vol(B_r^n))^r,
\end{equation}
\begin{equation}
\tag{2} \frac{1}{n!^{r-1}} \le \Vol(A_1^\circ) \dots \Vol(A_r^\circ) 
\le (\Vol(B_{r/(r-1)}^n))^r.
\end{equation}
All these inequalities are best possible.
\end{theorem}

One of the inequalities above is just Theorem~\ref{6.20}; the others
are all fairly easy consequences of results of Bollob\'as and Leader
from~\cite{BoLe}.

In \S\ref{other}, we remark on complexity issues, give an assortment 
of other inequalities, and conclude with some open problems. 

\section{Content and Volume} \label{candv}

\subsection{Skew-cubes} \label{skew}

We begin with Meyer's proof of Theorem~\ref{2.2}, recast to make
explicit the involvement of the content.  Aspects of this proof form
the basis of everything we do in this subsection.

\medskip
\noindent {\bf Proof of Theorem~\ref{2.2}.} \hspace*{1em}
We work by induction on $n$, noting that the result is trivial for
$n=0$.  For a convex corner $S$ in $\Rnp$ with $n\ge 1$, take a point 
$\bx \in S$ such that $\mu (S) = \sum_{i=1}^n x_i \mu(S_i)$.  For each
$i$, consider the cone $\conv(\bx, S_i)$ of volume 
$\frac{1}{n} x_i \Vol(S_i)$.  The interiors of these cones are
disjoint, and all the cones lie inside $S$.  Thus
$\Vol(S) \ge \frac{1}{n} \sum_{i=1}^n x_i \Vol(S_i)$.  By induction,
we have that $\Vol(S_i) \ge \mu(S_i)/(n-1)!$, and the result follows. 
\eproof

It is clear from inspection of the proof that we do not always have
equality.  What we shall now show is that $\mu(S)/n!$ is equal to the
volume of the largest set of a certain type inside $S$.  We need a 
little more notation before we can make the required definition.  All
of what follows can be understood by consideration of the proof of
Theorem~\ref{2.2} above. 

For each permutation $\sigma$ of $[n]$, and each $i=0,\dots,n$, set
$\be_{\sigma,i} = \be_{\{\sigma(1), \dots ,\sigma(i)\}}$.  Thus, for
any $\sigma$, $\be_{\sigma,0} = {\bf 0}$, and 
$\be_{\sigma,n} = {\bf 1}$.  Now, for each $\sigma$, define a simplex
$X_\sigma$ to be the convex hull of the $n+1$ vectors
$\be_{\sigma,i}$. It is easy to see that a vector $\bx\in [0,1]^n$ is
in $X_\sigma$ if and only if 
$x_{\sigma(1)} \ge x_{\sigma(2)} \ge \dots \ge x_{\sigma(n)}$.  Thus
the $n!$ simplices $X_\sigma$ make up a simplicial decomposition of
the unit cube.  Any function $f$ from the vertices $\be_A$ of
$[0,1]^n$ to $\bbR^n$ can be extended to a simplicial map $\hat f$
from the whole of $[0,1]^n$ to $\bbR^n$, by extending $f$ linearly
on each simplex $X_\sigma$.

We say that a function $f$ from $\{0,1\}^n$ to $\Rnp$ 
{\em respects the co-ordinates} if, for every subset $A$ of $[n]$,
$\supp(f(\be_A)) \subseteq A$.

We define a {\em skew-cube} to be the image $Q_f$ of $\hat f$, for some
function $f : \{0,1\}^n \to \Rnp$ respecting the co-ordinates. Note that,
if $T$ is any convex set, then $Q_f$ is contained in $T$ if and only if
the image of $f$ is. However, it is easy to construct examples of skew-cubes
that are not themselves convex.

For any co-ordinate $i \in [n]$, and any permutation $\sigma$ with
$\sigma(n) = i$, let $(X_\sigma)^i$ be the convex hull of the $n$
vectors $\be_{\sigma,0}, \dots ,\be_{\sigma,n-1}$. All of these
vectors have $i^{\rm th}$ co-ordinate equal to 0, so if $f$ respects
co-ordinates then $\hat f((X_\sigma)^i)$ is contained in the
$i^{\rm th}$ co-ordinate plane.  Now set $(Q_f)^i$ to be the union of 
all the simplices $\hat f((X_\sigma)^i)$ with $\sigma(n)=i$. Evidently
$(Q_f)^i$ is an $(n-1)$-dimensional skew-cube in the $i^{\rm th}$ 
co-ordinate plane; in fact it is exactly the skew-cube defined from
$f$ by restricting attention to the subcube of $\{0,1\}^n$ consisting
of those $\be_A$ with $i\notin A$.

Note that $(Q_f)^i \subseteq (Q_f)_i = \{ \bx \in Q_f : x_i = 0 \}$,
but we need not have $(Q_f)^i = (Q_f)_i$, since there may be some sets
$B$ with $i\in B$ but $f(\be_B)_i = 0$. However, if $f({\bf 1})_i > 0$,
then for any permutation $\sigma $ with $\sigma (n) = j \not= i$, we have
that $\hat f(X_\sigma) \cap \{ \bx : x_i = 0\} \subseteq \{ \bx : x_j =
0\}$.  In other words, provided that $f({\bf 1})_i > 0$,
the difference $(Q_f)_i \sm (Q_f)^i$ is contained in $(n-2)$-dimensional 
subspaces, and thus has $(n-1)$-dimensional volume~0. 

More generally, if $A$ is any subset of $[n]$, and $f$ is defined for
all vectors $\be_B$ with $B\subseteq A$, and respects the
co-ordinates, let $(Q_f)^A$ be the skew-cube defined by the points
$f(\be_B)$ with $B\subseteq A$; this is a skew-cube defined on the
subspace spanned by the basic unit vectors from the set $A$. Again, we
have $(Q_f)^A \subseteq (Q_f)_A$, but not necessarily equality.

\begin{lemma} \label{2.1}
Let $Q_f$ be the skew-cube associated with a function 
$f: \{0,1\}^n \to \Rnp$.  Then, up to a set of measure~0, $Q_f$ is the
disjoint union of the $n$ cones 
$$
C_i = \{ \lambda f({\bf 1}) + (1-\lambda) \bz : 0\le \lambda \le 1, 
\bz \in (Q_f)^i\}.
$$ 
Thus $\Vol(Q_f) = \frac{1}{n} \sum _{i=1}^n f({\bf 1})_i \Vol((Q_f)^i)
= \frac{1}{n} \sum _{i=1}^n f({\bf 1})_i \Vol((Q_f)_i)$.
\end{lemma}

\begin{proof}
Note that $Q_f$ is the union of simplices $\hat f (X_\sigma)$ (some of
which may have volume~0), each of which has $f({\bf 1})$ as a vertex,
and whose other vertices are those of 
$\hat f((X_\sigma)^{\sigma(n)})$, which is one of the simplices making
up $(Q_f)^i$.  Thus each point $\bx$ in $Q_f$ has a representation as
$\lambda f({\bf 1}) + (1-\lambda) \bz$, where $0\le \lambda \le 1$ and
$\bz$ is in some $(Q_f)^i$, so $Q_f$ is contained in the union of the
$C_i$.

Conversely, if $\bz$ is a vector in $(Q_f)^i$, then $\bz$ is in some
$\hat f((X_\sigma)^i)$, with $\sigma(n)=i$. Therefore any point on the
line between $\bz$ and $f({\bf 1})=f(\be_{\sigma,n})$ is in the convex
hull of $\hat f((X_\sigma)^i)$ and $f({\bf 1})$, which is just 
$\hat f(X_\sigma)$. We conclude that all the $C_i$ are contained in
$Q_f$.

To show that the $C_i$ are disjoint up to a set of measure~0,
note that, if $\bx$ is in the interior of some $C_i$, then the
representation $\bx = \lambda f({\bf 1}) + (1-\lambda) \bz$,
with $\bz \in \cup (Q_f)^i$, is unique, since $\bz$ must be the
point obtained by projecting from $f({\bf 1})$ through $\bx$ onto
$\cup (Q_f)^i$. Evidently the set of points $\bx$ in $C_i$ for which
this projection $\bz$ has a zero co-ordinate other than $z_j$ has
measure~0, as desired.

The volume of the cone $C_i$ is just 
$\frac{1}{n} f({\bf 1})_i \Vol ((Q_f)^i)$, and this is equal to
$\frac{1}{n} f({\bf 1})_i \Vol ((Q_f)_i)$, since either 
$f({\bf 1})_i = 0$, or $(Q_f)_i$ and $(Q_f)^i$ differ only on a set of
measure 0. Therefore the volume of $Q_f$ is given by either of the
stated sums.  
\end{proof}

We now give the promised extension of Theorem~\ref{2.2}.  

\begin{theorem} \label{2.2p}
For any convex corner $S$ in $\Rnp$, the content of $S$ is equal to
$n!$ times the maximum volume of a skew-cube contained in $S$.  
Moreover, $\mu(S) = n! \Vol (S)$ if and only if $S$ is a skew-cube.

If $Q_f$ is any skew-cube of maximum volume inside $S$, 
and $A$ is a subset of $[n]$, then
$$
\mu(S_A) = \frac{1}{|A|} \sum _{i\in A} f(\be_A)_i \mu((S_A)_i)
$$
(in other words, the maximizations involved in the definition of
$\mu(S)$ are achieved at the vertices $f(\be_A)$).
\end{theorem}

\begin{proof}
We claim that a skew-cube $Q_f$ of maximum volume contained in $S$ can
be obtained by the following recursive procedure to choose $f$. First,
perforce, define $f(\be_\emptyset) = {\bf 0}$. Having defined
$f(\be_B)$ for all proper subsets $B$ of $A$, choose $f(\be_A)$ to be
any point $\bx$ in $S_A$ maximizing 
$\sum _{i\in A} x_i \Vol(((Q_f)^A)^i)$.

Moreover, we claim that, for each $A$, the skew-cube $(Q_f)^A$ thus
defined has maximum volume over all ($|A|$-dimensional) skew-cubes
contained in $S_A$.  Indeed, let $A$ be a minimal subset of $[n]$ such
that this is not the case, and let $(Q_g)^A$ be a larger skew-cube in
$S_A$.  Then we have 
\begin{align}  
\Vol ((Q_g)^A) &= 
\frac{1}{|A|} \sum _{i\in A} g(\be_A)_i \Vol (((Q_g)^A)^i) \notag \\ 
&\le \frac{1}{|A|} \sum _{i\in A} g(\be_A)_i \Vol (((Q_f)^A)^i) \notag\\
&\le \frac{1}{|A|} \sum _{i\in A} f(\be_A)_i \Vol (((Q_f)^A)^i) \notag\\
&= \Vol ((Q_f)^A),\notag
\end{align}
using Lemma~\ref{2.1}, the optimality of $Q_f$ for smaller
subspaces, and the choice of $f(\be_A)$.

This proves our claims, and we have that, for any subset 
$A\subseteq [n]$, 
$$
\Vol ((Q_f)^A) = \frac{1}{|A|} \max_{\bx \in S_A} 
\sum _{i\in A} x_i \Vol (((Q_f)^A)^i).
$$ 
Therefore $|A|! \Vol ((Q_f)^A)$ obeys the same recursive law as
$\mu(S_A)$, and has the same value for $A=\emptyset$, so the two are
equal. This also shows that 
$$
\mu(S_A) = \frac{1}{|A|} \sum _{i\in A} f(\be_A)_i \mu((S_A)_i),
$$ 
as in the statement of the theorem.

Finally, if $S$ is a convex corner with $\mu(S) = n! \Vol(S)$, then
there is a skew-cube $Q_f$ inside $S$ with volume equal to $S$. If
$Q_f \not= S$, then take some point $\bx$ in $S\sm Q_f$. Since $S$ has
full dimension, there is a point $\by$ in $S$ with all co-ordinates
non-zero. Since $S$ is convex and $Q_f$ is closed, there is a point
$\bz$ of $S\sm Q_f$ on the line-segment between $\bx$ and $\by$ with
all co-ordinates at least some $\delta > 0$. Let the $\ell_\infty$
distance between $\bz$ and $Q_f$ be $\eps > 0$. Since $S$ is a
down-set in $\Rnp$, all the points of the form 
$\bz - (\eps_1, \dots, \eps_n)$, with 
$0\le \eps_i \le \min(\eps, \delta)$ for all $i$, are in 
$S\sm Q_f$.  This set of points has positive volume, contradicting the
assumption that $Q_f$ has the same volume as $S$.

This completes the proof.
\end{proof}

\subsection{Characterizations of skew-cubes} \label{char-skew}

We now address the problem of determining whether a given convex
corner is a skew-cube; we shall give two characterizations of
skew-cubes, although unfortunately neither is especially attractive.
The next theorem is a consequence of the results of the previous
subsection.  Surprisingly, however, the proof seems to require
delicate handling; the difficulty is that it is not immediately
apparent that $S_A$ is a skew-cube whenever $S$ is; this does follow
as an immediate consequence of the theorem.

\begin{theorem} \label{2.3}
Let $S$ be a convex corner in $\Rnp$. Then $S$ is a skew-cube
if and only if, for every subset $A$ of $[n]$, there is a
point $\bx_A \in S_A$ such that $S_A$ is the union of the cones
$\conv(\bx_A, (S_A)_i)$, for $i\in A$.
\end{theorem}

\begin{proof}
If the condition is satisfied, then we can define $f(\be_A) = \bx_A$
for every $A\subseteq [n]$.  Using Lemma~\ref{2.1}, it follows 
immediately by induction that $S_A = (Q_f)^A$, for every $A$.

For the converse, suppose that $S=Q_f$ is both a convex corner and a
skew-cube.  Then certainly $S$ itself is the union of cones 
$\conv(f({\bf 1}), S_i)$, i.e., the condition of the theorem is
satisfied for $A=[n]$. Furthermore, the point $\bx = f({\bf 1})$
satisfies $\mu(S) = \sum _{i=1}^n x_i \mu(S_i)$, by Theorem~\ref{2.2p}.

Suppose that the condition is not satisfied for some $A\subset [n]$;
then we have that $S_A$ is not a skew-cube. We now claim that no
$S_B$, for $A\subseteq B \subseteq [n]$, is a skew-cube. For this we
use induction on $|B|$; it is true when $|B|=|A|$.

Suppose then that $A\subset B$, with $(S_B)_i$ not a skew-cube for any
$i\in B\sm A$. We claim that $S_B$ is not a skew-cube.  If it is, then
there is some point $\bx\in S_B$ with $S_B$ equal to the union of the
cones $\conv(\bx,(S_B)_i)$, and with 
$\mu(S_B) = \sum _{i\in B} x_i \mu((S_B)_i)$, as above.

Now we note that $\mu((S_B)_j) \le (|B|-1)!\, \Vol((S_B)_j)$ for every
$j$, by Theorem~\ref{2.2p}, with equality only when $(S_B)_j$ is a
skew-cube. If $x_i > 0$ for some $i\in B\sm A$, then we have 
$$
x_i \mu((S_B)_i) < x_i (|B| -1)!\, \Vol ((S_B)_i),
$$ 
and so 
$$
\mu(S_B) < (|B|-1)! \sum _{j\in B} x_j \Vol((S_B)_j) 
\le |B|!\, \Vol(S_B),
$$ 
as in the proof of Theorem~\ref{2.2}.  Hence in this case $S_B$ is 
not a skew-cube, by Theorem~\ref{2.2p} again.

If on the other hand $x_i = 0$ for every $i\in B\sm A$, then
$\bx \in S_A$. Then there is a point $\bz$ of $S_A$ not in the union
of the cones $\conv(\bx, (S_A)_i)$. Clearly $\bz$ is also a 
point of $S_B$ not in the union of the cones $\conv(\bx,(S_B)_i)$,
which gives a contradiction. 
\end{proof}

The previous characterization is perhaps unsurprising given the proof
of Theorem~\ref{2.2}.  The other result we give characterizing
skew-cubes is quite different in character.  Our experience so far
suggests that this is in many ways a more useful result than
Theorem~\ref{2.2p}.

\begin{theorem} \label{5.1}
A convex corner $S$ in $\Rnp$ is a skew-cube if and only if, for every
subset $A$ of $[n]$, all the maximal points of $S_A^\circ$ lie on a
hyperplane.  Furthermore, if $S$ is a skew-cube, then the vector $\bx$
satisfies $\mu(S) = \sum _{i=1}^n x_i \mu(S_i)$ if and only if all the
maximal points $\by$ of $S^\circ$ lie on the hyperplane 
$\bx \cdot \by = 1$.  
\end{theorem}

Before moving to the proof of Theorem~\ref{5.1}, we need a lemma
characterizing maximal points in convex corners that are polytopes.

\begin{lemma} \label{5.2}
Let $S$ be a convex corner that is a polytope, and let $\bx$ be a point
of $S$. Then the following are equivalent.

\noindent {\rm (a)} \quad
$\bx$ is maximal.

\noindent {\rm (b)} \quad
For $i=1, \dots, n$, there is a point $\bz \in S^\circ$, 
with $z_i > 0$, such that $\bx\cdot \bz = 1$.

\noindent {\rm (c)} \quad
There is a point $\by \in S^\circ$, with $y_i > 0$ for every
$i$, such that $\bx\cdot \by = 1$. 
\end{lemma}

\begin{proof}
{(a) $\Rightarrow$ (b)} \quad 
Suppose that there is no point $\bz \in S^\circ$ with 
$\bx \cdot \bz = 1$ and $z_1 > 0$. Then there is $\eps > 0$ such
that, for all of the finitely many {\it vertices} $\bz$ of $S^\circ$,
$\bx \cdot \bz \le 1-\eps z_1$.  Then we have 
$(\bx + \eps \be_1) \cdot \bz \le 1$, for every vertex 
$\bz \in S^\circ$, where $\be_1$ denotes the first basic unit
vector. This implies that $\bx + \eps \be_1 \in S$, contradicting
the maximality of $\bx$.

\noindent {(b) $\Rightarrow$ (c)} \quad
If, for each $i$, there is a point $\bz(i) \in S^\circ$ with $z(i)_i > 0$ 
and $\bx\cdot \bz(i) = 1$, then the point
$\by = \frac{1}{n}\sum _{i=1}^n \bz(i)$ has $\bx\cdot \by =1$
and $y_i > 0$ for every $i$.

\noindent {(c) $\Rightarrow$ (a)} \quad
Let the vector $\by$ be as given.  For any vector $\bw$ in $S$ with
$w_i\ge x_i$ for every $i$, we have 
$1 \ge \bw \cdot \by \ge \bx \cdot \by = 1$, and so $w_iy_i = x_iy_i$
for every $i$, which implies that $\bw = \bx$.  Therefore $\bx$ is maximal.
\end{proof}

\medskip
\noindent {\bf Proof of Theorem~\ref{5.1}.} \hspace*{1em}
Note that, if $S$ is a skew-cube, then it is a polytope, and
hence so is $S^\circ$. The condition of the theorem also implies that
$S^\circ$ is a polytope, as it is defined by at most $2^n$
hyperplanes, and hence so is $S$. Thus we may restrict attention to
those convex corners that are polytopes.

Thus, by Theorem~\ref{2.3}, it is enough to prove that, for convex
corners $S$ that are polytopes, the condition that all the maximal
points $\by$ of $S^\circ$ lie on the hyperplane given by 
$\bx \cdot \by = 1$ is equivalent to $S$ being the union of the cones
${\rm conv}(\bx, S_i)$.

Suppose first that all the maximal points $\by$ of $S^\circ$ lie on
the hyperplane $\bx \cdot \by = 1$.  Then $\bx\cdot \bw \le 1$ for
every point $\bw$ of $S^\circ$, and so (since $S$ is a convex corner)
$\bx \in S$. By Lemma~\ref{5.2}, $\bx$ is maximal in $S$, since for
every $i$ there is a maximal point of $S^\circ$ with non-zero 
$i^{\rm th}$ co-ordinate.

Now take any point $\bz\not=\bx$ of $S$, and choose a co-ordinate $i$
to minimize $z_i/x_i$. This minimum $\lambda$ is strictly less than 1,
since otherwise $z_i \ge x_i$ for each $i$, and so $\bz = \bx$ by
maximality of $\bx$.  Now consider the point $\bv$ satisfying 
$\bz = \lambda \bx + (1-\lambda) \bv$. Note that $v_i = 0$, and 
$v_j \ge 0$ for all $j$, by choice of $\lambda$. If $\bv \notin S$,
then there is a point $\by$ of $S^\circ$ with $\bv\cdot \by > 1$, and
we may take $\by$ to be maximal. But then 
$$
\bz \cdot \by = \lambda \bx \cdot \by + (1-\lambda) \bv \cdot \by 
> \lambda + (1-\lambda) = 1,
$$ 
which is not possible since $\bz \in S$ and $\by\in S^\circ$.
Therefore $\bv\in S$, and hence $\bv\in S_i$, and so 
$\bz\in {\rm conv}(\bx, S_i)$. But $\bz$ was arbitrary, so $S$ is
equal to the union of the cones, as required.

Conversely, suppose that $S$ is the union of the cones 
${\rm conv}(\bx, S_i)$, but there is a maximal point $\bw$ of
$S^\circ$ with $\bx\cdot \bw < 1$. By Lemma~\ref{5.2}, there is a
point $\bz$ of $S$, with all co-ordinates $z_i$ positive, and 
$\bz \cdot \bw =1$.  We can take 
$\bz = \lambda \bx + (1-\lambda) \bv$, for some $\bv$ in some $S_i$,
and some $\lambda$ between 0 and 1. We have $\lambda >0$, since $\bz$
is not in any $S_i$. This gives 
$$
1 = \bz\cdot \bw = \lambda \bx\cdot \bw + (1-\lambda) \bv \cdot \bw 
< \lambda + (1-\lambda) \bv \cdot \bw.
$$ 
This implies that $\bv \cdot \bw > 1$, which is not possible
since $\bv$ is in $S$ and $\bw$ in $S^\circ$.

This completes the proof.
\endproof

\subsection{Lower bounds on the content} \label{lbc}

We conclude this section by discussing how far from equality we can
get in Theorem~\ref{2.2}.  It is perhaps not immediately obvious that
there is any lower bound for $\mu(S)$ in terms of the volume of $S$,
but notice that any cuboid inside $S$ is certainly a skew-cube, so
$\mu(S) \ge V(S)$.  Now we conclude from Kahn and Kim's result, 
Theorem~\ref{KaKi}, that
$$
\frac{1}{n!} \mu(S) \le \Vol (S) \le \frac{n^n}{n!^2} \mu(S)
\le \frac{e^n}{n!} \mu(S),
$$ 
i.e., that $\frac{1}{n!} \mu(S)$ also approximates $\Vol(S)$ to 
within a factor of $e^n$.

Presumably the factor of $e^n$ above can be improved upon
substantially.  To pose this problem precisely, let us define, for a
convex corner $S$ in $\Rnp$, 
$$ 
\phi(S) = \left( \frac{n! \Vol (S)} {\mu(S)} \right) ^{1/n}.  
$$ 
We have that $1\le \phi(S) < e$ for all convex corners $S$.  It would
be of interest to find the value of the supremum $\phi$ of $\phi(S)$
over all convex corners $S$.

Two families of examples that seem to be reasonable candidates for
large values of $\phi(S)$ are the families $B_p^n$ and $T_t^n$ defined
in \S\ref{Definitions}.  It turns out that $\phi(B_p^n) \le 1.2883$
for all $p$ and $n$, while $\phi(T_{an}^n) > 1.2984$ when
$a\simeq 0.3581$ and $n$ is large.  (Surprisingly, estimating the 
volume of $T_t^n$ seems not to be easy -- we intend to give details
elsewhere.)  Thus we have the bounds
$$
1.2984 < \phi \le e.
$$
We strongly believe that the lower bound is closer to the true value
of $\phi$. 
 
\section{Inequalities Involving the Polar} \label{sec:Polar}

We now turn our attention to Theorem~\ref{2.7}, stating that
$\mu(S)\mu(S^\circ) \ge n!$ for every $n$-dimensional convex corner
$S$.  Before proving this, we need one easy preliminary lemma.

\begin{lemma} \label{2.6}
For any convex corner $S$ in $\Rnp$, and any co-ordinate $i$,
$(S^\circ)_i = (S_i)^\circ$.
\end{lemma}

\begin{proof}
Note that $S_i$, and hence also, by definition, $(S_i)^\circ$, lie in the
$i^{\rm th}$ co-ordinate plane.

If $\bx\in (S^\circ)_i$, then $x_i = 0$, and 
$\sum _{j=1}^n x_j y_j \le 1$ for every $\by \in S$. Hence certainly
$\sum _{j\not=i} x_j y_j \le 1$ for every $\by \in S_i$, so 
$\bx \in (S_i)^\circ$.

Conversely if $\bx \in (S_i)^\circ$, then $x_i = 0$, and
$\sum _{j\not=i} x_j y_j \le 1$ for every $\by \in S_i$. Since
$S$ is a down-set, for every point $\bz\in S$, the projection of
$\bz$ onto the $i^{\rm th}$ co-ordinate plane is in $S_i$. Hence
$\sum _{j=1}^n x_j z_j = \sum _{j\not=i} x_j z_j \le 1$, so
$\bx \in S^\circ$, and therefore in $(S^\circ)_i$.
\end{proof}

It is worth observing that the assumption that $S$ is a down-set (or,
equivalently, that our underlying norm is 1-unconditional) is crucial
to Lemma~\ref{2.6}. From now on, this assumption will be used
implicitly whenever we write $S_i^\circ$, which we can do without
ambiguity whenever $S$ is a convex corner.

\medskip
\noindent {\bf Proof of Theorem~\ref{2.7}.} \hspace*{1em}
We prove the result by induction on $n$. It is trivially true for
$n=0$.  Suppose the result is true in dimension $n-1$, and let $S$ be
any convex corner in $\Rnp$.  We have that 
$\mu(S_i) \mu(S_i^\circ) \ge (n-1)!$ for each $i$.

Define the vector $\by$ by setting $y_i = \mu(S_i)/\mu(S)$.
By the definition of $\mu(S)$, we have $\bx \cdot \by \le 1$
for every $\bx \in S$, which means that $\by \in S^\circ$.

So
\begin{align} 
\mu(S^\circ) &\ge  \sum _{i=1}^n y_i \mu(S^\circ_i) \notag\\
&= \frac{1}{\mu(S)} \sum _{i=1}^n \mu(S_i) \mu(S^\circ_i) \notag\\
&\ge  \frac{1}{\mu(S)} \sum _{i=1}^n (n-1)!, \notag
\end{align}
and thus $\mu(S) \mu(S^\circ) \ge n!$.  The result follows by induction.
\eproof

Let us stress once more that the only novelty here, compared with
Meyer's proof of Saint-Raymond's Theorem, is in the explicit use of
the content, and in the separation of Theorem~\ref{2.7} from issues
concerning the volume.    

We shall be interested in when we have equality in Theorem~\ref{2.7},
i.e., for which $S$ we have $\mu(S) \mu(S^\circ) = n!$; we say that
$S$ is {\em $\mu$-minimal}.  (The choice of terminology
follows that used in connection with Saint-Raymond's Inequality, where
a convex corner $S$ in $\Rnp$ is called {\em minimal} if
$\Vol(S)\Vol(S^\circ) = 1/n!$.)  Let us note here that, as an
immediate consequence of the proof of Theorem~\ref{2.7}, if $S$ is
$\mu$-minimal, then so is every $S_i$.  Also, if $S$ is $\mu$-minimal,
then the vector $\by$ defined in the proof, with 
$y_i = \mu(S_i) / \mu(S)$, must maximize 
$\sum _{i=1}^n y_i \mu(S_i^\circ)$ over all vectors in $S^\circ$.

We have already noted that Theorems~\ref{2.2} and~\ref{2.7} combine to
give Saint-Raymond's Inequality, Corollary~\ref{2.20}, and also
Theorem~\ref{2.9}.  If we use Theorem~\ref{2.2p} in place of
Theorem~\ref{2.2}, we get the following strengthening of
Corollary~\ref{2.20}.

\begin{corollary} \label{2.8}
For any convex corner $S$ in $\Rnp$, there are skew-cubes 
$Q\subseteq S$ and $Q'\subseteq S^\circ$ such that 
$$
\Vol(Q) \Vol(Q') \ge \frac{1}{n!}.
$$
\end{corollary}

Weaker versions of Corollary~\ref{2.8} might be more immediately
appealing.  For instance, we can conclude that there are convex
polytopes $R\subseteq S$ and $R'\subseteq S^\circ$ with 
$\Vol(R) \Vol(R') \ge 1/n!$.  Furthermore, $R$ and $R'$ each have at
most $2^n$ vertices -- this is Theorem~\ref{2.21}. Even more, there
are maps from the discrete cube $\{ 0,1\}^n$ to these sets of vertices
that respect the co-ordinates.

Meyer~\cite{Mey} and Reisner~\cite{Rei} showed that there is only a
very small class of convex corners $S$ with 
$\Vol(S) \Vol(S^\circ) = 1/n!$, namely those $S$ that can be built up
from 1-dimensional convex corners by $\ell_1$- and $\ell_\infty$-sums.
However, it is not too hard to show that suitable symmetry conditions
are enough to imply that $S$ is $\mu$-minimal.

For instance, suppose the symmetry group of $S$ includes all the $n!$
isometries permuting the co-ordinate axes; the same is then true of
$S^\circ$.  This also implies that all the $S_i$ are isomorphic, as are
all the $S_i^\circ$.  We may suppose by induction that all the $S_i$
are $\mu$-minimal, i.e., $\mu(S_i)\mu(S_i^\circ) = (n-1)!$.  
Let $\by$ and $\bz$ be the points on the
boundaries of $S$ and $S^\circ$, respectively, with all co-ordinates
equal, say to $y$ and $z$ respectively.  Then certainly $yz \le 1/n$.
As noted earlier, the maximizations defining $\mu(S)$ and
$\mu(S^\circ)$ occur at $\by$ and $\bz$ respectively, so 
$$
\mu(S)\mu(S^\circ) = 
\sum _{j=1}^n y \mu(S_j) \sum _{k=1}^n z \mu(S_k^\circ) = 
n^2 y z \mu(S_1)\mu(S_1^\circ) \le n!,
$$ 
and $S$ is $\mu$-minimal.

For example all of the convex corners in the families $B_p^n$ and
$T_t^n$ are $\mu$-minimal -- for $S=B_p^n$, this can also easily be
verified by direct calculation, since we have 
$\mu(S)\mu(S^\circ) = (n!)^{1-1/p}(n!)^{1-1/q} = n!$.

In fact, somewhat weaker symmetry conditions suffice for
$\mu$-minimality.  On the other hand, it would be misleading to think
that a $\mu$-minimal $S$ necessarily has any symmetry properties: when
we consider the case of stable set polytopes of graphs in
\S\ref{mussp}, we shall see examples of highly asymmetric bodies that
are nevertheless $\mu$-minimal.

\medskip

We can say more about the situation where $S$ is $\mu$-minimal and
$S^\circ$ is a skew cube, so that 
$\mu(S) = n!/\mu(S^\circ) = 1/\Vol(S^\circ)$, i.e., we have equality
in Theorem~\ref{2.9}.  Note that there is no real loss of generality
involved in imposing the condition that all the basic unit vectors are
on the boundary of $S$, since any convex corner can be made to satisfy
this condition by re-scaling, i.e., changing the scales on the axes.

\begin{theorem} \label{6.11}
Let $S$ be a convex corner in $\Rnp$ with all the basic
unit vectors $\be_i$ on the boundary of $S$. Suppose that $S$ is 
$\mu$-minimal, and that $S^\circ$ is a skew-cube. Then $S$ is a 0-1 
polytope.
\end{theorem}

\begin{proof}
First observe that, since $S^\circ$ is a skew-cube, it is a polytope,
and hence so is $S$.

Suppose that $S$ has a vertex that is not a 0-1 vector, and take one,
say $\bx$, with minimal support, say $A$. By the remarks after the
proof of Theorem~\ref{2.7}, we have that $S_A$ is $\mu$-minimal, and
furthermore that the vector $\by$ given by 
$y_i = \mu((S_A)_i)/\mu(S_A)$ maximizes 
$\sum_{i\in A} y_i \mu((S_A^\circ)_i$ over $S_A^\circ$. Moreover,
Theorem~\ref{5.1} tells us that all the maximal points $\bz$ of $S_A$
lie on the hyperplane $\by \cdot \bz = 1$. In other words, all maximal
points $\bz$ of $S_A$ satisfy 
$\mu(S_A) = \sum _{i\in A} z_i \mu((S_A)_i)$. This implies that, for
each maximal $\bz$, $S_A$ is the union of the cones 
$\conv(\bz, (S_A)_i)$.

Since $\bx$ is non-integral, there is a co-ordinate $i$ with
$0 < x_i < 1$. Since $\be_i \in S_A$, there is a maximal point
$\bz \in S_A$ with $z_i = 1$, so in particular $\bz \not= \bx$.
By the above, $\bx$ is a convex combination of $\bz$ and some point
$\bw$ in some $(S_A)_j$. This contradicts the assumption that $\bx$
is a vertex, since $\bx$ is equal to neither $\bz$ nor (since $\bx$
has support $A$) $\bw$.  Thus $S$ is a 0-1 polytope.
\end{proof}

Theorem~\ref{6.11} goes some way towards determining the convex
corners $S$ for which $\mu(S) = 1/ \Vol(S^\circ)$, but we have not 
managed to completely describe the class of such convex corners. 
We comment further on this problem in \S\ref{later}.

\medskip

We close this section by considering how far $\mu(S) \mu(S^\circ)$ can
be from $n!$.  An upper bound for the product follows from
Theorem~\ref{2.2} and Santal\'o's Theorem, namely that
$$
\frac{\mu(S) \mu(S^\circ)}{n!^2} \le \Vol(S) \Vol(S^\circ) \le
\left(\Vol(B^n_2)\right)^2 = 
\frac{(\pi/4)^n}{\Gamma(1+n/2)^2}.
$$
Since $\Gamma(1+n/2)^2 \ge n! 2^{-n}$ for all integers $n$, we have that
$$
n! \le \mu (S) \mu(S^\circ) \le n! \left( \frac{\pi}{2} \right) ^n.
$$
As we have already seen, actually $\mu(B^n_2)^2 = n!$, so we would expect
the upper bound above on $\mu(S) \mu(S^\circ)$ to be rather weak.

For $S$ a convex corner in $\Rnp$, set
$$
\eta(S) = \left( \frac{\mu(S) \mu(S^\circ)}{n!} \right) ^{1/n}.
$$
The previous argument shows that 
$1\le \eta(S) \le \pi/2 \simeq 1.5708$ for all convex corners $S$.  As
for the constant $\phi$ in the previous section, it would be
interesting to find the value of the supremum $\eta$ of $\eta(S)$ over
all convex corners $S$.

The best lower bound for $\eta$ we have been able to find is based on the
2-dimensional convex corner $T$ maximizing $\mu(T)\mu(T^\circ)$. 

\begin{theorem} \label{3.3}
For a convex corner $S$ in $\bbR_+^2$, 
$2\le \mu(S)\mu(S^\circ) \le \frac{9}{4}$. The upper bound is achieved
when $S$ is the convex hull $T$ of $(0,0)$, $(0,1)$, $(1,0)$ and
$(1,1/2)$, in which case $S^\circ$ is the reflection of $T$ in the
diagonal $x=y$.  
\end{theorem}

We omit the straightforward proof.  There is a notion of the
``$T$-sum'' of convex corners, for the 2-dimensional body $T$ above:
repeatedly taking $T$-sums yields a sequence of bodies $T_j$ with
$$
\eta(T_j) = \frac{ \prod_{i=1}^j 
\left( 2^{2^{i-1}-1} + \binom{2^i -1}{2^{i-1}} 2^{-2^{i-1}} \right)
^{2^{1-j}}}{\left( 2^j! \right) ^{1/2^j}} \to 1.31527\dots
$$ 
as $j\to\infty$.  Hence we have
$$
1.3152 \le \eta \le \frac{\pi}{2} \simeq 1.5708.
$$ 
We think it is just about possible that the lower bound gives the
correct value of $\eta$; however, we have not been able to show even
that $\eta < \pi/2$.

\section{Stable set polytopes of graphs} \label{graphs} 

\subsection{Graph-content} \label{mussp}

Recall that the graph-content $\mug(G)$ of a graph $G$, introduced by
Sidorenko~\cite{Sid}, is $\mu(\Stab(G))$.  Since the stable set
polytope $\Stab(G)$ of $G$ is a convex corner, the results of the
previous sections apply; for instance, we obtain Theorem~\ref{4.1}.
We have also noted that the polar $\FStab(\ol G)$ of $\Stab(G)$ is equal to
$\Stab(\ol G)$ if and only if $G$ is perfect.  Thus
we have the following consequence of Theorem~\ref{2.7}.

\begin{theorem} \label{4.3}
\quad {\rm (a)} \quad
For any graph $G$ on $n$ nodes, $\mug(G) \mu(\FStab(\ol G)) \ge n!$. 

\noindent {\rm (b)} \quad
For any perfect graph $G$ on $n$ nodes, $\mug(G) \mug(\ol G) \ge n!$.
\end{theorem} 

Theorem~\ref{4.3}(b) is essentially proved by Sidorenko~\cite{Sid};
although he states the result only for comparability graphs of partial
orders, his proof works in the general setting of perfect graphs.  As
noted by Sidorenko in~\cite{Sid}, the result does not hold for all
graphs: the smallest example is, not surprisingly, $G = \ol G = C_5$,
when $\mug(G)\mug(\ol G) = 10^2 < 5!$.

Of course we can also combine Theorems~\ref{4.1} and~\ref{4.3}, or
apply our earlier results on volume directly, to obtain the following
results.

\begin{theorem} \label{4.4}
Let $G$ be a graph on $n$ nodes.

\noindent {\rm (a)} \quad 
$\displaystyle{\mug(G) \ge \frac{1}{\Vol(\FStab(\ol G))}}$.

\noindent {\rm (b)} \quad 
$\displaystyle{\Vol(\Stab(G)) \Vol(\FStab(\ol G)) \ge \frac{1}{n!}}$.

\noindent {\rm (c)} \quad 
If $G$ is perfect, then 
$\displaystyle{\Vol(\Stab(G)) \Vol(\Stab(\ol G)) \ge \frac{1}{n!}}$. 
\qed
\end{theorem}

Parts (b) and (c) of Theorem~\ref{4.4} were first stated in
Bollob\'as, Brightwell and Sidorenko~\cite{BBS}.  Again, some
condition on $G$ is required for the conclusion of
Theorem~\ref{4.4}(c) to hold. Rather than give an explicit example
to illustrate this, let us consider what happens when we take $G$ to
be a {\em random graph} $G_{n,1/2}$.

Almost surely, there is no stable set in $G = G_{n,1/2}$ containing
more than $2\log_2 n$ nodes. Therefore, all of $\Stab(G)$ lies
inside $\{ \bx \in [0,1]^n : \sum x_i \le 2\log_2 n \}$, a body of
volume at most $(2\log_2 n)^n / n!$. The same is true for the
complement, another copy of $G_{n,1/2}$ and so, for almost every $G$,
we have
$$
\Vol(\Stab(G)) \Vol(\Stab(\ol G)) \le \frac{(2\log_2 n)^{2n}}{n!^2},
$$
which is much less than $1/n!$ for large enough $n$. 

This argument shows that, for $G=G_{n,1/2}$, we almost surely have
$\mug(G) \le (2\log_2 n)^n$ -- indeed it is trivial that, for any
graph $G$ with largest independent set of size $k$, $\mug(G) \le k^n$.
In fact, one can show that this is a fairly good estimate of $\mug(G)$
for a random graph $G$.

We next look at cases of equality in the various inequalities in
Theorems~\ref{4.3} and \ref{4.4}. We start with the strongest
inequality, namely Theorem~\ref{4.3}(a); to say that we have equality
here for a graph $G$ amounts to saying that $\Stab(G)$ is
$\mu$-minimal.

Let $P_4$ denote the path on 4 nodes. It is easy to check that 
$\mug(P_4) = 5$. Now $P_4$ is perfect, and its complement is again a
copy of $P_4$, so we have 
$$
\mug(P_4) \mu(\FStab(\ol {P_4})) = \mug(P_4) \mug (P_4) = 25 > 4!,
$$
so $\Stab(P_4)$ is not $\mu$-minimal.  

Now, if $\Stab(G)$ is $\mu$-minimal, then, as noted after the proof of
Theorem~\ref{2.7}, so is every $(\Stab(G))_A$, for $A$ a subset of the
node set of $G$.  This means that $\Stab(H)$ is $\mu$-minimal for
every induced subgraph $H$ of $G$.  Thus we have that, if $G$ is
$\mu$-minimal, then $G$ contains no induced copy of $P_4$.

Graphs with no induced copy of $P_4$ are called {\em cographs}, and they 
are made up recursively from one-node graphs by the two operations of 
\begin{itemize}
\item {\em disjoint union} $G_1 \cup G_2$: taking copies of graphs
$G_1$ and $G_2$ on disjoint node sets, and putting no edges between the two, 
\item {\em disjoint sum} $G_1 + G_2$: taking copies of graphs 
$G_1$ and $G_2$ on disjoint node sets, and adding all the edges between 
the two sets.
\end{itemize} 
Cographs are comparability graphs of partial orders.  Thus we can use 
Theorem~\ref{4.8} and/or Theorem~\ref{4.9} to calculate 
$\mug(G) = n! \Vol(\Stab(G))$ for $G$ a cograph, or indeed we can work
directly from the definition of graph-content.  One obtains the
recursive formulae below, as first noted by Sidorenko~\cite{Sid}. 

\begin{lemma} \label{cographs}
If $G_1$ and $G_2$ are graphs on $n_1$ and $n_2$ nodes respectively, then 
\begin{align} 
\mug(G_1\cup G_2) &= \binom{n_1+n_2}{n_1} \mug(G_1) \mug(G_2), \notag\\
\mug(G_1 + G_2) &= \mug(G_1) \mug(G_2).\notag
\end{align}
\qed
\end{lemma} 

\begin{theorem} \label{4.6} 
For any of the inequalities in Theorems~\ref{4.3} and~\ref{4.4}, the
graph $G$ satisfies the inequality with equality if and only if $G$ is
a cograph.
\end{theorem}

\begin{proof} 
We have already seen that, if $G$ is not a cograph, then it does not
achieve equality in Theorem~\ref{4.3}(a), and so does not achieve
equality in any of the inequalities.

It remains to be shown that cographs satisfy all the inequalities
exactly.  Since we know that 
$\Vol(\FStab(G)) = \Vol(\Stab(G)) = \mug(G)/n!$ for $G$ an
$n$-node cograph, it is enough to show that $\mug(G)\mug(\ol G)=n!$ 
for all cographs $G$.  As shown by Sidorenko in~\cite{Sid}, this
follows readily on using Lemma~\ref{cographs}. 
\end{proof}

\subsection{0-1 convex corners} \label{0-1}

Combining Sidorenko's and Stanley's Theorems shows that the stable set
polytopes of comparability graphs of partial orders are skew-cubes,
i.e., $\mug(G) = \Vol(\Stab(G))$ whenever $G$ is the comparability
graph of a partial order.  Theorem~\ref{5.3}, which we now prove,
implies that this equality holds for the somewhat wider class of
strongly perfect graphs, but not for any other graphs.  Furthermore,
there are no examples of 0-1 polytopes that are skew-cubes, but are
not stable set polytopes of graphs.  Our proof is a direct application
of the characterization of skew-cubes given in Theorem~\ref{5.1}.

\medskip
\noindent {\bf Proof of Theorem~\ref{5.3}.} \hspace*{1em}
Let $S$ be a 0-1 convex corner in $\Rnp$.

Suppose first that $S$ is not the stable set polytope of a graph. This
implies that there is a subset $A$ of $[n]$ such that all the
2-element subsets of $A$ correspond to vertices of $S$, but $A$ itself
does not.  If we further take $A$ minimal with this property, then we
have that all proper subsets of $A$ correspond to vertices of $S$, but
$A$ does not.  Now all the basic unit vectors $\be_i$ are maximal
points of $S_A^\circ$, and so is the vector 
$(\frac{1}{|A|-1}, \dots, \frac{1}{|A|-1})$. These vectors do not lie
on a common hyperplane so, by Theorem~\ref{5.1}, $S$ is not a skew-cube.

Now suppose that $S$ is the stable set polytope of a graph $G$, and
that $S$ is a skew-cube.  Take any induced subgraph $H$ of $G$, say on
node set $A$.  Each maximal clique $C$ in $H$ corresponds to a maximal
point $\be_C$ in $S_A^\circ$.  (Typically, there are other maximal
points as well.)  By Theorem~\ref{5.1}, all the points of $S_A^\circ$
corresponding to maximal cliques lie on a hyperplane 
$\bx\cdot \by = 1$, where $\bx\in S_A$. Therefore there must be a 
{\em vertex} $\bz$ of $S_A$ such that $\bz\cdot \be_C = 1$ whenever
$C$ is a maximal clique in $H$.  This vertex $\bz$ corresponds to a
stable set in $H$, which therefore meets all the maximal cliques.  We
deduce that $G$ is strongly perfect.

Now suppose that $S$ is the stable set polytope of a strongly perfect
graph $G$. Since $G$ is perfect, Theorem~\ref{4.2} tells us that
$S^\circ = \Stab(\ol G)$, i.e., that the vertices of $S^\circ$
correspond to the cliques of $G$.

For any induced subgraph $H$ of $G$, say on node set $A$, we have
that there is a stable set $B\subseteq A$ meeting every maximal clique
in $H$.  The vector $\be_B$ then corresponds to a hyperplane through
all the vectors $\be_C$, where $C$ is a maximal clique in $H$, i.e.,
through all the maximal vertices of $S_A^\circ$. This hyperplane
therefore passes through all the maximal points of $S_A^\circ$.  We
deduce from Theorem~\ref{5.1} that $S$ is a skew-cube.  
\endproof

\section{Pointwise products of convex corners} \label{ppcc}

Our aim in this section is to derive inequalities concerning the content
and volume under the condition that the pointwise product of several
convex corners is contained in another.  Before we get properly
underway, we need a few easy preliminary results.  

As we have seen, the pointwise product of polytopes need not be a
polytope.  The next lemma shows that at least the convex hull of such
a product is a polytope. 

\begin{lemma} \label{6.1}
Let $A_1, \dots, A_r$ be any sets in $\Rnp$. Then
$$
\conv(\conv(A_1) \circ \dots \circ \conv(A_r)) = 
\conv(A_1 \circ \dots \circ A_r).
$$ 
\end{lemma}

\begin{proof}
We give the proof for $r=2$ only; the full result can be proved in a
similar way, or can be deduced from the case $r=2$ using induction.

The lemma amounts to saying that any point in 
$\conv(A_1) \circ \conv(A_2)$ can be written as a convex combination
of points from $A_1 \circ A_2$.

Accordingly, suppose that $\bx = \sum _j \lambda _j \bx^j$ is a convex
combination of points $\bx^j$ in $A_1$, and that 
$\by = \sum _k \mu_k \by^k$ is a convex combination of points $\by^k$
in $A_2$.  Then we have 
\begin{align} 
\bx\circ \by &= \big( \sum _j \lambda_j \bx^j\big) 
\circ \big( \sum _k \mu_k \by^k \big) \notag\\ 
&= \sum_{i=1}^n \big( \sum _j \lambda_j (\bx^j)_i \big) 
\big( \sum _k \mu_k (\by^k)_i \big) \notag\\
&= \sum _{i=1}^n \sum _{j,k} \lambda_j \mu_k (\bx^j)_i (\by^k)_i \notag\\ 
&= \sum _{j,k} \lambda_j \mu_k (\bx^j \circ \by^k),\notag
\end{align}
a convex combination of vectors from $A_1 \circ A_2$.
\end{proof}

\begin{theorem} \label{6.2}
If $C_1, \dots , C_r$ are convex polytopes in $\Rnp$, then so is 
$C=\conv(C_1 \circ \dots \circ C_r)$, and $C$ is the convex hull of the 
set of points of the form $\bx^1 \circ \dots \circ \bx^r$, where each 
$\bx^i$ is a vertex of the polytope $C_i$. 
\end{theorem}

\begin{proof} 
This follows immediately on applying Lemma~\ref{6.1} to the sets $A_i$
of vertices of $C_i$.  
\end{proof}

\subsection{Further generalizations of Saint-Raymond's Theorem} 
\label{fgS-R}
 
Recall Theorem~\ref{2.7}, stating that, for $S$ a convex corner in
$\Rnp$, we have $\mu(S) \mu(S^\circ) \ge n!$. In terms of pointwise
products, we can restate this as saying that, if $S$ and $T$ are any
two convex corners in $\Rnp$ with $S\circ T \subseteq B_1^n$, then
$\mu(S^\circ) \mu(T^\circ) \ge n!$.  Indeed, it is not hard to see
that $S$ and $T$ can be taken to be any two bounded sets in $\Rnp$
satisfying the condition: we discuss this carefully a little later.

We aim for generalizations of the inequality above.  The main tool
we need is Theorem~\ref{6.3}, stating that, if $A$, $B$ and $C$ are
convex corners in $\Rnp$ with $A\circ B \subseteq C$, then 
$\mu(A) \le \mu(B^\circ) \mu(C)$.  The proof of this result is very 
similar to that of Theorem~\ref{2.7}.  

\medskip
\noindent {\bf Proof of Theorem~\ref{6.3}.} \hspace*{1em}
As usual, we use induction on $n$ and begin by observing that the
result is trivial in one dimension.

Suppose the result is true in dimensions less than $n$, take any $A$,
$B$ and $C$ in $\Rnp$ satisfying the hypotheses, and find a point 
$\bx \in A$ with $\mu(A) = \sum _{i=1}^n x_i \mu(A_i)$.  Note that
$A_i \circ B_i \subseteq C_i$ for each $i$ so, by the induction
hypothesis, we have 
$$
\mu(A) \le \sum _{i=1}^n x_i \mu(B_i^\circ) \mu(C_i).
$$

Consider the vector $\by$ defined by $y_i = x_i \mu(C_i) /\mu(C)$ for
each $i$. We claim that $\by \in B^\circ$.  To verify this, take any
$\bz \in B$; by our hypothesis we have $\bx \circ \bz \in C$.  This
means that $\mu(C) \ge \sum _{i=1}^n x_i z_i \mu(C_i)$, or that 
$\bz \cdot \by \le 1$. So $\by \in B^\circ$, as claimed.

Finally, observe that we have
$$
\mu(A) \le \mu(C) \sum _{i=1}^n y_i \mu(B_i^\circ) \le 
\mu(C) \mu(B^\circ),
$$
as required. The result follows by induction.
\eproof

Since the condition that $A\circ B \subseteq C$ is equivalent to the
condition that $A\circ B \circ C^\circ \subseteq B_1^n$, we can
restate Theorem~\ref{6.3} in various forms, such as (a) and (b) below.

\begin{theorem} \label{6.4} 
Let $S$, $T$ and $U$ be convex corners in $\Rnp$, with 
$S\circ T \circ U \subseteq B_1^n$. Then:

\noindent {\rm (a)} \quad 
$\mu (S) \le \mu (T^\circ) \mu (U^\circ)$,

\noindent {\rm (b)} \quad 
$\mu ((T\circ U)^\circ) \le \mu (T^\circ) \mu (U^\circ)$,

\noindent {\rm (c)} \quad 
$\mu(S^\circ) \mu(T^\circ) \mu (U^\circ) \ge n!$. 
\end{theorem}

\begin{proof} 
As noted, (a) is equivalent to Theorem~\ref{6.3}. Part (b) 
is the special case of (a) with $S=(T\circ U)^\circ$, and (c) 
follows on combining (a) with Theorem~\ref{2.7}.
\end{proof}

Theorem~\ref{6.4}(c) is a particularly clear extension of
Theorem~\ref{2.7}. It is natural to ask whether it can be extended
further to products of four or more sets.  Indeed, as we now see,
Theorem~\ref{6.3} forms the basis for a natural induction argument
giving the desired results.

\begin{theorem} \label{6.5}
Let $A_1, \dots, A_r, C$ be convex corners in $\Rnp$ such that
$A_1 \circ \dots \circ A_r \subseteq C$. Then
$$
\mu(A_1) \le \mu(A_2^\circ) \dots \mu(A_r^\circ) \mu(C),
$$
and so
$$
n! \le \mu(A_1^\circ) \dots \mu(A_r^\circ) \mu(C).
$$
In particular, if $A_1 \circ \dots \circ A_r \subseteq B_1^n$, then
$$
\mu(A_1^\circ) \dots \mu(A_r^\circ) \ge n!.
$$
\end{theorem}

\begin{proof} The first assertion uses induction on $r$; the case
$r=2$ is just Theorem~\ref{6.3}.  Suppose we have the result for
products of $r-1$ convex corners, and suppose that 
$A_1 \circ \dots \circ A_r \subseteq C$.  Now let 
$A = \conv(A_1 \circ \dots \circ A_{r-1})$.  By Lemma~\ref{6.1}, 
$$
A\circ A_r \subseteq 
\conv((A_1 \circ \dots \circ A_{r-1}) \circ A_r) \subseteq C.
$$ 
Hence, by Theorem~\ref{6.3}, we have 
$$
\mu(A) \le \mu(A_r^\circ) \mu(C).
$$ 
Also we have $A_1 \circ \dots \circ A_{r-1} \subseteq A$ so, by the
induction hypothesis, 
$$
\mu(A_1) \le \mu(A_2^\circ) \dots \mu(A_{r-1}^\circ) \mu (A).
$$ 
Multiplying these two inequalities gives the desired result.

The second assertion of the theorem follows on multiplying through by
$\mu(A_1^\circ)$ and using Theorem~\ref{2.7}. The third is the special
case with $C=B_1^n$.  (Alternatively, the third assertion follows from
the first with $A_1 = B_\infty ^n$ and $C= B_1^n$; and the second
follows from the third with $A_{r+1} = C^\circ$.)  
\end{proof}

A special case of Theorem~\ref{6.5} was earlier given by
Sidorenko~\cite{Sid}; see the notes to Theorem~\ref{6.3} above and
Theorem~\ref{6.10} below.  We think that Theorem~\ref{6.5} is
interesting in its own right, but no doubt its consequences for volume
are more immediately appealing.  The second part of the next result is
Theorem~\ref{6.20}, extending Saint-Raymond's Theorem in a natural
way.

\begin{theorem} \label{6.6p}
Let $A_1, \dots, A_r, C$ be convex corners in $\Rnp$ such that
$A_1 \circ \dots \circ A_r \subseteq C$. Then
$$
\Vol(A_1^\circ) \dots \Vol(A_r^\circ) \ge \frac{1}{n!^{r-1} \mu (C)} 
\ge \frac{1}{n!^r \Vol(C)}.
$$
In particular, if $A_1, \dots, A_r$ are convex corners in $\Rnp$ such
that $A_1 \circ \dots \circ A_r \subseteq B_1^n$, then
$$
\Vol(A_1^\circ) \dots \Vol(A_r^\circ) \ge \frac{1}{n!^{r-1}}.
$$
\end{theorem}

\begin{proof}
This is an immediate consequence of Theorem~\ref{6.5} and 
Theorem~\ref{2.2}.
\end{proof}

Note also that one does not need the $A_i$ in Theorem~\ref{6.6p} to be
convex corners.  It is enough that the $A_i$ are bounded sets in
$\Rnp$, none of them contained in any co-ordinate hyperplane.  For
then, if $B_i$ is the smallest convex corner containing $A_i$, for
each $i$, we have $A_i^\circ = B_i^\circ$, and Theorem~\ref{6.6p} can
be applied to the $B_i$.  What is more, if all the $A_i$ are bounded
and one, say $A_j$, is contained in a co-ordinate hyperplane, then
$A_j^\circ$ will have infinite volume, so the inequality holds in that
case too.  Thus it is enough to assume that the $A_i$ are bounded sets
in $\Rnp$.  Similar remarks apply to Theorem~\ref{6.5} and indeed to
Theorem~\ref{6.3}, where $B$ can be any bounded set in $\Rnp$.

Furthermore, the conclusion of Theorem~\ref{6.6p} can be strengthened
by noting that we can find skew-cubes inside 
$A_1^\circ, \dots, A_r^\circ$ whose volumes satisfy the inequality.
Let us couch Theorem~\ref{6.20} in this more general form.

\begin{theorem} \label{6.7}
Suppose that $A_1, \dots, A_r$ are bounded subsets of $\Rnp$ with 
$A_1 \circ \dots \circ A_r \subseteq B_1^n$.  Then there are
skew-cubes $Q_1 \subseteq A_1^\circ, \dots , Q_r \subseteq A_r^\circ$
such that 
$$
\Vol(Q_1) \dots \Vol(Q_r) \ge \frac{1}{n!^{r-1}}.
$$
\qed
\end{theorem}

We discuss Theorem~\ref{6.20} further in \S\ref{addendum}.

\subsection{Pointwise products of stable set polytopes} \label{ppssp}

We wish to interpret some of the results from previous sections in the
case where all the convex corners involved are stable set polytopes of
graphs. Our results will naturally turn out a little more cleanly when
some or all of the graphs are perfect.

In particular, we aim to prove Theorem~\ref{counterexample}, giving a
counterexample to the two conjectures of Bollob\'as and
Leader~\cite{BoLe} mentioned in \S\ref{MainResults}.  Our example
involves stable set polytopes, and accordingly we investigate when
stable set polytopes of graphs $G_1,G_2,G_3$ satisfy the conditions of
their conjectures, namely 
$\Stab(G_1)\circ \Stab(G_2) \circ \Stab(G_3)\subseteq B_1^n$, with 
all the $\Stab(G_i)$ maximal subject to this condition.

We begin with two lemmas explaining how the pointwise product
operation acts on stable set polytopes.

\begin{lemma} \label{6.8}
Let $G_1, \dots, G_r$ be graphs on $[n]$, and let $G$ be the 
edge-union of the $G_i$. Then 
$$
\conv(\Stab(G_1) \circ \dots \circ \Stab(G_r)) = \Stab(G).
$$
\end{lemma}

\begin{proof}
By Theorem~\ref{6.2}, 
$S=\conv(\Stab(G_1) \circ \dots \circ \Stab(G_r))$ is the convex hull
of the set of points of the form 
$\be_{X_1} \circ \dots \circ \be_{X_r} = \be_{\cap X_i}$, where each
$X_i$ is a stable set in the corresponding $G_i$.  The sets that occur
as $\cap X_i$ are exactly the stable sets in $G$, so the vertices of
$S$ are exactly the indicator vectors of stable sets in $G$, as
required.  
\end{proof}

We say that the $r$-tuple $(G_1, \dots ,G_r)$ of graphs on $[n]$ is
{\em exhaustive} if each $S_i = \Stab(G_i)$ is a maximal convex corner
subject to the condition that 
$S_1 \circ \dots \circ S_r \subseteq \Stab(G)$, where $G$ is the
edge-union of the $G_i$.

\begin{theorem} \label{6.9}
Let $G_1, \dots ,G_r$ be graphs on $[n]$, and let $G$ be their
edge-union.  

\noindent {\rm (a)}\quad  
If $(G_1, \dots, G_r)$ is exhaustive, then the $G_i$ are edge-disjoint.  

\noindent {\rm (b)}\quad 
If the $G_i$ are edge-disjoint and each $G_i$ is perfect, then 
$(G_1, \dots, G_r)$ is exhaustive.  

\noindent {\rm (c)}\quad 
If $G$ is perfect, then $(G_1,\dots, G_r)$ is exhaustive if and 
only if the $G_i$ are edge-disjoint and each $G_i$ is perfect.  
\end{theorem}

\begin{proof} 
(a) \quad 
If the $G_i$ are not edge-disjoint, then we can delete a duplicated
edge from some $G_j$, increasing $\Stab(G_j)$, and preserving the
union $G$ of the $G_i$. So by Lemma~\ref{6.8}, the original
$\Stab(G_j)$ was not maximal, and the original $r$-tuple of graphs was
not exhaustive.

\noindent (b) \quad
Suppose that the $G_i$ are edge-disjoint, and that the $G_i$ are all
perfect.  Suppose further that $\Stab(G_1)$ is not maximal, so that
there is a point $\bx$ not in $\Stab(G_1)$ with 
$\bx \circ \Stab(G_2) \circ \dots \circ \Stab(G_r) \subseteq
\Stab(G)$.  Since $G_1$ is perfect, we have that 
$\bx \notin \Stab(\ol{G_1})^\circ$, by Theorem~\ref{4.2}.  Thus there 
is a clique $Y$ in $G_1$ with $\bx \cdot \be_Y > 1$. Since the $G_i$
are edge-disjoint, $Y$ is a stable set in each other $G_i$, so 
$\be_Y \in \Stab(G_2) \circ \dots \circ \Stab(G_r)$.  Hence 
$\bx \circ \be_Y \in \Stab(G)$. Now we have 
$$
\bx \cdot \be_Y = \sum _{i\in Y} (\bx \circ \be_Y)_i \le 1,
$$ 
since $Y$ is a clique in $G$. This is a contradiction, completing the
proof of this part.

\noindent (c) \quad
One direction here follows from (b). For the other, suppose that $G$ is
perfect, and that $G_1$ is not perfect, so
$\Stab(G_1) \subset \Stab(\ol{G_1})^\circ$. Now we claim that
$\Stab({\ol G_1})^\circ \circ \Stab(G_2) \circ \dots \circ \Stab(G_r)
\subseteq \Stab({\ol G})^\circ$, which will complete the proof since
$G$ is perfect and thus $\Stab({\ol G})^\circ = \Stab(G)$.
We know from Lemma~\ref{6.8} that $\Stab(G_2) \circ \dots \circ \Stab(G_r)
\subseteq \Stab(\cup _{i=2}^r G_i)$, which means that we may
assume that $r=2$.

Take any vectors $\bx \in \Stab({\ol G_1})^\circ$ and
$\by \in \Stab(G_2)$; we need to show that
$\bx \circ \by \in \Stab({\ol G_1 \cup G_2})^\circ$.
We may assume that $\by = \be_Y$ for some stable set $Y$ in $G_2$,
since $\bx \circ \by$ is a convex combination of vectors of the
form $\bx \circ \be_Y$.  Now take any clique $Z$ in $G_1\cup G_2$,
and note that
$$
(\bx \circ \be_Y) \cdot \be_Z = \bx \cdot (\be_Y \circ \be_Z) = 
\sum _{i \in Y\cap Z} x_i \le 1,
$$
since $Y\cap Z$ is a clique in $G_1$. Hence
$\bx \circ \be_Y \in \Stab({\ol G_1 \cup G_2})^\circ$, 
as desired.
\end{proof}

What parts (b) and (c) of Theorem~\ref{6.9} actually prove is that the
polytopes $S_i = \Stab(G_i)$ are maximal subject to the weaker
condition that 
$S_1 \circ \dots \circ S_r \subseteq \Stab({\ol G})^\circ$, where $G$ 
is the edge-union of the $G_i$, if and only if the $G_i$ are disjoint 
and all perfect. This is in fact equivalent to the special case of 
Theorem~\ref{6.9}(c) with $G = K_n$, since our condition is exactly that 
$S_1 \circ \dots \circ S_r \circ \Stab(\ol G) \subseteq B_1^n$.

We can now prove Theorem~\ref{counterexample}, giving the
counterexample to the conjectures of Bollob\'as and
Leader~\cite{BoLe}.  Recall that $G_1$, $G_2$ and $G_3$ are the
graphs with node set $\{ 1,2,3\}$ and edge-sets $\{12\}$, $\{13\}$ and
$\{23\}$ respectively, and that the $S_i$ are the stable set polytopes
of the corresponding $G_i$.

\medskip

\noindent {\bf Proof of Theorem~\ref{counterexample}.} \hspace*{1em}
The first assertion amounts to saying that $(G_1,G_2,G_3)$ is
exhaustive, since the edge union of the graphs is $K_3$, and
$\Stab(K_3)=B_1^3$.  This follows from Theorem~\ref{6.9}(b). 

To see that $S_1\circ S_2 \circ S_3 \not= B_1^3$, consider the point
$(\frac{1}{3},\frac{1}{3},\frac{1}{3})$, which is in $B_1^3$.
However, for any point $(a,b,c)\in \Stab(G_1)$, $a+b\le 1$ and 
$c\le 1$, so $abc\le \frac{1}{4}$.  Similarly, for 
$(d,e,f)\in \Stab(G_2)$ and $(g,h,i)\in \Stab(G_3)$, we have 
$def\le \frac{1}{4}$ and $ghi\le\frac{1}{4}$.  Thus 
$abcdefghi \le \frac{1}{64}$, so 
$$
(a,b,c)\circ (d,e,f)\circ (g,h,i) = (adg,beh,cfi) \not= 
\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right).
$$

Finally, we need to verify that $\Vol(\Stab(G_1)) = \frac{1}{2}$.
This can be seen geometrically, analytically, or by observing that
$G_1$ is the comparability graph of a poset with $3=\frac{1}{2}3!$ 
linear extensions.
\eproof 

We look briefly at applications of results from \S\ref{fgS-R} to the
case of stable set polytopes.  By Theorem~\ref{6.3} and
Lemma~\ref{6.8}, we see that, for any graphs $G_1$ and $G_2$, 
$$
\mug(G_1) \le \mu(\Stab(G_2)^\circ) \mug(G_1 \cup G_2).
$$
More generally, using Theorem~\ref{6.5}, we have that if
$H, G_1, \dots ,G_r$ are graphs with edge-union $H_0$, then
$$
\mu(\Stab (H)) \le 
\mu(\Stab(G_1)^\circ) \dots \mu(\Stab(G_r)^\circ) \mu(\Stab(H_0)).
$$
If $G_1, \dots, G_r$ are all perfect, with complements 
$H_1, \dots , H_r$, then we obtain the following result.

\begin{theorem} \label{6.10}
Suppose that $H, H_0$ are graphs, and $H_1, \dots,H_r$ are perfect graphs on 
$[n]$ with $H_0\cap H_1\cap \dots \cap H_r  \subseteq H$. Then
$$
\mug(H) \le \mug(H_0)\mug(H_1) \dots \mug(H_r).
$$
\qed
\end{theorem}

Theorem~\ref{6.10} generalizes a result of Sidorenko, Theorem~14
of~\cite{Sid}, which is the case of the theorem where 
$H_1, \dots, H_r$ are comparability graphs. In this case, as we have
seen, $\mug(H_i)$ has an interpretation as the number of linear
extensions of the corresponding partial order. Theorem~\ref{6.10} is
of course also a generalization of Theorem~\ref{4.3}(b), and we saw
even in that case that the result will fail without some assumption on
some of the graphs involved being perfect.

As usual, it would be straightforward to use Theorem~\ref{2.2} to
derive inequalities involving volumes from Theorem~\ref{6.10} and
other results above.

\subsection{Cases of equality} \label{equality} 

The cases of equality in Theorem~\ref{1.1} were found by
Meyer~\cite{Mey} and Reisner~\cite{Rei}: they showed that 
$\Vol (S) \Vol (S^\circ) = 1/n!$ if and only if $S$ is, after
rescaling, the stable set polytope of a cograph; in other words, if
$S$ can be built up from one-dimensional polytopes by $\ell_1$- and
$\ell_\infty$-sums.  Our aim here is to see when we have equality in
Theorem~\ref{6.20}, i.e., for which $r$-tuples of convex corners $A_1,
\dots, A_r$ with $A_1 \circ \dots \circ A_r \subseteq B^n_1$ we have
$\Vol (A_1^\circ) \dots \Vol (A_r^\circ) = n!^{1-r}$.  Our proof does
not rely on the result of Meyer and Reisner, so we obtain another 
proof of that result which, however, is not essentially different 
from Meyer's.

To describe all cases of equality in Theorem~\ref{6.20}, it is easiest
to regard the various bodies concerned as stable set polytopes of
graphs.  For each $r$, we define the family of {\em complementary}
$r$-tuples of graphs recursively as follows.  Firstly, the family 
$(G, \dots, G)$, where each $G$ is a one-node graph, is complementary.
Then, if $V=V_1\cup V_2$ is any partition of the node set into two
parts, $(H_1, \dots, H_r)$ is a complementary $r$-tuple on $V_1$,
$(H'_1, \dots, H'_r)$ is a complementary $r$-tuple on $V_2$, and 
$j \in [r]$ is any index, then the $r$-tuple $(G_1, \dots, G_r)$ is a
complementary $r$-tuple on $V$, where $G_i = H_i \cup H'_i$ for every
index $i\not=j$, and $G_j = H_j + H'_j$.

If $(G_1, \dots, G_r)$ is a complementary $r$-tuple of graphs on
node set $[n]$, then clearly the $G_i$ are edge-disjoint with union
$K_n$, and furthermore each $G_i$ individually is built up from
one-node graphs by the operations of disjoint union and disjoint
sum, so is a cograph.  However, note that the three one-edge subgraphs
of $K_3$ are all cographs, and their union is $K_3$, but the triple of
graphs is not complementary.
 
Now suppose that $(G_1, \dots ,G_r)$ is a complementary $r$-tuple of
graphs on $[n]$, and consider the stable set polytopes 
$S_i = \Stab(G_i)$.  By Lemma~\ref{6.7}, we have that 
$\conv(S_1 \circ \dots \circ S_r) = \Stab(K_n) = B_1^n$.

\begin{theorem} \label{6.12}
Suppose that $(G_1, \dots ,G_r)$ is a complementary $r$-tuple of
graphs on a node set of size $n$, and let $S_i = \Stab(G_i)$ for
each $i$.  Then 
$$
\Vol (S_1^\circ) \dots \Vol (S_r^\circ) = n!^{1-r}.
$$
\end{theorem}

\begin{proof}
We work by induction on $n$, with the result being trivial for $n=1$. 

For the induction step, suppose that the complementary $r$-tuple
$(G_1, \dots, G_r)$ of graphs on $V$, of size $n$, was obtained from
the two complementary $r$-tuples $(H_1, \dots, H_r)$ and 
$(H'_1, \dots ,H'_r)$ on node sets $V_1$ and $V_2$ of sizes $n_1$
and $n_2$ respectively, with $j$ being the distinguished
index.  Suppose also that $(H_1, \dots, H_r)$ and $(H'_1, \dots, H'_r)$
satisfy the conclusion of the theorem, i.e., 
$$
\Vol (T_1^\circ) \dots \Vol (T_r^\circ) = n_1!^{1-r}
$$ 
and 
$$
\Vol (U_1^\circ) \dots \Vol (U_r^\circ) = n_2!^{1-r},
$$ 
where $T_i = \Stab(H_i)$ and $U_i = \Stab(H'_i)$ for each $i$.

Note that all the graphs involved are strongly perfect, so that for
instance $S_i^\circ = \Stab(\ol{G_i})$, and 
$\Vol(S_i^\circ) = \frac{1}{n!}\mug(\ol G_i)$ for each $i$.  
Now, for $i\not=j$, we have 
$S_i^\circ = \Stab(\ol {G_i}) = \Stab(\ol {H_i} + \ol {H'_i})$ so, 
by Lemma~\ref{cographs}, 
$$
\Vol(S_i^\circ) = \frac{1}{n!}\mug(\ol G_i) = 
\frac{1}{n!}\mug(\ol H_i)\mug(\ol H'_i) =
\frac{n_1!n_2!}{n!} \Vol (T_i^\circ) \Vol (U_i^\circ).
$$
Similarly, $S_j^\circ = \Stab(\ol {H_j} \cup \ol {H'_j})$,
and $S_j^\circ$ has volume $\Vol (T_j^\circ) \Vol (U_j^\circ)$. 

Combining the various identities, we have that
\begin{align} 
\Vol (S_1^\circ) \dots \Vol (S_r^\circ) &= 
\left( \frac{n_1!n_2!}{n!}\right) ^{r-1} 
\Vol (T_1^\circ) \dots \Vol (T_r^\circ)
\Vol (U_1^\circ) \dots \Vol (U_r^\circ) \notag\\
&= \left( \frac{n!}{n_1!\, n_2!} \right) ^{1-r} n_1!^{1-r} n_2!^{1-r} 
= n!^{1-r}, \notag
\end{align}
as desired.
\end{proof}

The converse of Theorem~\ref{6.12} is the content of the next theorem.
Before that, we need one graph-theoretic lemma. 

\begin{lemma} \label{6.13} 
Suppose that $G_1, \dots, G_r$ are edge-disjoint cographs on node
set $[n]$ with union $K_n$, such that no three-element subset of 
$[n]$ contains edges from three different $G_i$. Then
$(G_1, \dots, G_r)$ is a complementary $r$-tuple. 
\end{lemma}

\begin{proof}
Suppose the result is false, and take a counterexample with minimal $n$.

Suppose that none of the $G_i$ is connected, and let $X$ be a largest
component in any $G_i$, with $u$ some node outside $X$ and $v$ some
node inside.  Then the edge $uv$ is in some $G_j$, and the condition
gives that $uw$ is an edge of $G_j$ for every $w\in X$. This means
that $X\cup \{ u\}$ is connected in $G_j$, contradicting the
maximality of $X$.

Thus one cograph $G_j$ is connected, which means it must contain all
the edges between some set $X$ and its complement $Y$, with $X$ and
$Y$ non-empty.  The graph $G_j$ is then the disjoint sum of separate
graphs on $X$ and on $Y$, while all the other graphs $G_i$ are the
disjoint union of graphs on $X$ and on $Y$.  By minimality of $n$, the
$r$-tuples $(G_1|_X, \dots , G_r|_X)$ and $(G_1|_Y, \dots, G_r|_Y)$
are complementary.  Hence so is $(G_1, \dots , G_r)$, a contradiction.
\end{proof}

\begin{theorem} \label{6.14}
Suppose that $A_1, \dots ,A_r$ are convex corners in $\Rnp$
with $A_1 \circ \dots \circ A_r \subseteq B_1^n$, so that
$$
\Vol(A_1^\circ) \dots \Vol(A_r^\circ) \ge n!^{1-r}.
$$  
Suppose that each basic unit vector $\be_j$ is on the boundary of 
each $A_i$.  Then we have equality above if and only if each $A_i$ 
is the stable set polytope of a graph $G_i$ on $[n]$,
and the $r$-tuple $(G_1, \dots ,G_r)$ is complementary.
\end{theorem}

\begin{proof}
By Theorem~\ref{6.5}, we have that, if 
$A_1 \circ \dots \circ A_r \subseteq B_1^n$, then 
$$
\mu(A_1) \le \mu(A_2^\circ) \dots \mu(A_r^\circ).
$$ 
We also have that $n! \le \mu(A_1) \mu (A_1^\circ)$, and that
$\mu(A_i^\circ) \le n! \Vol(A_i^\circ)$ for each $i$.  Multiplying
all these together gives that 
$n!^{1-r} \le \Vol (A_1^\circ) \dots \Vol(A_r^\circ)$, just as in
earlier proofs.  Thus we must have equality in all of the above
inequalities, i.e., $A_1$ is $\mu$-minimal, and all the $A_i^\circ$
are skew-cubes.  Also, $A_1^\circ$ has minimal volume subject to the
condition that 
$A_1 \circ (A_2 \circ \dots \circ A_r) \subseteq B_1^n$, i.e., 
$A_1^\circ = \conv(A_2 \circ \dots \circ A_r)$.

Note that these conditions all pass to co-ordinate subspaces, so we
may use induction on the dimension $n$ of the space. Thus it is
sufficient to show that all the $A_i$ are stable set polytopes of
graphs $G_i$, and that the $r$-tuple $(G_1, \dots ,G_r)$ can be broken
down as in the definition of a complementary $r$-tuple.

By Theorem~\ref{6.11}, we see that $A_1$ is a 0-1 polytope.  By
symmetry, all the other $A_i$ are also 0-1 polytopes.  Thus, by
Theorem~\ref{6.2}, $A_1^\circ = \conv(A_2 \circ \dots \circ A_r)$ is a
polytope, all of whose vertices are the products of 0-1 vectors, so
are themselves 0-1 vectors.  In other words, $A_1^\circ$ is a 0-1
convex corner.  As it is also a skew-cube, Theorem~\ref{5.3} tells us
that $A_1^\circ$ is the stable set polytope of a strongly perfect
graph $H_1$.  Furthermore, since $A_1^\circ$ is $\mu$-minimal, we have
by Theorem~\ref{4.6} (or, rather, the calculation preceding it
concerning $P_4$) that $H_1$ is a cograph.  By symmetry, each
$A_i^\circ$ is the stable set polytope of a cograph $H_i$.

Each $A_i$ is the stable set polytope of the complement $G_i$ of
$H_i$. We need to show that the $r$-tuple $(G_1, \dots, G_r)$ is
complementary.

By Lemma~\ref{6.8}, 
$$
\Stab(G_1) = A_1^\circ = \conv(A_2 \circ \dots \circ A_r) = 
\Stab(H_2 \cup \dots \cup H_r).
$$ 
This implies that $G_1 = H_2 \cup \dots \cup H_r$, i.e., that the
union of all the $H_i$ is the complete graph $K_n$, and that $H_1$ as
no edge in common with any other $H_i$. By symmetry, we deduce that
the $H_i$ are edge-disjoint.

Next we note from the proof of Theorem~\ref{6.5} that we
have $\mu(A_1) = \mu(A_2^\circ) \mu(C)$, where
$C=\conv(A_1\circ A_2)$, which here is the stable set polytope of
$G_1\cup G_2$. Also, from the proof of Theorem~\ref{6.3}, we see
that this implies that $\mu((A_1)_i) = \mu((A_2^\circ)_i) \mu(C_i)$,
for any $i$ such that there is a vector $\bx\in A_1$ with $x_i > 0$ and
$\mu(A_1) = \sum _{i=1}^n x_i \mu((A_1)_i)$. But we know that all maximal
vectors $\bx$ of $A_1$ have this property, so we have
$\mu((A_1)_i) = \mu((A_2^\circ)_i) \mu(C_i)$ for every $i$, and hence
$\mu((A_1)_X) = \mu((A_2^\circ)_X) \mu(C_X)$ for every subset $X$ of $[n]$.

Now consider the case $n=3$, with $G_1$ consisting of one edge, and
$G_2$ a different edge. Then $\mu(A_1) = 3$, $\mu(A_2^\circ) = 2$, and
$\mu(C) = 2$. We conclude that no two of the $G_i$ contain this
configuration; i.e., if $uv \in G_i$ and $vw \in G_j$, then the edge
$uw$ is in either $G_i$ or $G_j$.

The cographs $G_1, \dots, G_r$ thus satisfy the conditions of
Lemma~\ref{6.13}, and hence $(G_1, \dots ,G_r)$ is complementary, as
required.  
\end{proof}

\section{Products of volumes} \label{addendum}

Our main aim here is to prove the various assertions in
Theorem~\ref{product-inequalities}, giving best possible upper and
lower bounds on both $\prod \Vol(A_i)$ and $\prod\Vol(A_i^\circ)$,
when $A_1, \dots, A_r$ are convex corners with 
$A_1\circ \dots \circ A_r \subseteq B_1^n$.

For the upper bound on $\prod \Vol(A_i)$, we use Theorem~12 of
Bollob\'as and Leader~\cite{BoLe}, which is as follows.

\begin{theorem} \label{Bo-Le12} 
If $A_1, \dots , A_r$ are convex corners, then
$$
\Vol \left( (A_1 \circ \dots \circ A_r)^{1/r} \right) \ge 
\left(\Vol(A_1) \dots \Vol (A_r) \right) ^{1/r}.
$$
\end{theorem}
 
Note that the case $r=2$ is the result we quoted earlier as
Theorem~\ref{BoLe}(b).  An instant consequence of
Theorem~\ref{Bo-Le12} is that, if $A_1, \dots, A_r$ are convex corners
(or, for that matter, bounded subsets of $\Rnp$) with 
$A_1\circ \dots \circ A_r \subseteq B_1^n$, then 
$$ 
\Vol (A_1) \dots \Vol (A_r) \le \left( \Vol (B_r^n)\right) ^r.
$$ 
Of course, the case $A_1 = A_2 = \dots = A_r = B_r^n$ shows this to
be best possible.  The case $r=2$ is just Santal\'o's Theorem for
1-unconditional bodies.

For the lower bound, we can use Theorem~\ref{BoLe}(a), also due to
Bollob\'as and Leader, stating that, if $A$ and $B$ are down-sets in
$\Rnp$, then $\Vol(A\circ B) \le \Vol(A) \Vol(B)$.  It follows by
induction that, for any down-sets $A_1, \dots, A_r$ in $\Rnp$, 
$$
\Vol(A_1 \circ \dots \circ A_r) \le \Vol(A_1) \dots \Vol(A_r).  
$$ 
If $A_1\circ \dots \circ A_r = B_1^n$, the left-hand-side is $1/n!$.
To see that this is best possible, let $(G_1, \dots, G_r)$ be a
complementary $r$-tuple of graphs and set $A_i=\Stab(G_i)$ for each
$i$.  Now $\Vol(A_i)\Vol(A_i^\circ) = 1/n!$ for each $i$, and
$\Vol(A_1^\circ) \dots \Vol(A_r^\circ) = 1/n!^{r-1}$, by
Theorem~\ref{6.12}, so $\Vol(A_1) \dots \Vol(A_r) = 1/n!$.  Thus we
have proved part (1) of Theorem~\ref{product-inequalities}.

As we saw in \S\ref{ppssp}, the lower bound 
$\prod \Vol(A_i) \ge 1/n!$ ceases to be
valid if we demand only that the $A_i$ are maximal convex corners
subject to $A_1 \circ \dots \circ A_r \subseteq B_1^n$.  Indeed, we
know of no non-trivial lower bound on $\prod_{i=1}^r \Vol(A_i)$ under
these conditions.  We give an example showing that the product can be
substantially smaller than $1/n!$.

Let $r=2^{d-1}$, and take $d$ independent random linear orderings
$L_1, L_2, \dots, L_d$ on $[n]$.  For a linear order $L$, let $L^*$
denote its reverse.  Now, for each of the $2^{d-1}$ possible choices
$(M_2, \dots, M_d)$, where each $M_i$ is either equal to $L_i$ or
$L_i^*$, construct the partial order 
$L_1\cap M_2 \cap \dots \cap M_d$.  Note that each pair of elements
from $[n]$ is comparable in exactly one of these $r=2^{d-1}$ partial
orders $P_1, \dots, P_r$, so $K_n$ is the edge disjoint union of 
the comparability graphs $C(P_i)$.  By Theorem~\ref{6.9}(b), the 
$r$-tuple $(C(P_1), \dots, C(P_r))$ is exhaustive, so the convex
corners $\Stab(C(P_i))$ are maximal subject to the condition that
their pointwise product is contained in $\Stab(K_n) = B_1^n$. 

Stanley's Theorem, Theorem~\ref{4.9}, tells us that 
$n! \Vol(\Stab(C(P_i))) = e(P_i)$, the number of linear extensions. 
For each $i$, the number of linear extensions is distributed as the
number of linear extensions of a {\em random $d$-dimensional partial
order} $P_d(n)$.  Brightwell~\cite{Bri} showed that, for each fixed
$d$, with probability tending to~1 as $n\to \infty$,  
$$
\left( e^{-2}n^{1-1/d} \right)^n \le e(P_d(n)) \le 
\left( 2dn^{1-1/d} \right)^n. 
$$
Bollob\'as, Brightwell and Sidorenko~\cite{BBS} used Saint-Raymond's
Theorem and Santal\'o's Theorem to improve the constants in both
inequalities above in the case $d=2$.  For $d>2$, the application is 
the other way around.   

Indeed, with probability tending to~1 as $n\to\infty$ with $r=2^{d-1}$
fixed, we have that
$$
\prod _{i=1}^r \Vol(\Stab(C(P_i))) \le 
\left( \frac{(2dn^{1-1/d})^n}{n!} \right) ^r 
\le \left( 2den^{-1/d} \right)^{nr} = n^{-n2^{d-1}/d(1+o(1))}.
$$
For $d\ge 3$, this is much smaller than $1/n!$. 

One can obtain similar examples when $r$ is not a power of 2.  For
instance, if $r=3$, take three linear orders $L_1,L_2,L_3$ as above,
and consider the three partial orders $L_1\cap L_2$, 
$L_1\cap L_2^*\cap L_3$ and $L_1\cap L_2^*\cap L_3^*$, and the stable
set polytopes of their comparability graphs.  The same method shows
that these polytopes satisfy the hypotheses, and gives an upper bound
on the volume product around $n^{-7n/6}$.

\medskip

Turning to the proof of part (2) of Theorem~\ref{product-inequalities}, the
lower bound $\prod_{i=1}^r \Vol(A_i^\circ) \ge n!^{1-r}$  is just 
Theorem~\ref{6.20}.  The remaining assertion that we have to prove is 
that the product is largest when the $A_i$ are all equal to $B_r^n$, 
in which case the $A_i^\circ$ are equal to $B_{r/(r-1)}^n$.  We
restate this as a theorem. 

\begin{theorem} \label{polar-volume-product}
Suppose that $A_1, \dots, A_r$ are convex corners in $\Rnp$ such that
$A_1 \circ \dots \circ A_r = B_1^n$.  Then
$$
\prod _{i=1}^r \Vol(A_i^\circ) \le 
\left( \Vol( B_{r/(r-1)}^n) \right) ^r.
$$
\end{theorem}

\begin{proof}
We apply Theorem~\ref{Bo-Le12} to the $A_i^\circ$. 
Note that each $A_i^\circ$ is the pointwise product of all the 
$A_j$ with $j\not=i$.  Thus 
$$
\prod _{i=1}^r A_i^\circ = \prod _{j=1}^r A_j^{r-1} = (B_1^n) ^{r-1},
$$
so that $(\prod A_i^\circ)^{1/r} = (B_1^n)^{(r-1)/r} = B_{r/(r-1)}^n$.
The result now follows from Theorem~\ref{Bo-Le12}. 
\end{proof} 

The case $r=2$, needless to say, is the unconditional form of
Santal\'o's Theorem.

Again, the condition that the $A_i$ are maximal subject to 
$A_1\circ \dots \circ A_r = B_1^n$ is not sufficient for the
conclusion of Theorem~\ref{polar-volume-product}.  Our three-node
example from Theorem~\ref{counterexample} does not quite work this 
time, but $E(K_4)$ can be partitioned into three copies of the perfect
graph $H$ consisting of two independent edges, and 
$\Vol(\Stab(H)^\circ) = \frac{1}{6}$, while 
$\Vol(B_{3/2}^4) = 0.1655\dots < \frac{1}{6}$.

We end this section with an inequality relating $\prod \Vol(A_i)$ and
$\prod \Vol(A_i^\circ)$.

\begin{theorem} 
If $A_1, \dots, A_r$ are convex corners with 
$A_1 \circ \dots \circ A_r = B_1^n$, then
$$
\prod _{i=1}^r \Vol (A_i^\circ) \le 
\left( \prod _{i=1}^r \Vol(A_i) \right) ^{r-1}.
$$
\end{theorem}

\begin{proof}
We note again that $A_i^\circ = \prod_{j\not=i} A_j$.  By Bollob\'as'
and Leader's Theorem~14, the volume of $A_i^\circ$ is thus at most
$\prod _{j\not=i} \Vol(A_j)$, and the result follows.
\end{proof} 

We always have equality when $r=2$, and also when $A_i = \Stab(G_i)$,
for $(G_1, \dots, G_r)$ a complementary $r$-tuple of graphs. 

\section{Other topics} \label{other}

\subsection{Complexity Issues} \label{complexity}

It is natural to ask whether the content of a convex corner, or at
least of a suitably presented polytope, can be efficiently computed.
The answer, as we explain below, is that exact computation is
\#P-hard, and even approximation may be difficult. 

In the very special case where $S$ is the stable set
polytope of the comparability graph of a partial order $P$, we know
from Theorem~\ref{4.7} that $\mu(S)$ is the number of linear
extensions of $P$. A result of Brightwell and Winkler~\cite{BrWi}
states that it is \#P-complete to calculate the number of linear
extensions of an $n$-element partial order, and it follows that it is
\#P-hard to calculate $\mu(S)$ exactly, even when $S$ has this special
structure.  This also proves that computing the volume of a convex
corner is \#P-hard. 

It seems to be unknown whether it is NP-hard to decide whether a graph
is strongly perfect, although Ho\'ang~\cite{Hoa} has proved that it is
NP-hard to decide whether a graph has a stable set meeting every
maximal clique.  In our terms, this means that we do not know if it is
NP-hard to determine whether a 0-1 convex corner is a skew-cube, i.e.,
whether its content is equal to its volume. 

One very weak positive result is that it is possible to approximate
the content of a suitably presented convex corner in deterministic
polynomial time, up to an exponential factor. This follows from the
fact, noted by Kahn and Kim~\cite{KaKi} that $V(S)$, the volume of the
largest cuboid inside $S$, can be determined to within a factor of
$(1+\eps)$ in deterministic polynomial time, using the ellipsoid
algorithm.  They concluded from this that the volume of a convex
corner can be approximated within a factor $e^n$ in deterministic
polynomial time (this is known {\em not} to be true for a general
convex body -- see B\'ar\'any and F\"uredi~\cite{BaFu}), and the same
evidently holds for the content.

One open problem in this direction is to decide whether or not
$\mu(S)$ can be approximated to within any factor $(1+\eps)$ in
{\em randomized} polynomial time.  Dyer, Frieze and Kannan~\cite{DFK}
showed that the volume can be so approximated, even in more general
circumstances. 

\subsection{Other inequalities} \label{later}

Let $S$ be a convex corner in $\Rnp$.  We know from the proof of
Theorem~\ref{2.2} that 
$$ 
\Vol (S) \ge \sum _{i=1}^n y_i \Vol(S_i) 
$$
for every $\by\in S$. This means that the vector $\bz$ defined by 
$z_i = \Vol(S_i) / n \Vol (S)$ is in $S^\circ$.  So we have 
$$
\sum_{i=1}^n z_i \frac{\Vol (S)}{\Vol (S_i)} = 1.
$$ 
A consequence of this is that there is an extreme point $\bw$ of
$S^\circ$ such that 
$$
\sum _{i=1}^n w_i \frac{\Vol (S)}{\Vol (S_i)} \ge 1.
$$ 
If $S^\circ$ is a polytope, whose vertices we know, then this simple
result will have an interpretation. In particular we have the
following.

\begin{theorem} \label{7.1}
Let $G$ be a perfect graph. Then there is a clique $C$ in $G$ such that
$$
\sum _{x\in C} \frac{\Vol (\Stab (G))}{\Vol (\Stab (G-x))} \ge 1.
$$
\end{theorem}

\begin{proof}
Apply the preceding inequality to $\Stab(G)$. 
\end{proof} 

\begin{theorem} \label{7.2}
For every partial order $P$, there is a chain $C$ in $P$ with
$$
\sum _{x\in C} \frac{e(P)}{e(P-x)} \ge |P|.
$$
\end{theorem}

\begin{proof} 
Apply Theorem~\ref{7.1} to the comparability graph of $P$. 
\end{proof} 

Theorem~\ref{7.2} follows (in much the same way) from results of
Sidorenko~\cite{Sid}, and seems to us to be an attractive ``dual'' to
Theorem~\ref{4.7}.

\medskip

Changing tack somewhat, let us give one more generalization of
Saint-Raymond's Inequality.  Suppose that $S$ is a convex corner in
$\Rnp$, and that the natural number $r$ is such that $S^r$, the
pointwise product of $r$ copies of $S$, is convex.  Thus, by 
Theorem~\ref{6.6p}, with $A_1 = \dots = A_r = S$ and $C= S^r$, we have 
$$
(\Vol (S^\circ)) ^r \ge \frac{1}{n!^r \Vol (S^r)}.
$$
Rearranging gives the following result.

\begin{theorem} \label{7.3}
Suppose that $S$ is a convex corner in $\Rnp$, and that $r$ is a
natural number such that $S^r$ is convex. Then 
$$
\Vol (S) \Vol (S^\circ) \ge 
\frac{\Vol (S)}{(\Vol (S^r))^{1/r}} \frac{1}{n!}.
$$
\qed
\end{theorem}

A consequence of Corollary~13 of Bollob\'as and Leader~\cite{BoLe} is
that $\Vol (S) \ge (\Vol (S^r))^{1/r}$, so this is (at least in some
cases) a stronger form of Saint-Raymond's Inequality.

\subsection{Open problems} \label{problems}

We expect that there is much more to be discovered by following the
themes of this paper.  Here are just some of the problems that we have
encountered that seem to us to be worth further study.

\begin{problem} \label{Prob1}
Find better bounds for the constant 
$\displaystyle
{\phi = \sup_S \left( \frac{n!\Vol(S)}{\mu(S)} \right)^{1/n}}$ 
defined in \S\ref{lbc}. 
\end{problem}

A related problem is the following.

\begin{problem} \label{Prob2}
Is there a positive $\eps$ such that, for every $n$ and
every convex corner $S$ in $\Rnp$, there is a point $\bx$ in $S$ such
that 
$$
\Vol (S) \le \frac{1}{n\eps} \sum _i x_i \Vol (S_i)?
$$
In other words, is there always a point $\bx\in S$ such that
the union of the cones $\conv(\bx, S_i)$ contains a positive
proportion of the volume? 
\end{problem}

The example of $T^n_{n/2}$ shows that we cannot have $\eps > 1/2$ in
the above. If one could find such an $\eps$, then it would follow
immediately that $\mu(S) \ge \eps^n n! \Vol (S)$ for every convex
corner $S$ in $\Rnp$, i.e., that $\phi < 1/\eps$.

\begin{problem} \label{Prob3}
Find better bounds for the constant 
$$
\eta = \sup_S \left( \frac{\mu(S) \mu(S^\circ)}{n!} \right) ^{1/n}
$$ 
defined in \S\ref{sec:Polar}.  In particular, is it true that 
$\eta < \pi/2$? 
\end{problem}

One possible approach to this would be to show that polytopes with a
limited number of vertices are not close to being extremal examples in
Santal\'o's Inequality.  More precisely, the answer to the next
problem is surely yes. 

\begin{problem} \label{Prob3.5}
Is it true that, for every constant $c$, there is a positive $\eps$
such that, whenever $S$ is a polytope in $\Rnp$ with at most $c^n$ 
vertices, 
$$
\Vol(S) \Vol(S^\circ) \le (1-\eps)^n (\Vol(B_2^n))^2?
$$
\end{problem}

The next problem is probably rather less innocent than it first
appears.  The result of Meyer~\cite{Mey} and Reisner~\cite{Rei}
characterizing the cases of equality in Saint-Raymond's Theorem can be
viewed as saying that, after scaling, the convex corners $S$ such that
both $S$ and $S^\circ$ are skew-cubes, and $S$ is $\mu$-minimal, are
exactly the stable-set polytopes of cographs, i.e., those polytopes
that can be formed from 1-dimensional convex corners by $\ell_1$- and
$\ell_\infty$-sums.  It seems that we may not get a much larger class
of extremal examples if we demand only that $S$ is $\mu$-minimal and
{\em one} of $S$ and $S^\circ$ (say $S^\circ$) is a skew-cube.  This
is, by the definitions, what the next problem amounts to. 

\begin{problem} \label{Prob5}
Determine the class of convex corners $S$ such that 
\begin{equation} 
\mu(S) = 1/\Vol (S^\circ). \tag{$*$}
\end{equation}
\end{problem}

As we noted earlier, Theorem~\ref{6.11} implies that any $S$ satisfying
($*$) is, after re-scaling, a 0-1 convex corner. There
are also a number of other conclusions that can be drawn about $S$
from various results in this paper.  We describe all the convex
corners we know that satisfy ($*$).  Notice that all the
convex corners $T_t^n$ are $\mu$-minimal, and their polars are
skew-cubes by Theorem~\ref{5.1}.  The examples below include the
$T_t^n$ as a special case. 

Let $U(t,m,r)$ be the set system on ground-set $M$, the disjoint union
of $r$ sets $M_1, \dots, M_r$, each of size $m$, with $X\in U(t,m,r)$
unless $X$ contains $t$ of the $M_i$. Now define the convex corner
$S(t,m,r)$ to be the convex hull of the vectors $\be_X$, for 
$X\in U(t,m,r)$. One can check that $S(t,m,r)$ satisfies ($*$)
for all $t$, $m$ and $r$.  

It is easy enough to check that, if $S$ and $T$ both satisfy
($*$), then so do both the $\ell_1$- and $\ell_\infty$-sums of
$S$ and $T$.  Indeed, we suspect that all convex corners satisfying
($*$) can be constructed from convex corners of the form
$S(t,m,r)$ by repeated $\ell_1$- and $\ell_\infty$-sums.

Some other problems concerning pointwise products occurred to us,
motivated at least partly by the special cases where the convex
corners concerned are stable set polytopes of (perfect) graphs. We
state two of these, although we have not investigated them at all
thoroughly.

\begin{problem} \label{Prob4}
Is it true that, for all convex corners $A$, $B$ and $C$ in $\Rnp$
with $A\circ B \subseteq C$, we have 
$\Vol (A) \le n! \Vol (B^\circ) \Vol (C)$?  Equivalently, if 
$S\circ T \circ U \subseteq B_1^n$, does it follow that 
$\Vol (S) \le n! \Vol (T^\circ) \Vol (U^\circ)$?
\end{problem}

This would be the analogue of Theorem~\ref{6.3} (and
Theorem~\ref{6.4}(a)), with content replaced by $n!$ times volume
everywhere. It would of course be yet another extension of
Saint-Raymond's Inequality.  It can be shown that this would imply the
perhaps even more attractive inequality below. 

\begin{problem} \label{Prob7} 
Suppose that $S$, $T$ and $U$ are convex corners in $\Rnp$ satisfying
$S\circ T \supset U\circ B_1^n$. Does it follow that 
$$
\Vol(S) \Vol(T) \ge \Vol (U) \Vol (B_1^n) = \frac{1}{n!} \Vol (U)?
$$ 
\end{problem}


\begin{thebibliography}{99}

\bibitem{BaFu}
I.B\'ar\'any and Z.F\"uredi, Computing the volume is difficult, 
{\it Disc.\ and Comp.\ Geom. \bf 2} (1987) 319--326.

\bibitem{BeDu} 
C.Berge and P.Duchet, Strongly perfect graphs, in {\it Topics
on Perfect Graphs} (C.Berge and V.Chv\'atal eds.), North Holland, Amsterdam,
1984, 57--61. 

\bibitem{BBS} 
B.Bollob\'as, G.Brightwell and A.Sidorenko, Geometrical
techniques for estimating numbers of linear extensions, submitted. 

\bibitem{BoLe0}
B.Bollob\'as and I.Leader,
Generalized duals of unconditional spaces and Lozanovskii's
theorem, Comptes Rendus de l'Acad\'emie des Sciences, Paris, 
S\'erie~I, t.~{\bf 317} (1993) 583--588.

\bibitem{BoLe} 
B.Bollob\'as and I.Leader, Products of unconditional bodies,
{\it Operator Theory: Advances and Applications \bf 77} (1995) 13--24. 

\bibitem{BLR} 
B.Bollob\'as, I.Leader and A.J.Radcliffe, Reverse Kleitman 
Inequalities, {\it Proc.\ London Math.\ Soc.\ (3) \bf 58} (1989) 153--168. 

\bibitem{Bri} 
G.Brightwell, Random $k$-dimensional orders: width and number of
linear extensions, {\it Order \bf 9} (1992) 333--342. 

\bibitem{BrWi} 
G.Brightwell and P.Winkler, Counting linear extensions,
{\it Order \bf 8} (1991) 225--242. 

\bibitem{Chv} 
V.Chv\'atal, Perfectly ordered graphs, in {\it Topics on
Perfect Graphs} (C.Berge and V.Chv\'atal eds.), North Holland, Amsterdam,
1984, 57--61. 

\bibitem{CKLMS} 
I.Csisz\'ar, J.K\"orner, L.Lov\'asz, K.Marton and G.Simonyi,
Entropy splitting for antiblocking corners and perfect graphs, 
{\it Combinatorica \bf 10} (1990) 27--40. 

\bibitem{DFK}
M.Dyer, A.Frieze and R.Kannan, A randomly polynomial time algorithm
for estimating volumes of convex bodies, {\it Proc.\ 21st ACM
Symposium on the Theory of Computing} (1989) 375--381. 

\bibitem{GLS} 
M.Gr\"otschel, L.Lov\'asz and A.Schrijver, {\it Geometric 
Algorithms and Combinatorial Optimisation}, Springer (1988). 

\bibitem{Hoa} 
C.T.Ho\`ang, Efficient algorithms for minimum weighted colouring of
some classes of perfect graphs, {\it Disc.\ Appl.\ Math. \bf 55}
(1994) 133--143. 

\bibitem{HMP} 
C.T.Ho\`ang, F.Maffray and M.Preissmann, New properties of
perfectly orderable graphs and strongly perfect graphs, {\it Discrete Math.
\bf 98} (1991) 161--174. 

\bibitem{KaKi} 
J.Kahn and J.Kim, Entropy and sorting, {\it J.\ Comp.\ Sys.\ Sci. \bf
51} (1995) 390--399. 

\bibitem{LiTz} 
J.Lindenstrauss and L.Tzafriri, {\it Classical Banach Spaces I and
II}, Springer, 1996.  (Originally published as two separate volumes
in 1977 and 1979.)  

\bibitem{Lov} L.Lov\'asz, Normal hypergraphs and the perfect graph conjecture,
{\it Discrete Math. \bf 2} (1972) 253--267. 

\bibitem{Loz} 
G.Ya.Lozanovskii, On some Banach lattices (translated from 
Russian), {\it Siberian Math.\ J. \bf 10} (1969) 419--430.

\bibitem{Mah} 
K.Mahler, Ein \"Ubertragungsprinzip f\"ur konvexe K\"orper,
{\it Casopis Pest.\ Mat.\ Fys. \bf 68} (1939) 93--102.

\bibitem{Mey} 
M.Meyer, Une caract\'erisation volumique de certains espaces
norm\'es de dimension finie, {\it Israel J.\ Math. \bf 55} (1986) 317--327.

\bibitem{MePa}
M.Meyer and A.Pajor, On Santal\'o's inequality, in {\it Geometric
Aspects of Functional Analysis} (J.Lindenstrauss and V.D.Milman eds.),
Springer Lecture Notes in Mathematics {\bf 1376}, 1985, pp261--263. 

\bibitem{Rei} 
S.Reisner, Minimal volume-product in Banach spaces with a 
1-unconditional basis, {\it J.\ London Math.\ Soc.\ (2) \bf 36} (1987) 126--136.

\bibitem{StR} 
J.Saint-Raymond, Sur le volume de corps convexes sym\'etriques,
{\it Seminaire d'Initiation \`a l'Analyse}, 20e anne\'e (1980/81) No.~11, 25pp.

\bibitem{San} 
L.A.Santal\'o, Un invariante afin para los cuerpos convexos
del espacio de $n$ dimensiones, {\it Portugal.\ Math. \bf 8} (1949) 155--161. 

\bibitem{Sid} 
A.Sidorenko, Inequalities for the number of linear extensions 
of a partial order, {\it Order \bf 8} (1991) 331--340.

\bibitem{Sta} 
R.Stanley, Two poset polytopes, {\it Disc.\ Comp.\ Geom. \bf 1}
(1986) 9--23. 

\bibitem{Toft} 
B.Toft, Colouring, stable sets and perfect graphs, in {\it Handbook
of Combinatorics Vol~1} (R.L.Graham, M.Gr\"otschel, L.Lov\'asz eds.),
Elsevier Science (1995) 233--288. 

\end{thebibliography}

\end{document}





