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

dankras@yahoo.com

Endre Boros                           Rutgers University, New Jersey

Vladimir Gurvich                    Rutgers University, New Jersey

Alexander Kelmans               Rutgers University and University of Puerto Rico

kelmans@rutcor.rutgers.edu

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:

# 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.