Papers › Improved Lower Bound on the Number of Pseudoline Arrangements
Improved Lower Bound on the Number of Pseudoline Arrangements
Justin Dallant
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We show that for large enough n, the number of non-isomorphic pseudoline arrangements of order n is greater than 2^(c·n²) for some constant c > 0.2604, improving the previous best bound of c>0.2083 by Dumitrescu and Mandal (2020). Arrangements of pseudolines (and in particular arrangements of lines) are important objects appearing in many forms in discrete and computational geometry. They have strong ties for example with oriented matroids, sorting networks and point configurations. Let Bₙ be the number of non-isomorphic pseudoline arrangements of order n and let bₙ := log₂(Bₙ). The problem of estimating bₙ dates back to Knuth, who conjectured that bₙ ≤0.5n² + o(n²) and derived the first bounds n²/6-O(n) ≤bₙ ≤0.7924(n²+n). Both the upper and the lower bound have been improved a couple of times since. For the upper bound, it was first improved to bₙ < 0.6988n² (Felsner, 1997), then bₙ < 0.6571 n² by Felsner and Valtr (2011), for large enough n. In the same paper, Felsner and Valtr improved the constant in the lower bound to c> 0.1887, which was subsequently improved by Dumitrescu and Mandal to c>0.2083. Our new bound is based on a construction which starts with one of the constructions of Dumitrescu and Mandal and breaks it into constant sized pieces. We then use software to compute the contribution of each piece to the overall number of pseudoline arrangements. This method adds a lot of flexibility to the construction and thus offers many avenues for future tweaks and improvements which could lead to further tightening of the lower bound.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections