Maximizing the number of parallel lines, can you beat the regular $n$-gon?

Question

Given $n$ points in the plane, with no 3 on a line, there are $n(n-1)/2$ lines that pass through exactly 2 of them. We partition these $n(n-1)/2$ lines in equivalence classes where lines are equivalent if they are parallel.

What is the lowest number of equalence classes we can get?

• Putting the $n$ points on the corners of a regular $n$-gon we get $n$ equivalence classes.

• The minimum can not be less than $n-1$ since no two of the $n-1$ lines through a given point are parallel to each other.

This leaves us with only two possibilities for the answer, and based on playing around a bit in GeoGebra the answer is $n$ rather than $n-1$. In other words: it seems impossible to beat the regular $n$-gon.

This makes sense intuitively: things that minimize or maximize some quantity are often highly symmetrical and you can't beat the regular $n$-gon when it comes to symmetry.

But on the other hand: this question can be reformulated in terms of abstract projective geometry as follows, and there the notion of 'regular' does not make a whole lot of sense:

In a projective plane, let a line $l$ and $n$ points not on $l$ be given such that no three points lie on the same line. Each two of the $n$ points define a a unique line through them that in turn intersects $l$. Obviously the maximum number of such intersections is $n(n-1)/2$ but what is the minimum and how to attain it?

In this formulation it is not even clear at first sight that the answer must be $\geq n-1$ (although on second sight it is, since two lines that share two points must be equal) so I don't think this more general formulation is very useful, but maybe it is? It would indeed be interesting to know if the answer would be different for projective planes over finite fields from what it is in the original formulation.

Answer 1

PROOF (For the original formulation)

Form the convex hull of the points and let $u,v,w$ be three successive points on this hull. Then consider the $n-1$ lines through $v$ and the line $uw$.

Any point other than $v$ on a line through $v$ parallel to $uw$ would be outside the convex hull and so we have found $n$ non-parallel lines as required.

Answer 2

FINITE PROJECTIVE PLANES (Preliminary thoughts - too long for comments)

Your idea seems very interesting. It certainly has different results from the Euclidean case. For example, the bound of $n-1$ can (at least sometimes) be attained.

Consider a projective plane of order $2$. (There is only one but we don't need to know that.)

Take any line $l$. This has three points.

Consider the set $S$ of four points not on $l$.

If any three points of $S$ were on a line then this line would intersect $l$ and therefore would have more than three points, which is impossible.

The lines joining pairs of points of $S$ then intersect $l$ at only three points.

MAXIMISING $n$

In the comments you propose that

the maximal number of points that can simultaneously satisfy the two conditions (no 3 on a line and no one of them on a special, pre-specified line) is 1 more than the number of points on a line (so q+2 for order q planes)

If we ignore the pre-specified line, then a relevant result is stated here: https://mathoverflow.net/questions/278762/largest-number-of-points-one-can-pick-in-finite-projective-space-without-getting

In $PG(2,q)$ the maximum is $q+1$ for odd $q$ but $q+2$ for even $q$.