Linear Hypergraphs with Dimension 3

Discussion

A hypergraph is linear if any two edges may share at most one vertex. The incidence poset of a hypergraph is the vertex-edge inclusion poset. The dimension of a poset $ P $ is the minimum number of linear extentions of $ P $ , whose intersection is $ P $ [DM]. Schnyder proved that the incidence poset of a graph $ G $ has dimension at most $ 3 $ if and only if $ G $ is planar [S89]. Fraysseix, Rosenstiehl and Ossona de Mendez proved that every planar graph has a representation by contacts of triangles [FOR94] and Scheinerman conjectured that every planar graph has a representation by intersection of segments [S84] (claimed to be proved by Gonçalves et al.). A hypergraph is planar if its vertex-edge incidence graph is planar [W]. Fraysseix, Rosenstiehl and Ossona de Mendez proved that every planar linear hypergraph has a representation by contacts of triangles [FOR07] and it has been conjectured that they have a representation by intersection of straight line segments [FO07] (cf Straight line representation of planar linear hypergraphs ). Although the incidence poset of a simple planar hypergraph has dimension at most $ 3 $ (what follows from [BT]), the converse is false: The linear hypergraph with vertices $ 1,\dots,5 $ and edge set $ \{\{1,2\},\{2,3\},\{3,4\},\{1,4\},\{1,3,5\},\{2,4,5\}\} $ has incidence dimension $ 3 $ but is not planar (its vertex-edge incidence graph is a subdivision of $ K_{3,3} $ ). It follows from [O] that the vertices of simple hypergraphs with incidence posets of dimensions $ d $ can be represented by convex sets of the Euclidean space of dimension $ d-1 $ , in such a way that the edges of the hypergraph are exactly the maximal subsets of vertices, such that the corresponding subset of convexes has a non-empty intersection.