Random Networks Workshop
21st May, 2025

Title: Entropy of High Dimensional Random Geometric Graphs

Abstract: In the modern age, high dimensional data is becoming more and more common. In order to model such data, it is important to understand the geometry of and the distance between data points in high dimensional space. We extend a multivariate central limit theorem for distance distributions in high dimensional cubes to high dimensional tori, and show that translation invariance means that the distribution of random geometric graphs (RGGs) on the torus limits to Erdős–Rényi ensemble, whereas the distribution of RGGs on a cube tends to a fundamentally different limit, with lower entropy. We then attempt to introduce higher-order corrections to the CLT to approximate the entropy of RGGs in lower dimensional space.

Title: Dissimilar Batch Decompositions of Random Datasets

Abstract: For better learning, large datasets are often split into small batches and fed sequentially to the predictive model. In this talk, we study such batch decompositions from a probabilistic perspective. We assume that data points are drawn independently from a given space and define a concept of similarity between two data points. We then consider decompositions that restrict the amount of similarity within each batch and obtain high probability bounds for the minimum size. We demonstrate an inherent tradeoff between relaxing the similarity constraint and the overall size and also use martingale methods to obtain bounds for the maximum size of  data subsets with a given similarity.

Title: Sharp threshold for reconstructing a positive fraction of the points from a random subset of the pairwise distances

Abstract: Let V = {v_1 , …, v_n} be points on the real line.  Suppose that we are only know the following information about points V: for every pair {v_i, v_j} independently with probability p we learn the distance between v_i and v_j. Girão, Illingworth, Michel, Powierski, and Scott conjectured that, for every c>1, if p = c/n then we can determine all pairwise distances between a positive fraction of the vertices with high probability. We resolve the conjecture.

Title: Sampling (Coxeter) Tournaments

Abstract: In a classical tournament, every pair of players competes in a game, with the winner earning +1 point and the loser receiving -1 point. In a Coxeter tournament, in addition to the competitive game, every pair of players also plays a collaborative game. In this game, both players either win, each gaining +1 point, or both lose, each receiving -1 point. After the tournament, all points are summed, resulting in a score sequence.

In this talk, I will discuss how one can approximately sample uniformly from the sets of both classical and Coxeter tournaments with a given score sequence.

Based on joint work with Matthew Buckland, Brett Kolesnik, and Rivka Mitchell.