The Plank Problem from the Viewpoint of Hypergraph Matchings and Covers

Ron Holzman

MIT

September 15,
4:15pm
refreshments at 3:45pm
2-338

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(at-sign)math.mit.edu


Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on August 31, 1999 at 02:04 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.