<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 9 Issue 2" %>
Collinear Points in Permutations
Joshua N. Cooper1 and Jozsef Solymosi2
1Department of Mathematics, Courant Institute of Mathematical Sciences, New York University, New York, USA
2Department of Mathematics, University of British Columbia, 1984 Mathematics Road, Vancouver, BC, Canada
Annals of Combinatorics 9 (2) p.169-175 June, 2005
AMS Subject Classification: 51E15, 11T99
Consider the following problem: how many collinear triples of points must a transversal of have? This question is connected with venerable issues in discrete geometry. We show that the answer, for n prime, is between (n-1)/4 and (n-1)/2 consider an analogous question for collinear quadruples. We conjecture that the upper bound is the truth and suggest several other interesting problems in this area.
Keywords: finite field, affine geometry, collinearity, transversal


1. H.E. Dudeney, Amusements in Mathematics, Nelson, Edinburgh, 1917.

2. R.K. Guy and P.A. Kelly, The no-three-in-line problem, Canad. Math. Bull. 11 (1968) 527--531.

3. R. Lidl, and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and Its Applications, Vol. 20, Cambridge University Press, Cambridge, 1983.

4. K.F. Roth, On a problem of Heilbronn, J. London Math. Soc. 26 (1951) 198--204.