**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 *T _{f}* of so-called

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 *F _{f}*

Suppose that a monotone Boolean function satisfies the condition:

**(C)**
there exists a polynomial function *p* such that *p*( | *T _{f }*|
)

In
other words, the number *T _{f}* of minimal true sets grows at
least as a polynomial function of the number

A set *X* of points in the plane is called ** convex**
if for every two points

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

·
A *z*-containing set *X* is ** minimal in
S** if

·
*X* is a ** z-avoiding set** if

·
A *z*-avoiding set *X* is ** maximal in S**
if there is no

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 *f _{S }*.

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 *f _{S}* satisfies condition

In the case when *d* = 2, i.e. for the plane, we proved
the following:

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*(

Theorem 2 implies *| A*(* S *)* | _{} *2