Allowable sequences

(Jeck here.)

Consider an arrangement of $n$ lines on the plane, which do not necessarily need to be in general position. There are many combinatorial problems one can explore with such configurations:

1. If no three lines are concurrent, the number of regions into which these lines divide the plane is given by $1+\binom{n+1}{2}$.
2. If not all lines are concurrent, there is always at least one intersection point that is shared by exactly two lines. This is the dual of the Sylvester-Gallai Theorem.

To solve these problems, what properties of the lines do we actually use? A crucial property is that any two lines either intersect at exactly one point or are parallel. If we consider the lines within the projective plane, then parallel lines are also considered to intersect once, at a point at infinity. Interestingly, this characteristic—where lines intersect once transversely or are parallel—often suffices for these problems. The actual "straightness" of the lines is usually not essential.

Pseudoline arrangements

We can generalise the notion of an arrangement of lines to an arrangement of pseudolines, where pseudolines are allowed to be "curvy". More formally, a pseudoline is a simple curve that extends to infinity in both directions. An arrangement of pseudolines must have the property that every two pseudolines intersect exactly once transversely (or, in the context of the projective plane, parallel pseudolines intersect at a point at infinity).

One can see that the combinatorial properties described in problem 1 above also hold true for pseudoline arrangements. Regarding the Sylvester-Gallai Theorem, there is a well-known proof by considering the point closest to some line, which many of you might have encountered in your Olympiad days. However, this proof might be challenging to extend to pseudoline arrangements. Nevertheless, the theorem itself still holds, since there are other proofs that can be generalised to apply to pseudolines.

However, not all pseudoline arrangements are "isomorphic" to some line arrangements. Here's an example:

There is no concurrency in the middle since the pseudolines can be bent around that point. However, for line arrangements, concurrency in the middle arises due to Pappus's theorem. Despite these differences, most theorems about line arrangements also hold true for pseudoline arrangements.

Now, consider a finite set of points on the plane, not necessarily in general position, where some of the points are collinear. We can generalise this by replacing straight lines with pseudolines. More formally, a generalised configuration is a finite set of points in the plane, along with a pseudoline arrangement such that each pseudoline contains at least two points, and there is a pseudoline through any pair of points.

Again, not all generalised configurations are isomorphic to ordinary configurations of points. Nevertheless, most theorems about configurations of points still hold true for generalised configurations.

Allowable sequences

A natural question to ask is how many non-isomorphic configurations of points there are. This motivates the following combinatorial description of a configuration of points, due to Goodman and Pollack.

Label the points 1 to $n$ and start with a generic line $l$. Project the $n$ points onto $l$ and record their ordering on $l$. Slowly rotate $l$ anti-clockwise, and note down the changes in the ordering of the projections. Continue this until $l$ has rotated $180^{\circ}$. Below is an example with 5 points.

Initially, the ordering is $12345$. As $l$ rotates and becomes horizontal, $12$ and $34$ get transposed, resulting in the permutation $21435$. The next permutation change occurs when $l$ is perpendicular to both $14$ and $35$, leading to $24153$. It changes again to $24513$ when $l$ is perpendicular to $15$, and so on. We obtain the following sequence of permutations:

1 2 3 4 5
2 1 4 3 5
2 4 1 5 3
2 4 5 1 3
5 4 2 3 1
5 4 3 2 1

The underlined blocks correspond to points collinear on a line perpendicular to $l$, and multiple blocks in the same row correspond to parallel lines. Notice that the final permutation is the reverse of the first. Each permutation is obtained from the previous one by flipping one or more consecutive blocks, and every pair of numbers is flipped across each other exactly once (this reflects the fact that there is a unique line through any two points). This is an example of an allowable sequence.

An allowable sequence is a sequence of permutations $\sigma_0, \ldots, \sigma_m$ (viewed as strings) of a finite set $S$ satisfying:

1. $\sigma_{i+1}$ is obtained from $\sigma_i$ by reversing one or more consecutive blocks of symbols.
2. Every pair of symbols is flipped across each other exactly once. Therefore, $\sigma_m$ is the reverse of $\sigma_0$.

We have just seen that any configuration of points gives rise to an allowable sequence. This procedure can also be extended to obtain an allowable sequence from any generalised configuration. Remarkably, generalised configurations and allowable sequences are equivalent: every allowable sequence arises from some generalised configuration.

Some problems

What is the point of allowable sequences? By rewording a problem about configurations of points into a problem about allowable sequences, crucial observations can often become trivial.

(IMO 2011 Q2) Let $\mathcal{S}$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal S$ are collinear. A windmill is a process that starts with a line $\ell$ going through a single point $P \in \mathcal S$. The line rotates clockwise about the pivot $P$ until the first time that the line meets some other point belonging to $\mathcal S$. This point, $Q$, takes over as the new pivot, and the line now rotates clockwise about $Q$, until it next meets a point of $\mathcal S$. This process continues indefinitely. Show that we can choose a point $P$ in $\mathcal S$ and a line $\ell$ going through $P$ such that the resulting windmill uses each point of $\mathcal S$ as a pivot infinitely many times.

This is a problem about configuration of points, so let's rephrase it in terms of allowable sequences. We have an allowable sequence $\sigma_0,\ldots,\sigma_m$, and the windmill is a pointer pointing at some element of each $\sigma_i$. As we move from $\sigma_i$ to $\sigma_{i+1}$, the fact that no three points are collinear translates to the fact that $\sigma_{i+1}$ is obtained by disjoint transpositions. If none of the transpositions involve the pointed element, the pointer doesn't change. However, if there is a transposition $xy$ with the pointer at $x$, then the pointer changes to $y$. Notice anything? The location of the pointer doesn't change, and this translates to the fact that the number of points to the left and right of $\ell$ is invariant. The rest of the problem follows by picking the pointer to start at the center of $\sigma_0$.

Here is another problem which was solved using allowable sequences. Give it a try :)

(Ungar's Theorem [1]) $2n$ points on the plane determine at least $2n$ directions. That is, there are at least $2n$ pairwise non-parallel lines among all lines drawn by connecting two points.

What about $2n+1$ points? It turns out there are configurations of $2n+1$ points determining only $2n$ directions. And $2n$ is the best, by ignoring one point and applying Ungar's.

Kupitz's conjecture

Here's another simple-looking problem involving configuration of points.

(Kupitz's conjecture) Given $n$ points on the plane, there is a line through at least two points such that the number of points on both sides differ by at most one.

Why one and not zero? Just consider an odd number of points in general position.

It turns out this conjecture is false, due to a construction by Alon. This construction has the property that for any determined line, the number of points on both sides differ by at least 2.

This has 12 points, and can be easily extended to any larger even number by adding an equal number of points on both sides of some line.

Can you construct a configuration with an odd number of points such that for any determined line, the number of points on both sides differ by at least 2?

A construction can be found in [2].

So, Kupitz's conjecture is false, but we can easily modify it by replacing "one" with some constant.

(Kupitz's conjecture, modified) There is a constant $C>0$ such that for any $n$ points on the plane, there is a line through at least two points such that the number of points on both sides differ by at most $C$.

This is currently open: we do not even know of a counter-example for $C=2$.

What about upper bounds? Pinchasi showed that there is an upper bound of the form $C\log \log n$. In fact, their proof uses allowable sequences, so their result holds more generally for generalised configurations.

(Pinchasi [3]) There exists an absolute constant $C$ such that every generalised configuration with $n$ points contains a pseudoline where the number of points on either side of the pseudoline differ by at most $C \log \log n$.

Recently, it was proved that this is tight. In other words, Kupitz's modified conjecture is false for generalised configurations!

(Conlon-L. [2]) There exists a positive constant $c$ such that for every sufficiently large natural number $n$ there is a generalised configuration with $n$ points where the number of points on either side of each pseudoline differ by at least $c \log \log n$.

Finally, I conclude with the following generalisation of Kupitz's conjecture in 3D, which is open as far as I know. A natural generalisation is to ask for a plane through 3 points so that the number of points on both sides differ by at most $C$. However, we can ask the following simpler problem, which seems like there should be a trivial solution by a sweeping or projecting argument.

Is there is a constant $C>0$ such that for any $n$ points in $\mathbb{R}^3$, there is a plane through at least two points such that the number of points on both sides of the plane differ by at most $C$?

---

[1] P. Ungar. $2N$ noncollinear points determine at least $2N$ directions. J. Combin. Theory Ser. A, 33:343–347, 1982.
[2] D. Conlon and J. Lim, Everywhere unbalanced configurations, preprint available at https://arxiv.org/abs/2308.02466.
[3] R. Pinchasi, Lines with many points on both sides, Discrete Comput. Geom. 30 (2003), 415–435.