General position
Task number: 3898
Prove that for a finite projective plane of sufficiently high order the generalization of the axiom for quadruples applies:
For every \(k \in \mathbb N\) exists \(n \in \mathbb N\) such that for any finite projective plane \((X,\mathcal P)\) of order at least \(n\) there exist \(k\) points in th general position, i.e. a set \(K \subseteq X, |K|=k\) satisfying \(\forall P\in\mathcal P: |K\cap P|\le 2\).
Hint
First, try to construct a projective plane with a five-element set in the general position.
Then generalize the method to be possible to use mathematical induction on \(k\).
Solution
Let \(n_k\) be the smallest number such that each projective plane of the order \(n_k\) contains \(k\) points in the general position. We know from the axioms of the projective plane that \( n_4 = 2 \).
First for five: If we have a projective plane of order \(n\) and its four-element set in the general position \(K_4\), then these four points determine \(\binom{4}{2}\) lines. These lines have at most \(\binom{4}{2}(n+1)\) points. (In fact, exactly \(\binom {4}{2}(n+1)-8\), but that would only complicate our reasoning.) If the total number of points in the set \(X\) is higher than the number of points lying on the lines specified by \(K_4\), then there is a point \(x \in X \) which does not lie on any lines specified by the points \( K_4 \). The set \( K_4 \cup \{x\} \) is the wanted five-element in the general position. To get \( |X|=n^2+n+1> \binom{4}{2}(n+1)\) it sufiifes the order \(n\ge\binom{4}{2}=6\). Hence \(n_5 \le 6 \).
By induction we show that \(n_{k+1}\le\binom{k}{2}\). Assume that the above estimate holds for \(k\), and that a projective plane of order of at least \( \ binom {k} {2} \) is given. Since \(\binom{k}{2}\ge\binom{k-1}{2}\ge n_{k} \), according to the inductive hypothesis this projective plane contains a \(k\)-element set \( K_k \) in general position. The points \(K_k\) specify the \(\binom{k}{2}\) lines. On these lines at most \(\binom{k}{2} \left(\binom{k}{2}+1 \right)\) points may be placed. However, because the total number of points is \(\binom{k}{2}^2 + \binom{k}{2} +1 \), there is a point \(x\) outside these lines. The set \( K_k \cup \{x \} \) is the desired \((k+1)\)-element set in general position.
