Embedded Files
Random Networks Workshop
The University of Sheffield Probability Group invites you to attend a one-day workshop on the broad topic of Random Networks.
This workshop is the third in a series which aims to bring together academics interested in random networks regularly to hear about exciting advancements in the field. This workshop previously ran in 2022 and 2024. Plans are in place to run this workshop again in 2026.
Please see below for details of this workshop as well as information about how to register.
Programme
Programme
09:00 - 09:30: Registration (tea/coffee + Pastries, catered by PJ Taste.)
09:00 - 09:30: Registration (tea/coffee + Pastries, catered by PJ Taste.)
Title: to come
Abstract: to come
10:20 - 10:50: Refreshments (tea/coffee + biscuits, catered by PJ Taste.)
10:20 - 10:50: Refreshments (tea/coffee + biscuits, catered by PJ Taste.)
Title: Lower tail probabilities via Gibbs uniqueness on hypertrees
Abstract: Given a graph $H$, what is the probability that the Erdős-Rényi random graph $G(n,p)$ contains no copy of $H$ or fewer copies than expected? This is a classical example of a `lower-tail' large deviation probability that arises naturally in combinatorics. Other examples include the probability that a random subset of $\{1,\ldots, n\}$ avoids $k$-term arithmetic progressions or that a random subset of an abelian group is sum free.
In this talk I will discuss a method for determining the logarithmic asymptotics (or rate function) for such probabilities. The method applies for a range of parameters in the `critical regime': between the regime amenable to hypergraph container methods and that amenable to Janson's inequality.
The method works in the general framework of estimating the probability that a $p$-random subset of vertices of a $k$-uniform hypergraph contains fewer hyperedges than expected. We show that under some simple structural conditions on the hypergraph and an upper bound on $p$ determined by a phase transition on an infinite hypertree, this probability can be approximated by a formula derived from a Gibbs measure on the hypertree.
This is joint work with Will Perkins, Aditya Potukuchi and Michael Simkin.
11:40 - 11:50: Break
11:40 - 11:50: Break
11:50 - 12:40: Open problem session
Chairing session: Nic Freeman
11:50 - 12:40: Open problem session
Chairing session: Nic Freeman
Problems will be delivered in the following order during the session:
Problem 1: Matthew Jenssen, King's College London
Problem 2: Debleena Thacker, Durham University
Problem 3: Bas Lodewijks, University of Augsburg
Problem 4: Dominic Yeo, King's College London
Problem 5: Christian Mönch, Johannes Gutenberg University Mainz
Problem 6: Yangrui Xiang, University of Nottingham
Problem 7: Alastair Haig, University of Sussex
Problem 8: Benjamin Andrews, University of Sheffield
Problem 9: Sergio Estan Ruiz, Imperial College London
Talks should aim to be five minutes long (or shorter, if possible). However, if more time is required, we will use some of the lunch break.
12:40 - 13:30: Lunch (Sandwiches, catered by PJ Taste.)
12:40 - 13:30: Lunch (Sandwiches, catered by PJ Taste.)
13:30 - 14:50: Contributed talks by PDRAs and PhD students
Chairing session: Robin Stephenson
13:30 - 14:50: Contributed talks by PDRAs and PhD students
Chairing session: Robin Stephenson
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.
14:10 - 14:30: Georgii Zakharov (PhD student), University of Oxford
14:10 - 14:30: Georgii Zakharov (PhD student), University of Oxford
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.
14:50 - 15:10: Refreshments (tea/coffee + biscuits, catered by PJ Taste.)
14:50 - 15:10: Refreshments (tea/coffee + biscuits, catered by PJ Taste.)
Title: to come
Abstract: to come
16:00 - 16:10: Break
16:00 - 16:10: Break
16:10 - 17:00: Maksim Zhukovskii, University of Sheffield (website)
Chairing session: Jonathan Jordan
16:10 - 17:00: Maksim Zhukovskii, University of Sheffield (website)
Chairing session: Jonathan Jordan
Title: Sharp thresholds for spanning regular subgraphs
Abstract: Let F be a d-regular graph on n vertices. What is the threshold probability for containing an isomorphic copy of F by a binomial random graph G(n,p)? In the talk, I will give an asymptotically sharp answer for a large family of graphs F. In particular, this family includes the square of a cycle, confirming the conjecture of Kahn, Narayanan, and Park. Although the proof relies on the fragmentation technique, as the original proof by Kahn, Narayanan, and Park for establishing a coarse threshold, the way of selecting fragments is essentially different. One of the main ingredients of the proof is the fact that sufficiently many squares of cycles have fragments that avoid squares of paths of length at least logarithmic in n with high probability.
Registration Link
Registration Link
https://forms.gle/qSqvP51SvhPFQ1SP8
Registration is open and will close at 12 noon on 12-May-2025.
Location
Location
All talks will take place in Lecture Theatre A of the School of Mathematics and Statistics located in Hicks Building. This room is located at the south entrance to the Hicks Building by the Harley Pub (down the hill from the main entrance.) Helpful images are below.
Address: Hicks Building, Hounsfield Road, Sheffield, S3 7RH
The red box on the right hand side is Sheffield's train station. The red circle on the left is the School of Mathematics and Statistics. Distance between the two is a 15-20 minute walk.
Here you can see the School of Mathematics and Statistics (Hicks Building) and a red arrow indicating the entrance where you will find Lecture Theatre A. The Black pentagon is where lunch will be served.
Hotels in the area
Hotels in the area
Below are a few hotels in the area for those of you who intend to stay overnight in Sheffield.
Funding bodies
Funding bodies
This meeting is generously supported by a grant from the Heilbronn Institute for Mathematical Research and the Engineering and Physical Sciences Research Council. The University of Sheffield has supplied physical and online facilities for this workshop. The Applied Probability Trust is providing administrative and organisational support for this meeting.
Page updated
Report abuse