On the number of collinear triples in permutations

2008/02/05 by Liangpan Li, Li, Liangpan
Mathematics · #11T99 #51E15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:11T99 #msc:51E15

paper · pdf · doi:10.48550/arxiv.0802.0572

4 pages

arxiv created 2008/05/02 · arxiv updated 2009/12/01

Abstract

Let α:ℤ_n→ℤ_n be a permutation and Ψ(α) be the number of collinear triples modulo n in the graph of α. Cooper and Solymosi had given by induction the bound min_αΨ(α)≥\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.

Related

• Collinear triples in permutations
• Collinear Points in Permutations
• Permutations minimizing the number of collinear triples
• Collinear Triple Hypergraphs and the Finite Plane Kakeya Problem
• The Multiple Permutation Problem and Some Conjectures