# Training Week : Expansion properties and Random Walks

On 30 October– 3 November 2017 NETWORKS organizes the fifthTraining Week for PhD Students of NETWORKS. The topics of this Training Week are a minicourse on Expansion properties of networks and one on Random walks, forests and network analysis. Viresh Patel and Luca Avena are the main lecturers in the morning during this Training Week.

In the afternoon various Networks PhD students and other Networks researchers will give talks about their recent results. There will also be time for joint research in small groups (either in existing collaborations or in new collaborations) in so-called working sessions.

## Expansion properties of networks

Lecturer Viresh Patel

Expansion is a measure of how well connected a graph or network is. There are different closely-related notions of expansion depending on whether one takes a geometric, algebraic or probabilistic perspective. One way of defining expansion is the following: the expansion of an n-vertex graph is the smallest number c such that for every subset S of vertices with |S| \leq n/2, one must delete at least c|S| edges in order to disconnect S from the rest of the graph. The idea of expansion appears in different areas of mathematics and computer science with several applications, e.g. to construction of error correcting codes and to derandomisation of algorithms. The aim of the minicourse will be to give a basic understanding of various notions of expansion and how they are related to each other as well as some of their applications.

A good source of material for the course in the following survey:

## Random walks, forests and network analysis

Lecturer: Luca Avena

In this mini-course I will present part of my recent research work on random spanning forests on arbitrary given networks (graphs).

The main emphasis will be given on new applications in networks analysis and related randomized algorithms.

In particular, I plan to discuss in some details 1) a probabilistic notion of well distributed points in a network 2) a network reduction procedure 3) and an algorithm in the spirit of wavelets to process graph signals (i.e. functions defined on networks). If time allows, I'll also touch some further potential applications in clustering problems.

The main object of investigation will be a certain probability measure on spanning rooted forests of a graph. This measure is a variant of the so-called uniform spanning tree measure'' and it is intimately related with the graph Laplacian and with lots of random combinatorial models of current research interest in statistical mechanics (e.g. loop-erased walks, integrable systems, dimer models, sandpiles, Gaussian free fields, percolation, determinantal and coalescence-fragmentation processes). Although in the introductory lecture I'll try to highlight this more fundamental line of investigation, for the rest of the lectures I plan to discuss concrete applications and open problems at the interface of probability theory and computer science. As prerequisites, I will only assume familiarity with basic notions on Markov chains.

Most of the course will be based on material from the following references:

1) Avena and Gaudillière: https://arxiv.org/abs/1310.1723 (2013)

2) Avena and Gaudillière: J. Theor. Probab (2017). https://doi.org/10.1007/s10959-017-0771-3
3) Avena, Castell, Mélot and Gaudillière: https://arxiv.org/abs/1707.04616 (2017)
4) Avena, Castell, Mélot and Gaudillière: https://arxiv.org/abs/1702.05992 (2017)

Further, for those interested in understanding deeper connections with statistical mechanics models, here is a good starting reference:  A. Jarai, lecture notes: The uniform spanning tee and related models'', 2009. Avialable at: http://www.maths.bath.ac.uk/~aj276/teaching/USF/USFnotes.pdf

## Location

De Schildkamp, Leerdamseweg 44, 4147 BM Asperen

https://www.schildkamp.nl/

## Programme

 Monday October 30, 2017 12:00 – 12:30 Arrival 12:30 – 13:30 Lunch 13:30 – 14:30 Session 1: Optimization and control of network traffic Jaap Storm: Analysis of a roundabout model Abishek: A novel approach to analyze unsignalized intersections: How to incorporate driver behavior and heterogeneous traffic Liron Ravner: A strategic model of job arrivals to a single machine with earliness and tardiness penalties 14:30 – 14:40 Short break 14:40 – 15:40 Session 2: Network structure Alessandro Garavaglia: Results and open problems on citation networks Debankur Mukherjee: Phase transitions of extremal cuts for random graphs Margriet Oomen: Spatial populations on hierarchical graphs with seed-bank 15:40 – 16:00 Break 16:00 – 17:00 Open problem session 17:00 – 18:00 Research session: work in small groups 18:30 Dinner Tuesday October 31, 2017 07:30 – 09:00 Breakfast 09:00 – 10:15 Mini-course on Expansion properties of networks: Viresh Patel 10:15 – 10:45 Break 10:45 – 12:00 Mini-course on Random walks, forests and network analysis: Luca Avena 12:00 – 13:30 Lunch 13:30 – 14:50 Session 3: (Geometric) Graph Algorithms Jesper Nederlof: Using graph decompositions algorithmically via matrix rank Astrid Pieterse: Optimal data reduction for graph coloring using low-degree polynomials Bart Jansen: TBA Mark de Berg: Geodesic spanners for points on a polyhedral terrain 14:50 – 15:20 Break 15:20 – 18:00 Research session: work in small groups 18:30 Dinner Wednesday November 1, 2017 07:30 – 09:00 Breakfast 09:00 – 10:15 Mini-course on Expansion properties of networks: Viresh Patel 10:15 – 10:45 Break 10:45 – 12:00 Mini-course on Random walks, forests and network analysis: Luca Avena 12:00 – 13:30 Lunch 13:30 – 14:10 Session 4: Dynamics on random graphs Jan Nagel: Random walks in barely supercritical random environments Hakan Guldas: Mixing times for random walks on dynamic random graphs Pieter Kleer: Shapley cost-sharing in clustering games on (random) graphs 14:10 – 14:30 Break 14:30 – 16:30 Research session: work in small groups 16:30 – 21:00 Social activity and dinner Thursday November 2, 2017 07:30 – 09:00 Breakfast 09:00 – 10:15 Mini-course on Expansion properties of networks: Viresh Patel 10:15 – 10:45 Break 10:45 – 12:00 Mini-course on Random walks, forests and network analysis: Luca Avena 12:00 – 13:30 Lunch 13:30 – 14:50 Session 5: Queueing and more Matteo Sfragara: Transition time asymptotics  of queue-based activation protocols in random-access networks Nicos Starreveld: A network of M/M/infty queues with connection failures Fiona Sloothaak: Cascading failures on a connected configuration model 14:50 – 15:20 Break 15:20 – 18:00 Research session: work in small groups 18:30 Dinner Friday November 3, 2017 07:30 – 09:00 Breakfast 09:00 – 10:00 Session 6: Decision making and performance analysis Stella Kapodistria: Decision making in a Bayesian framework Madelon de Kemp: Appointment scheduling Murtuza Ali Abidini: Performance analysis of optical networks 10:00 – 10:30 Break 10:30 – 12:00 Closing session 12:00 – 13:30 Lunch

Details
When: Monday October 30th, 2017  -  Friday November 3rd, 2017
Time: 12:00 - 13:30
Where: De Schildkamp, Asperen
Location

De Schildkamp
Leerdamseweg 44
4147 BM Asperen