2012/02/22 by Timothy G. F. Jones, Jones, Timothy G. F.
Computer Science · Mathematics · #11B75 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:11B75
paper · pdf · doi:10.48550/arxiv.1202.4972
10 pages
arxiv created 2012/02/22 · openalex publication_date 2012/02/22 · arxiv updated 2012/02/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We use the theory of cross ratios to construct a real-valued function f of only three variables with the property that for any finite set A of reals, the set f(A) = f(a,b,c):a,b,c ∈ A has cardinality at least C|A|2/log|A|, for an absolute constant C. Previously-known functions with this property had all been of four variables. We also improve on the state of the art for functions of four variables by constructing a function g for which g(A) has cardinality at least C|A|2; the previously best-achieved bound was C|A|2/log|A|. Finally, we give an example of a five-variable function h for which h(A) has cardinality at least C|A|4/log|A|. Proving these results depends only on the Szemeredi-Trotter incidence theorem and an analoguous result for planes due to Edelsbrunner, Guibas and Sharir, each applied in the Erlangen-type framework of Elekes and Sharir. In particular the proofs do not employ the Guth-Katz polynomial partitioning technique or the theory of ruled surfaces. Although the growth exponents for f, g and h are stronger than those for previously considered functions, it is not clear that they are necessarily sharp. So we pose a question as to whether the bounds on the cardinalities of f(A), g(A) and h(A) can be further strengthened.