The Plank Problem from the Viewpoint of Hypergraph Matchings and
Covers
Ron Holzman
MIT
September 15,
4:15pm
refreshments at 3:45pm
2338
ABSTRACT

The "plank problem", open since 1950, is the following
conjecture. Suppose that the convex set K is contained in the unit cube of
R^n, and meets all of the cube's facets. Suppose further that a collection
of planks is given (where "plank" means a strip determined by two parallel
hyperplanes orthogonal to one of the axes), and the union of these planks
covers K. Then the sum of the planks' widths must be at least 1.
We propose an analogy between this problem and familiar concepts from the
theory of hypergraphs. This leads to a proof of the conjecture in certain
special cases, and to a formulation of a fractional counterpart of the
conjecture, which we are able to verify to within a factor of 2.
This is joint work with Ron Aharoni, Michael Krivelevich and Roy Meshulam.

Speaker's Contact Info: holzman(atsign)math.mit.edu
Return to seminar home page
Page loaded on August 31, 1999 at 02:04 PM.

Copyright © 199899, Sara C. Billey.
All rights reserved.

