Explicit Ramsey graphs and Erdős distance problems over finite Euclidean and non-Euclidean spaces

MaRDI QIDQ1010710zbMATH OpenFDO

Authors Le Anh Vinh

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.3508, https://eudml.org/doc/117208, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r5.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Erd?s problems and related topics of discrete geometry (52C10)

Abstract: We study the Erdos 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 Bannai-Shimabukuro-Tanaka (2004, 2007). 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 Erdos distance problems with explicit constants. Second, we can construct many explicit tough Ramsey graphs R(3,k).

Review text

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

Recommendations

• Finite analogues of Euclidean space
• Open problems in Euclidean Ramsey theory
• Non-Ramanujancy of Euclidean graphs of order 2\(^{r}\)
• Finite Euclidean graphs over rings
• Distance Ramsey numbers

Cited in

(15)

• Commutative association schemes
• On character sums with distances on the upper half plane over a finite field
• The generalized \(k\)-resultant modulus set problem in finite fields
• On distance sets and product sets in vector spaces over finite rings
• The number of occurrences of a fixed spread among \(n\) directions in vector spaces over finite fields
• On the sums of any k points in finite fields
• A bound for s-distance permutation families and explicit Ramsey graphs
• Distance preserving Ramsey graphs
• On the additive energy of the distance set in finite fields
• The analog of the Erdös distance problem in finite fields
• On kaleidoscopic pseudo-randomness of finite Euclidean graphs
• Distance sets of two subsets of vector spaces over finite fields
• On a Furstenberg-Katznelson-Weiss type theorem over finite fields
• On the generalized Erdős-Falconer distance problems over finite fields
• On Ramsey numbers for special complete distance graphs

This page was built for publication: Explicit Ramsey graphs and Erdős distance problems over finite Euclidean and non-Euclidean spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010710)