On The Number of Robust Geometric Graphs in a Euclidean Space

Authors

  • Lufei Yang Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, USA
  • Colin Yip Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, USA
  • Madison Zhao Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, USA
  • Konstantin Tikhomirov Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, USA

DOI:

https://doi.org/10.5195/pimr.2024.41

Abstract

We say that a graph Γ=(V,E) with vertices in a k–dimensional Euclidean space is an ε–robust distance graph with threshold τ if any two vertices v,w in V are adjacent if and only if vw2(1+ε)1τ and are not adjacent if and only if vw2>(1+ε)τ. We show that there are universal constants C,c,c>0 with the following property. For kCdlogn, asymptotically almost every d–regular graph on n vertices is isomorphic to a cd–robust distance graph in Rk , whereas for kcdlognlogd , a.a.e d–regular graph on n vertices cannot be represented as an cd–robust distance graph.

Downloads

Published

2024-12-06

How to Cite

[1]
L. Yang, C. Yip, M. Zhao, and K. Tikhomirov, “On The Number of Robust Geometric Graphs in a Euclidean Space”, Pittsburgh Interdiscip. Math. Rev., vol. 2, pp. 89–105, Dec. 2024.

Issue

Section

Undergraduate Research Articles