Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-98-15 June 1998

Abstract

A convex corner is a compact convex down-set of full dimension in  R₊ⁿ.  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 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 content  mu(S)  of a convex corner  S  in  R₊ⁿ  recursively by

As part of his proof of Saint-Raymond's Inequality -  Vol(S)Vol(S^o) >= 1/n!  - Meyer effectively showed that  mu(S) <= n! Vol(S)  for any convex corner  S.  Sidorenko 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, 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^o) >= n!  for any convex corner  S  and its polar  S^o.  We extend this result by working with the pointwise product of convex corners. The pointwise product of two sets  A  and  B  is  A o B = { x o y : x in A, y in B },  where   (x o y)_i = x_i y_i.  We show that, if  A, B and  C  are convex corners such that the pointwise product  A o B  is contained in  C,  then we have  mu(A) <= mu(B^o ) mu(C).  This leads to the following generalization of Saint-Raymond's Inequality: if  A₁, ..., A_r  are any bounded sets in  R₊ⁿ,  such that  A₁ o ... o A_r  is contained in the  l₁  unit ball, then  mu(A₁^o) ... mu(A_r^o) >= n!  and so  Vol(A₁^o) ... Vol(A_r^o) >= (n!)^-r+1.

We prove various other results concerning content and volume of convex corners, and give counterexamples to two conjectures of Bollobás and Leader  about pointwise products. We conclude with a number of open problems.

A compressed (gzip) PostScript file (163 kB) with the full contents of this report can be downloaded by clicking here.
The LaTeX file (118 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you like a free hard copy of this report, please send the number of this report, LSE-CDAM-98-15, together with your name and postal address to:

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-171-955 7732. Fax: +44(0)-171-955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html