Graph Theory » Topological G.T. » Drawings

Linear Hypergraphs with Dimension 3 ★★

Author(s): de Fraysseix; Ossona de Mendez; Rosenstiehl

Conjecture   Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.

Keywords: Hypergraphs

Posted by taxipom
updated September 26th, 2007
add new comment

Editorial policy

To ensure that the Garden is a high quality resource, we reserve the right to move submitted open problems to an alternate location on our site. These Second tier problems can be found by clicking the More link in the Navigate menu. When considering submissions, we take into account the value of the question, its relevance, and clarity of the exposition. Still, some of these Second tier problems can be an interesting exercise, or a worthy (but inadequately presented) question. Our editors (called greenthumbs) are listed below.

    Greenthumbs
  • Matt DeVos
  • Robert Samal
Geometry

Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

Let $ S $ be a set of points in the plane. Two points $ v $ and $ w $ in $ S $ are visible with respect to $ S $ if the line segment between $ v $ and $ w $ contains no other point in $ S $.

Conjecture   For all integers $ k,\ell\geq2 $ there is an integer $ n $ such that every set of at least $ n $ points in the plane contains at least $ \ell $ collinear points or $ k $ pairwise visible points.

Keywords: Discrete Geometry; Geometric Ramsey Theory

Posted by David Wood
updated September 25th, 2012
1 comment