Linear Hypergraphs with Dimension 3

Definitions and mathematical statement

Let $H=(V,\mathcal E)$ be a finite simple hypergraph: its edges are distinct nonempty subsets of $V$, no edge contains another, and every vertex belongs to an edge. It is linear when distinct edges have at most one common vertex. Its incidence poset has underlying set the disjoint union $V\sqcup\mathcal E$, with strict comparisons precisely $v<e$ when $v\in e$.

A linear extension is a total order respecting every comparison of this poset. The order dimension is the least number of linear extensions whose common comparisons are exactly those of the poset. Thus dimension at most three means that three total orders suffice, allowing repeated orders when fewer would suffice.

An intersection representation assigns a nonempty closed convex set $K_v\subseteq\mathbb R^2$ to each vertex, where every $K_v$ is either a filled nondegenerate triangle or a closed straight segment. Its intersection hypergraph has as edges precisely the inclusion-maximal subsets $X\subseteq V$ for which $\bigcap_{v\in X}K_v\ne\varnothing$.

The conjecture states that every linear hypergraph whose incidence poset has dimension at most three has such a representation by triangles and segments. Objects represent vertices; a common intersection represents a hyperedge, possibly involving more than two objects. This is different from merely representing the pairwise intersection graph, since pairwise intersections do not automatically give one common point. The simplicity convention is necessary for an intersection hypergraph defined by maximal intersecting subsets; redundant contained edges are not separate edges of that object.

Short English statement

Can every simple linear hypergraph of incidence-poset dimension at most three be represented by common intersections of planar triangles and segments?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3326 (OPG-596), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Linear Hypergraphs with Dimension 3. Original problem and discussion. http://www.openproblemgarden.org/op/linear_hypergraphs_with_dimension_3.
• S3 H. de Fraysseix, P. Ossona de Mendez and P. Rosenstiehl, Representation of Planar Hypergraphs by Contacts of Triangles, Graph Drawing 2007. https://doi.org/10.1007/978-3-540-77537-9_15.