Deviation Estimates for Extremal Relay Random Geometric Graphs

Ghurumuruhan Ganesan IISER, Bhopal · 2025

Read Deviation Estimates for Extremal Relay Random Geometric Graphs by Ghurumuruhan Ganesan IISER, Bhopal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-07000.txt.

Introduction

Ghurumuruhan Ganesan, writing alone in 2025, sets when relay nets on a drawn grid stay near best, and how heavy their worst link can run. A grid graph is drawn on a unit square. A chance web of near links then ties its knots as relays, to bear flow at low cost.

First come the terms: when does a relay web stand at all, and when is it near the best the drawn grid could ask, in the grid's own marks? Next, link weights dealt by a steep chance law grade the web's load: bounds cap the top weight a relay web of a set span can bear. Chance relays, the work shows, can be both sure and lean.

Catalog record

CREATORGhurumuruhan Ganesan IISER, Bhopal
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-07000

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Deviation Estimates for Extremal Relay Random Geometric Graphs Ghurumuruhan Ganesan IISER, Bhopal Abstract In this paper, we consider a deterministic graph Γ \Gamma drawn on the unit square with straight line segments as edges and connect vertices of Γ \Gamma using edges of a random geometric graph (RGG) G G with adjacency distance r n r_{n} as relays. We call the resulting graph as a relay RGG and determine sufficient conditions under such relay RGGs exist and are also near optimal, in terms of the graph parameters of Γ . \Gamma. We then equip edges of G G with independent, exponentially distributed weights and obtain bounds for the maximum possible weight W n W_{n} of a relay RGG with a given length L n . L_{n}. Key words: Relay Random Geometric Graphs; Minimum Length; Maximum Weight; Deviation Estimates. AMS 2000 Subject Classification: Primary: 60C05, 60D05; 1 Introduction Random geometric graphs (RGGs) are a class of Euclidean random graphs that often occur in the study of wireless networks gupta diaz penrose . Consequently, structural properties of RGGs have been studied extensively from both theoretical and application perspectives. For e.g., in gan_one gan_two we have obtained bounds on the size of the giant component and diameter in subcritical RGGs, respectively, using percolation theoretic techniques. As examples of applications, zhang song ferrero use RGGs for analysis of different models of vehicular and wireless networks. Many variants of RGGs have been studied as well: In david , random “anti”-geometric graphs are defined and connectivity properties are studied for the large vertex regime and recently, pen2 studied “soft” RGGs where edges of RGG are removed with a certain probability and connectivity is again established for various regimes of the graph parameters. In this paper, we consider a weighted subclass of RGGs which we call as relay RGGs and obtain deviation estimates for its extremal counterparts. Specifically, we begin with a deterministic planar graph \Gamma with edges drawn as straight line segments in the unit square and use the edges of a random geometric graph (RGG) as “relays” to connect vertices of \Gamma using edge disjoint paths (if such paths exist). We call the resulting graph as a relay RGG and establish conditions under which \Gamma is “supported” in the sense that relay RGGs exist and are near optimal in terms of length. We then equip each edge of G with a random weight whose entries are independent and identically distributed (i.i.d.) and obtain deviations for the maximum weight of relay RGGs. To motivate this, consider a typical wireless application scenario where the vertices of \Gamma represent communication terminals and the edges of the RGGs are relay links through which messages are passed from one vertex of \Gamma to another, without interference (and hence the edge disjoint condition). When the edges of the relay RGG act as communication links, the weights have a natural interpretation of the channel fading gain and it is of interest to maximize the network throughput by choosing the relay RGG with the maximum possible weight. Selecting links with maximum fading gain (also known as diversity gain) has important applications in wireless communications and for more details on exploiting diversity in wireless networks, we refer to Chapter 7, goldsmith , Chapter 12, molisch and references therein. In this paper we obtain deviation estimates for the maximum weight of relay RGGs that are of the same order and also establish sufficient conditions for the L^{2}- convergence of the maximum weight, appropriately scaled and centred. In the following section, we state and prove our two main results regarding minimum length and maximum weight relay RGGs. 2 Relay Random Geometric Graphs Let f be any density on the unit square S=\left[-\frac{1}{2},\frac{1}{2}\right]^{2} satisfying \epsilon_{1}\leq\inf_{x\in S}f(x)\leq\sup_{x\in S}f(x)\leq\epsilon_{2} (2.1) for some constants 0<\epsilon_{1}\leq\epsilon_{2}<\infty. We assume throughout that constants do not depend on n. For n\geq 1, let \{X_{i}\}_{1\leq i\leq n} be independently and identically distributed (i.i.d.) random variables with density f(.). We assign the label i to the vertex location X_{i} and let K_{n} be the complete graph with vertex set \{1,2,\ldots,n\}. For r_{n}>0, let G=G(r_{n})\subset K_{n} be the subgraph of K_{n} consisting of all edges of length at most r_{n}. Here and henceforth length always refers to the Euclidean length and we define G to be the random geometric graph (RGG) with adjacency distance r_{n}. Let \Gamma=(V(\Gamma),E(\Gamma)) be any deterministic graph containing v_{0}=v_{0}(n) vertices and e_{0}=e_{0}(n) edges in the interior of the unit square S. Let G_{loc}=G_{loc}(G,\Gamma) be the graph whose edge set is the union of the edge set of G and the edge of the graph obtained by connecting each vertex v\in V(\Gamma) to all vertices of G within distance r_{n} from v. A path of length l in G_{loc} is a sequence \pi=(a_{1},\ldots,a_{l+1}) containing l edges, where each vertex a_{i} is adjacent to a_{i+1}. The vertices a_{1} and a_{l+1} are defined to be the endvertices of \pi. We say \pi is a relay path if a_{1} and a_{l+1} are vertices of \Gamma and every other a_{i} is a vertex of G. Correspondingly, we say that a subgraph H\subset G_{loc} is a relay RGG (with respect to \Gamma ) if H=\bigcup_{f\in E(\Gamma)}P(f) where: (i) Each P(f) is a relay path with the same endvertices as f, (ii) The path P(f_{1}) is vertex disjoint from P(f_{2}) if f_{1} and f_{2} do not share an endvertex and (iii) If f_{1} and f_{2} share a common endvertex u, then P(f_{1}) and P(f_{2}) have only the vertex u in common. Intuitively, if the number of edges in \Gamma is too large, then there may not exist a relay RGG with respect to \Gamma. To illustrate, consider the graph \Gamma_{0} formed by the union of the edges f_{i}=(u_{i},v_{i}),1\leq i\leq n where u_{i}=\left(\frac{i-1}{n},0\right) and v_{i}=\left(\frac{i-1}{n},\frac{2}{n}\right). Thus the edges \{f_{i}\} are vertical, parallel and spaced \frac{1}{n} apart and each f_{i} has length \frac{2}{n}. If the adjacency distance r_{n}=\frac{1}{2n}, then we see that there does not exist a relay RGG with respect to \Gamma. Let L(G,\Gamma) be the minimum number of edges in a relay RGG, if it exists; else set L(G,\Gamma)=\infty. The following result determines sufficient conditions under which relay RGGs exist and are also near optimal, in terms of the overall number of edges. For an edge f\in E(\Gamma) we let l(f) be the Euclidean length of f and define l_{0}:=\min_{f}l(f) and l_{tot}:=\sum_{f}l(f) respectively to be the minimum length of an edge and the sum total of all edge lengths, in \Gamma. Throughout constants do not depend on n. Theorem 2.1 Suppose \Gamma has e_{0} edges and e_{0}\leq n^{\alpha},\;\;\;\frac{1}{n^{\beta}}\leq r_{n}\longrightarrow 0\;\;\text{ and }\;\;\frac{l_{0}}{r_{n}}\longrightarrow\infty (2.2) where 0<\alpha,\beta<1 are constants satisfying \beta<\frac{1-\alpha}{2} so that e_{0} is much smaller than nr_{n}^{2}. for every \epsilon>0 there is a constant C>0 such that \mathbb{P}\left(\frac{l_{tot}}{r_{n}}\leq L(G,\Gamma)\leq\frac{l_{tot}}{r_{n}}(1+\epsilon)\right)\geq 1-e^{-Cnr_{n}^{2}}. (2.3) Moreover, if 0<\beta<\frac{1-\alpha}{4}, then there is a constant D>0 such that \mathbb{P}\left(\frac{l_{tot}}{r_{n}}\leq L(G,\Gamma)\leq\frac{l_{tot}}{r_{n}}+2e_{0}\right)\geq 1-e^{-Dnr_{n}^{4}}. (2.4) As a check we see that l_{tot}\geq l_{0}e_{0} and so the term \frac{l_{tot}}{r_{n}}\geq\frac{l_{0}}{r_{n}}\cdot e_{0} is much larger than e_{0}, by ( 2.2 ). In other words, as long as the number of vertices in \Gamma is small enough in the sense of ( 2.2 ), then we can find a relay RGG using the edges of G that is also near optimal in terms

Read the complete text