Arrangement of pseudolines

An arrangement of pseudolines is a family of curves that share similar topological properties with a line arrangement.^[2][3] Most commonly, in the study of arrangements of lines, these have the simple property that each crosses every other line exactly once. These can be defined in the projective plane as simple closed curves any two of which meet in a single crossing point.^[2][4] Furthermore, in a simple (or uniform^[5]) arrangement, along with all lines being required to cross all others, no 3 pseudolines may cross at the same point.

Wiring diagram for an arrangement of pseudolines

Pseudoline arrangement constructed by Friedrich Levi which cannot be straightened due to its violation of the theorem of Pappus^[1]

Every arrangement of finitely many pseudolines can be extended so that they become lines in a "spread", a type of non-Euclidean incidence geometry in which every two points of a topological plane are connected by a unique line (as in the Euclidean plane) but in which other axioms of Euclidean geometry may not apply.^[6]

A common diagram used to represent an arrangement is the wiring diagram, a series of parallel lines with crossings between them drawn as an "X" in a simple crossing.^[1] When drawn this way, they can be described with notation for either the order in which each line crosses the other, the state of the orders between each crossing (or allowed groups of crossing whose orders do not matter), or as a list of pairs, each pair being the labels of 2 lines which have crossed, ordered in a given direction (usually left to right). They draw similarities to braids, although without any need to keep track of which crosses atop the other, the crossings may be seen as elements of the Coxeter group.

Two arrangements are said to be "related by a triangle-flip" if one of them can be transformed into the other by changing the orientation of a single triangular face, or in other words, by moving one of the three pseudolines that form the triangle across the intersection of the other two. For any two simple wiring diagrams numbered 1 through n in order, one can be transformed into the other with a sequence of these triangle-flips (and vice versa). This fact has counterparts in the terminology of mutations on oriented matroids and Coxeter relations for reduced decomposition.^[1]

Felsner and Valtr proved in 2009 that for an arrangement of ${\displaystyle n}$ pseudolines, there are at most ${\displaystyle 2^{0.657n^{2}}}$ simple arrangements. This improves upon the previous bounds of ${\displaystyle 2^{0.792n^{2}}}$ in 1992 and ${\displaystyle 2^{0.697n^{2}}}$ in 1997. ^[7] They also proved a lower bound of ${\displaystyle 2^{0.1887n^{2}}}$, which was improved in 2024 by Kühnast et al. to ${\displaystyle 2^{0.2721n^{2}}}$ for sufficiently large ${\displaystyle n}$.^[8] The number of simple arrangements of n pseudolines in the projective plane with a marked cell is known up to n=13:

1, 1, 1, 2, 3, 16, 135, 3315, 158830, 14320182, 2343203071, 691470685682, 366477801792538 (sequence A006247 in the OEIS)

The growth rate for the number of line arrangements is smaller compared to that of pseudoline arrangements; while for pseudolines ${\displaystyle A_{n}=2^{\Theta (n^{2})}}$, for lines, ${\displaystyle A_{n}=2^{\Theta (n\log n)}}$.^[8][9]

Stretchability

Non-approaching (top) vs. approaching (bottom) pseudoline arrangements

A pseudoline arrangement is said to be stretchable if it is combinatorially equivalent to a line arrangement, meaning that you can straighten each one while maintaining the order in which each crosses each other. Notable arrangements of pseudolines which cannot be stretched include the arrangement of 9 pseudolines constructed by Friedrich Levi which violates the theorem of Pappus, and a 10 pseudoline arrangement constructed to violate Desargues's theorem.^[1] Some symmetric pseudoline arrangements are stretchable, yet cannot be stretched into a symmetric line arrangement.^[5]

Stretchability is the problem of deciding for a given pseudoline arrangement if it is equivalent to a line arrangement, and simple stretchability is the same problem but for simple arrangements.^[10] Determining stretchability is a difficult computational task: it is complete for the existential theory of the reals to distinguish stretchable arrangements from non-stretchable ones,^[5][10] while determining simple stretchability is NP-hard.^[10] Algorithms do exist for stretchability, such as Bokowski’s rubber-band method,^[11] the final polynomial method,^[12][13] the solvability sequence method, and the inequality reduction method.^[1][14] These take advantage of the fact that the problem of stretchability is equivalent to the problem of the realization of a rank-3 oriented matroid.

An arrangement of approaching pseudolines is an arrangement of pseudolines where each pair of pseudolines approach each other until they cross, and then they move away from each other. There are arrangements of pseudolines that are not realizable with approaching pseudolines, and these are thus not stretchable in general. However, not all approaching arrangements can be stretched.^[9] Any such approaching arrangement can be transformed into any other by a series of triangle flips. In other words, approaching arrangements have a connected flip graph.

Oriented matroids

The top arrangement has ${\displaystyle \sigma (a,b,c)=+}$, and the bottom ${\displaystyle \sigma (a,b,c)=-}$

Each rank-3 oriented matroid is equivalent to an arrangement of pseudolines, and each oriented matroid which is also uniform (in which the independent sets are exactly the sets containing at most r elements, for some fixed integer r) is equivalent to a simple pseudoline arrangement. Tools for dealing with one form can therefore be used to analyze its equivalent form for either study.^[1]

The 3-signotope or chirotope ${\displaystyle \sigma }$ which corresponds to a given pseudoline arrangement is defined as follows: the sign of ${\displaystyle \sigma (a,b,c)}$ for ${\displaystyle a<b<c}$ describes the orientation of the triangle formed by 3 pseudolines ${\displaystyle a}$, ${\displaystyle b}$, and ${\displaystyle c}$. If ${\displaystyle a}$ and ${\displaystyle c}$ cross below ${\displaystyle b}$, then ${\displaystyle \sigma (a,b,c)=+}$. If ${\displaystyle a}$ and ${\displaystyle c}$ cross above ${\displaystyle b}$, then ${\displaystyle \sigma (a,b,c)=-}$.^[15] Equivalently, if ${\displaystyle a}$ crosses ${\displaystyle b}$ before ${\displaystyle c}$, then ${\displaystyle \sigma (a,b,c)=+}$, and if ${\displaystyle a}$ crosses ${\displaystyle b}$ after ${\displaystyle c}$, then ${\displaystyle \sigma (a,b,c)=-}$, assuming each pseudoline is given a direction (such as the implicit direction of each pseudoline in a wiring diagram, with each directed from left to right). If all 3 lines cross at the same point, then ${\displaystyle \sigma (a,b,c)=0}$.

Kobon triangle problem

The Kobon triangle problem is an unsolved problem in combinatorial geometry first stated by Kobon Fujimura (1903-1983). The problem asks for the largest number N(k) of nonoverlapping triangles whose sides lie on an arrangement of k lines.

The line arrangement problem is often broken down into two parts: the equivalent problem but with pseudoline arrangements, and the problem of the stretchability of the arrangements that have an optimal triangle count. This allows pure combinatorics and group theory to be leveraged without needing to worry about violating rules like the theorem of Pappus or Desargues's theorem.^[1][16]