3
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ This appears to be a hard problem in general, although for $n$ even, the upper bound is achieved: research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/… $\endgroup$ – Casteels Aug 15 '14 at 11:55
  • $\begingroup$ @Casteels Oh, the sets I was asking about are called "arcs"? I didn't know that. Thanks for your comment and the reference. If you post your comment as an answer, I will accept it. $\endgroup$ – bof Aug 15 '14 at 21:30
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Is there always an arc or size $n$? $\endgroup$ – bof Aug 18 '14 at 18:54
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.