Explicit Ramsey graphs and Erdős distance problems over finite Euclidean and non-Euclidean spaces (Q1010710): Difference between revisions

Summary: We study the Erdős distance problem over finite Euclidean and non-Euclidean spaces. Our main tools are graphs associated to finite Euclidean and non-Euclidean spaces that are considered in \textit{E. Bannai, O. Shimabukuro}, and \textit{H. Tanaka} [Eur. J. Comb. 25, No. 2, 243--259 (2004; Zbl 1033.05099), Discrete Math. 309, No. 20, 6126--6134 (2009; Zbl 1208.05046)]. These graphs are shown to be asymptotically Ramanujan graphs. The advantage of using these graphs is twofold. First, we can derive new lower bounds on the Erdős distance problems with explicit constants. Second, we can construct many explicit tough Ramsey graphs \(R(3,k)\).