Enumeration and Classification of Triangle-Maximal Pseudoline Arrangements

Abstract

We describe algorithms for the exhaustive enumeration and classification of simple arrangements of $n$ pseudolines ($n$ odd) maximizing the number of triangular faces. The depth-first search enumerates reduced words for the longest permutation $w_0$ by branching only on the even-indexed generators, using pruning constraints imposed by the geometry of optimal arrangements. The approach handles both perfect arrangements with a regular triangular pattern and unavoidable deviations from it for $n\equiv 1(\mathrm{mod}6)$. The output is classified into a hierarchy of equivalence classes: by commutation, by Euclidean transformations, and by projective transformations. For each projective class we recover its full symmetry group $G\subseteq S_{n+1}$ together with the orbit-stabilizer profile of its Euclidean subclasses. Completeness of the search and classification is proved: every wiring diagram is reached. We report full enumerations; e.g. for $n=27$, 85,562,064 wiring diagrams partitioned into 56,646 projective classes. For larger $n$ (up to $n=93$), where exhaustive enumeration is out of reach, we report partial (first-hit) results.

58 pages, 17 figures, 7 tables. Code and data: https://github.com/parpalak/pseudoline-algorithms