On the number of collinear triples in permutations

Abstract

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

4 pages

Cited by in corpus (1)

• Collinear triples in permutations