<%@ 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
cooper@cims.nyu.edu
2Department of Mathematics, University of British Columbia, 1984 Mathematics Road, Vancouver, BC, Canada
solymosi@math.ubc.ca
Annals of Combinatorics 9 (2) p.169-175 June, 2005
AMS Subject Classification: 51E15, 11T99
Abstract:
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

References:

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.