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

Main article: oriented matroid

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}$.

Arrangement graphs

Not to be confused with graphs defined on permutations, known as arrangement graphs.

A pseudoline arrangement graph is the graph induced by a simple pseudoline arrangement, where vertices correspond to intersection points and edges connect vertices that are adjacent along some pseudoline. Line arrangement graphs are defined analogously for line arrangements.^[16]

Pseudoline arrangement graphs can be recognized in linear time by an algorithm that exploits their structural properties.^[17] They are 2-vertex-connected and become 3-connected when augmented with a vertex adjacent to all degree-2 and degree-3 vertices, which gives them a unique planar embedding (the "canonical embedding"). In contrast, recognizing line arrangement graphs is ∃${\displaystyle \mathbb {R} }$-complete (and hence NP-hard) because it requires verifying geometric realizability with straight lines (determining stretchability).^[16][10]

These graphs have several other notable combinatorial properties:^[18][19]

• They are 4-edge-colorable and 3-vertex-colorable
• The diameter on ${\displaystyle n}$ pseudolines is exactly ${\displaystyle n-2}$, independent of structure
• A vertex is diametrical if and only if it lies on the outer face
• Their degree sequences are completely characterized: realizable sequences have the form ${\displaystyle \langle 4^{d_{4}},3^{d_{3}},2^{d_{2}}\rangle }$ with ${\displaystyle 3\leq d_{2}\leq n}$, ${\displaystyle d_{3}=2(n-d_{2})}$, and ${\displaystyle d_{4}=n(n-5)/2+d_{2}}$; when ${\displaystyle d_{2}=n}$, then ${\displaystyle n}$ must be odd
• Not all are Hamiltonian,^[16] though spherical arrangement graphs always are^[18]

Every ${\displaystyle n}$-vertex pseudoline arrangement graph can be drawn in linear time in a grid of area ${\displaystyle O(n^{7/6})}$.^[17] The width depends on the maximum k-level complexity of pseudoline arrangements, a major open problem in discrete geometry. These graphs also admit universal point sets of size ${\displaystyle O(n\log n)}$, much smaller than the quadratic bound for general planar graphs.^[17] Drawing arrangement graphs is the main task in the Planarity puzzle.^[17]

Kobon triangle problem

An arrangement of 19 lines forming the highest possible number of triangles (107)

Main article: 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 ${\displaystyle 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][20]

See also

• Arrangement of lines
• Oriented matroid
• Coxeter group

External links

• Dr. Lukas Finschi, "Homepage of Oriented Matroids"
• Handbook of Discrete and Computational Geometry