The Forbidden Simplex: Maximal Edge Density of Planar Hasse Diagrams

We establish a tight upper bound on the number of edges in thecover graph of a finite partially ordered set whose Hasse diagramis planar.The transitive reduction that defines the Hasse diagram forcesevery such graph to be triangle-free, yielding the clique boundω(H) ≤ 2.Combining this constraint with Euler's formula for planar graphs,we prove that every planar Hasse diagram on n ≥ 3 verticessatisfies |E| ≤ 2n - 4.We then show that this bound is tight: for every n ≥ 4, thecomplete bipartite graph K2, n-2 is realizable as a planarHasse diagram and achieves $|E| = 2n - 4$ exactly.Moreover, we prove that K2, n-2 is the unique extremalstructure among planar Hasse diagrams of height~2, and that nosimplicial complex of dimension ≥ 2 (triangle, tetrahedron,or higher simplex) can appear as a subgraph of any Hasse diagram.This ``forbidden simplex'' property distinguishes Hasse diagramsfrom the simplicial meshes that arise in computational geometry,finite element methods, and other discrete geometric settings.