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 socalled 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 closelyrelated 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 nvertex graph is the smallest number c such that for every subset S of vertices with S \leq n/2, one must delete at least cS 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:
http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
Random walks, forests and network analysis
Lecturer: Luca Avena
In this minicourse 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 socalled ``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. looperased walks, integrable systems, dimer models, sandpiles, Gaussian free fields, percolation, determinantal and coalescencefragmentation 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/s1095901707713
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
Programme
Monday 30 October 

12:00 – 13:30 
Lunch 
13:30 – 14:30 
Session 1: presentations 
14:30 – 14:40 
Short break 
14:40 – 15:40 
Session 2: presentations 
15:40 – 16:00 
Break 
16:00 – 17:00 
Open problem session 
17:00 – 18:00 
Research session: work in small groups 




Tuesday 31 October 

09:00 – 10:15 
Minicourse on Expansion properties of networks: Viresh Patel 
10:15 – 10:45 
Break 
10:45 – 12:00 
Minicourse on Random walks, forests and network analysis: Luca Avena 
12:00 – 13:30 
Lunch 
13:30 – 14:50 
Session 3: presentations 
14:50 – 15:20 
Break 
15:20 – 18:00 
Research session: work in small groups 




Wednesday 1 November 

09:00 – 10:15 
Minicourse on Expansion properties of networks: Viresh Patel 
10:15 – 10:45 
Break 
10:45 – 12:00 
Minicourse on Random walks, forests and network analysis: Luca Avena 
12:00 – 13:30 
Lunch 
13:30 – 14:30 
Research talks, Session 4: presentations 
14:10 – 14:30 
Break 
14:30 – 16:30 
Research session: work in small groups 
16:30 – 
Social event 
Thursday 2 November 

09:00 – 10:15 
Minicourse on Expansion properties of networks: Viresh Patel 
10:15 – 10:45 
Break 
10:45 – 12:00 
Minicourse on Random walks, forests and network analysis: Luca Avena 
12:00 – 13:30 
Lunch 
13:30 – 14:50 
Session 5: presentations 
14:50 – 15:20 
Break 
15:20 – 18:00 
Research session: work in small groups 




Friday 3 November 

09:00 – 10:00 
Session 6: presentations 
10:00 – 10:30 
Break 
10:30 – 12:00 
Closing session 
12:00 – 13:30 
Lunch 