Permutations minimizing the number of collinear triples

2025/01/04 by Joshua Cooper, Cooper, Joshua, Jack Hyatt +1
Computer Science · Engineering · Mathematics · #11T99 (Secondary) #51E15 (Primary) 05B25 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2501.02331

openalex publication_date 2025/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We characterize the permutations of \mathbbF_q whose graph minimizes the number of collinear triples and describe the lexicographically-least one, affirming a conjecture of Cooper-Solymosi. This question is closely connected to Dudeney's No-3-in-a-Line problem, the Heilbronn triangle problem, and the structure of finite plane Kakeya sets. We discuss a connection with complete sets of mutually orthogonal latin squares and state a few open problems primarily about general finite affine planes.

Related

• Collinear Triple Hypergraphs and the Finite Plane Kakeya Problem
• Collinear triples in permutations
• On the number of collinear triples in permutations
• Collinear Points in Permutations
• On the structure of pointsets with many collinear triples