WORK PACKAGE 2
Stochastic Geometry and Networks Details
Stochastic Geometry deals with random geometric structures. Among its many uses, it has been widely used to model and study wireless networks; see for example [BB09, H12, HABDF09, EHH13, BC03, PGWC09, NBK07], but also finds applications in many other fields like Astronomy, Ecology and Material Sciences [MS01, WS09, SP00, DL00, T13, C08]. Stochastic Geometry is an interdisciplinary field, which requires strong expertise in both Discrete Geometry and Probability, both areas wellrepresented in CONNECT. We will study problems related to random geometric networks, and also related to the problems of Work Package 1, of which we now give some examples.
Suppose that n points are placed uniformly at random in the unit square. In this setting many fundamental questions can be asked, whose answers may have far reaching practical and theoretical applications. CONNECT members Dr. Arizmendi and Dr. Salazar [AS15] computed the expected area of the largest “hole" in the square. Their results imply that with high probability there is a point of the square at distance at least (1 + o(1)) (log n)/n from the original points. This has direct implications for wireless networks. Suppose that the n points are radio antennas placed at random on some terrain; their result gives the expected value of the maximum distance of a point of the terrain to the nearest antenna. In other instances the answer to these questions is of theoretical interest. In [FMHM15], two CONNECT members computed the expected number of non-convex four-holes with vertices in the random points. They proved that this is equal to 12n2 log n + o(n2 log n). The problem of computing the maximum possible number of non-convex fourgons in a set of points belongs to the well-known family of Erdős-Szekeres type problems. The previous best bound on this number was O(n5/2 log n) [AFGHHHUV14]. In this case the use of probability gave a significant improvement on this bound.
When designing a network it is important to be able to compute various parameters to evaluate its performance (for example its connectivity). Fast Algorithms to compute many of these parameters have been proposed in Computational Geometry. However, they often assume a precise knowledge. In recent years a different viewpoint has been proposed, in which the input may change or be imprecise with some given probability. We will work on algorithmic problems under these assumptions. Consider a set of n nodes in the plane. Suppose we want to compute the minimum length geometric network connecting these nodes, called the Minimum Spanning Tree (MST). It is has been known for a long time that the MST can be computed in O(n log n) time. Now, suppose that each node has a certain probability of failure, and we are interested in computing the expected length of the MST of the nodes that are still available. Chan, Kamousi, Suri [KS11] showed that this problem is #P-hard. Under this assumption CONNECT member Dr. Pérez-Lantero has shown that parameters, which are straightforward to compute in a deterministic setting, like area and perimeter of the convex hull are #P-complete [P16]. It is a challenge to design fast algorithms under this scenario.
In some instances a random setting may be an advantage rather than a hindrance. When designing algorithms one considers the worst case scenario. It often happens that this scenario is highly unlikely to occur in real life. A random instance may be a better model in this case. For example, one may wish to store the combinatorial data pertaining the positions of the nodes of a network, which can be done with order types [GP83]. Unfortunately, to store a coordinate representation of a given order type of a set of points, up to an exponential number of bits are needed, see [GPS89]. We believe that this is not the case for random point sets. We conjecture that the expected number of bits needed to store the order type of a random point set in the unit square is polynomial. If this is the case then to store this data for real life networks may require little space. We will work on this problem.
Spectral Graph Theory (see for example [C97]) aims to give information of a graph from the eigenvalues and eigenvectors of matrices naturally associated with those graphs, such as the Laplacian or the adjacency matrix. Spectral theory of graphs is related to (stochastic) processes on graphs and mathematical physics. A very direct connection between the combinatorial aspects of a graph and its spectrum is given by the fact that one can count closed paths in the graph by considering the traces of powers of the adjacency matrix. Hence, one can get combinatorial information about the graph from its spectrum and vice versa. Models of random graphs are related to the spectrum, and studied because of their importance in applications. One of the first papers studying the distribution of random graphs different from the Erdős-Renyi model [ER60, ER60b] was the one of McKay [M81] which states that the asymptotic distribution of d-regular graphs is given by the Kesten-McKay distribution. The main observation there is that a large random d-regular graph looks locally as a d-regular tree, using combinatorial arguments or in a more modern way, using free probability; indeed the d-regular tree is the d-fold free product graph of K2 and thus its distribution is the d-fold free additive convolution of the Bernoulli distribution. These ideas allow to combine combinatorial tools and probabilistic arguments to find the spectrum of large random graphs. Recently, Dimitriu and Pal [DP12] and Tran, Vu and Wang [TVW13] showed that if d and n-d tend to infinity with n, then the asymptotic distribution of d-regular graphs converges to a semicircle distribution [W67]. More recently, CONNECT member Arizmendi and Gaxiola [AG16] generalized the theorem of McKay [M81] and showed that even at the level of vertices which are at distance k, the random d-regular graphs behave like d-regular trees. Other quantities and objects of interest have also been studied, such as eigenvectors or functional limits [DJPP13].
