DIMACS REU
Summer 2001
ON
CONVEX POLYTOPES IN THE PLANE “CONTAINING” AND “AVOIDING” ZERO
Authors:
Ricardo Collado University of Puerto Rico, Puerto Rico
Alexander Kelmans Rutgers University and University of Puerto Rico
Daniel Krasner University of California at Berkeley, California
Advisors:
Endre Boros Rutgers University, New Jersey
Vladimir Gurvich Rutgers University, New Jersey
Alexander Kelmans Rutgers University and University of Puerto Rico
The main motivation for considering our problem is the study
of monotone Boolean functions. It is
known and easy to show that a monotone Boolean function f is uniquely
defined by the family Tf of so-called minimal true sets
as well as by the family Ff of so-called maximal false
sets of variables of the function.
One natural problem is to generate “efficiently” all minimal true sets
(the elements of Tf ) or all maximal false sets ( the elements of Ff ) or
both (the elements of Ff
Tf ).
Due to Gurvich and Khachiyan (1995) and Fredman and Khachiyan
(1996) there exists a quasi-polynomial “time” algorithm to generate
incrementally all minimal true and maximal false sets of a monotone Boolean
function, i.e. the elements of Ff 
Tf
. It is not known
whether or not there exists a polynomial or quasi-polynomial time algorithm to
generate the elements Tf
(the same is true for Ff ).
Suppose that a monotone Boolean function satisfies the condition:
(C)
there exists a polynomial function p such that p( | Tf |
) 
| Ff |.
In other words, the number Tf of minimal true sets grows at least as a polynomial function of the number Tf of maximal false sets. Then the above mentioned algorithm allows also to generate all minimal true sets (the elements Tf ) in quasi-polynomial time. For that reason it is interesting to describe some natural classes of monotone Boolean functions satisfying condition (C).
A set X of points in the plane is called convex if for every two points a, b in X the set of all points on the line segment, joining a and b, belongs to X. Let S be a nonempty finite set of points in the plane. The convex hull of S is a convex set H containing S and minimal by inclusion (i.e. H has no proper convex subset containing S). The notions of a convex set and the convex hull of a set is defined similarly for a space of any given dimension.
Let S be a finite set of points in the plane, X
S, and z
be a point not in S.
· X is a z-containing set if z is in the interior of the convex hull of X.
· A z-containing set X is minimal in S if X has no proper z-containing subset.
· X is a z-avoiding set if z is not contained in the interior of the convex hull of X.
· A z-avoiding set X is maximal in S if there is no z-avoiding set containing X properly.
Let C( S ) and A( S ) denote the sets of minimal z-containing and maximal z-avoiding subsets of S, respectively. The families C( S ) and A( S ) can be interpreted as the families of minimal true sets and maximal false sets, respectively, of some monotone Boolean function fS .
E. Boros and V. Gurvich raised the following question:
Is it true that | A( S ) | 
2 d | C( S ) | where d is the dimension of the
space? If the above inequality holds
then the function fS satisfies condition (C).
In the case when d = 2, i.e. for the plane, we proved the following:
Theorem 1. Let S be a finite set of
points in the plane and z be a point not in S.
Suppose that z is in the interior of the convex hull of S.
Then
| A( S ) | 
3 | C( S ) | + 1
and the equality holds if and only if |
S | = 4, the convex hull of S is a quadrilateral Q, and z is the point of intersection of the two
diagonals of Q.
Using a different approach, A. Kelmans and A. Rubinov proved the following more general result.
Theorem
2 (A. Kelmans, A. Rubinov). Let S
be a finite set of points in the d-dimensional space and z be a point that
belongs to no hyperplane containing at least two points from S. Suppose that z is in the interior of the
convex hull of S. Then | A( S )
| 
d | C( S ) | + 1 and the
equality holds if and only if | S | = d + 1 and the convex hull of S is a (d+1)-dimensional simplex.
Theorem 2 implies | A( S ) | 
2 d | C( S ) |,
giving a positive answer to the question raised by E. Boros and V. Gurvich for
points in general position.