Finite projective planes

Question

How big a set of points in general position (i.e., no three collinear) can be found in a finite projective plane of order $n$?

I hope the answers won't be too technical, as I know almost nothing about projective planes besides the definition.

Motivation: I want to use this for an example in graph theory.

My work: If $S$ is a set of points in general position, then $|S|\le n+2$, since $S$ has at most a point $p$ and another point on each of the $n+1$ lines through $p$. So $n+2$ is an upper bound. For a lower bound, let $S$ be any maximal set of points in general position and note that $\binom{|S|-1}2\ge n$, whence $|S|\ge\frac{3+\sqrt{1+8n}}2$.

Answer 1

An arc is a set of points, no three collinear. An arc is complete if it is maximal with respect to set inclusion. So you are asking for the maximum size of a complete arc.

According to this paper, this appears to be a hard problem in general, although if $n$ is even, then your upper bound is attained, and if $n$ is odd, then it can be improved to $n+1$.

I was hoping to track down a proof for the $n$ even case (due to Segre) but it appears to be a bit too obscure. Hopefully you have better luck. Actually it's not clear to me if he "only" proved it for $n=2^k$.

Answer 2

The size of an arc is always less than $n+2$, as you noted. However $n+2$ can only occur if $n$ is even. To see this, take a collection of $n+2$ points no three collinear; it can then have no tangent lines. So every line either meets $0$ or $2$ points of the arc. Take a point not in the arc, and consider all of the secants to the arc through that point. There needs to be $(n+2)/2$ secants so $n$ must be even!

When the plane is $PG(2,q)$, q a prime power, than we always have $q+1$-arcs (ovals) defined by a conic. These are the only $q+1$-arcs when $q$ is odd. When $q$ is even, these can be extended to $q+2$-arcs (hyperovals). More interestingly, we have $q+2$-arcs that are not conics, and these are not classified. The hard problem referred to by Casteels is actually to find small arcs that are complete, that is they cannot be extended. Usually if arcs are large enough they can always be extended.

There are also interesting problems related to arcs in non-Desarguesian projective planes. Can we always find ovals? Some planes (Hall planes) can inherit them from the Desarguesian planes, but this problem is open in general (indeed we do not even know all of the planes).