On the number of arrangements of pseudolines (Q1380817): Difference between revisions

An \(x\)-monotone curve in Euclidean plane is called a pseudoline. An arrangement of pseudolines is a family of pseudolines with the following properties: (i) each pair of pseudolines has a unique point of intersection where the pseudolines cross, and (ii) no 3 pseudolines have a common point of intersection. Two arrangements are considered isomorphic, if their face lattices are isomorphic by re-labelling the pseudolines. The major contribution of the paper is an improved upper bound for the number of arrangements of \(n\) pseudolines, \(2^{. 6974n^2}\). As a byproduct, it turns out that the maximal number of halving lines of 10 points in the plane is 13. The main tool to achieve this bound is the following encoding. Associate with line \(i\) a permutation \(\sigma_i= (\sigma^i_1, \sigma^i_2, \dots, \sigma^i_{n-1})\) of \(\{1,2, \dots, i,\dots, n\}\) which tells the order of other lines as they cross \(i\). The vector \((\sigma_1, \sigma_2, \dots, \sigma_n)\) is known as an encoding of the arrangement. The paper shows that, for \(\tau^i_j=1\) if \(\sigma^i_j>i\) and \(\tau^i_j=0\) otherwise, and \(\tau_i= (\tau^i_1, \tau^i_2, \dots, \tau^i_{n-1})\), the vector \((\tau_1, \tau_2, \dots, \tau_n)\) is already an encoding.