On the number of collinear triples in permutations

Liangpan Li

Published 2008-02-05, updated 2008-05-02Version 2

Let $\alpha:\mathbb{Z}_n\to\mathbb{Z}_n$ be a permutation and $\Psi(\alpha)$ be the number of collinear triples modulo $n$ in the graph of $\alpha$. Cooper and Solymosi had given by induction the bound $\min_{\alpha}\Psi(\alpha)\geq\lceil(n-1)/4\rceil$ when $n$ is a prime number. The main purpose of this paper is to give a direct proof of that bound. Besides, the expected number of collinear triples a permutation can have is also been determined.