1
Graphs: introduction and basic spectral theory
▶
1.1
Basic graph theory
▶
1.1.1
Darts
1.1.2
Subgraphs
1.1.3
Finiteness
1.1.4
Locally finite graph, degree and regularity
1.1.5
Bipartiteness
1.1.6
Walks and reachability
1.1.7
Connectedness
1.1.8
Morphisms between graphs
1.1.9
Rooted graphs
1.1.10
Nonbacktracking walks and reduction
1.1.11
Universal cover
1.1.12
Metric
1.1.13
Diameter
1.2
Space of functions on a graph
▶
1.2.1
Constant fonctions
1.2.2
Indicator functions
1.2.3
Locally constant functions
1.3
Adjacency operator
▶
1.3.1
Definition of the adjacency operator and action on constants
1.3.2
Norm of the adjacency operator
1.3.3
Adjacency operator is self-adjoint
1.3.4
From adjacency operator to graph
2
Spectral theory of regular graphs
▶
2.1
Trivial eigenvalues
2.2
The spectral gap
2.3
The infinite regular tree
3
Random permutation graphs
▶
3.1
Permutation graphs
3.2
Random permutations
3.3
Words in random permutation matrices
▶
3.3.1
Statement of the result and notations
4
Analysis prerequisites
▶
4.1
Markov inequalities
4.2
Chebyshev polynomials
4.3
Compactly supported distributions
5
Weak and strong convergence
▶
5.1
The free group and its reduced algebra
Dependency graph
Friedman’s theorem: a new proof using strong convergence
Laura Monk
1
Graphs: introduction and basic spectral theory
1.1
Basic graph theory
1.1.1
Darts
1.1.2
Subgraphs
1.1.3
Finiteness
1.1.4
Locally finite graph, degree and regularity
1.1.5
Bipartiteness
1.1.6
Walks and reachability
1.1.7
Connectedness
1.1.8
Morphisms between graphs
1.1.9
Rooted graphs
1.1.10
Nonbacktracking walks and reduction
1.1.11
Universal cover
1.1.12
Metric
1.1.13
Diameter
1.2
Space of functions on a graph
1.2.1
Constant fonctions
1.2.2
Indicator functions
1.2.3
Locally constant functions
1.3
Adjacency operator
1.3.1
Definition of the adjacency operator and action on constants
1.3.2
Norm of the adjacency operator
1.3.3
Adjacency operator is self-adjoint
1.3.4
From adjacency operator to graph
2
Spectral theory of regular graphs
2.1
Trivial eigenvalues
2.2
The spectral gap
2.3
The infinite regular tree
3
Random permutation graphs
3.1
Permutation graphs
3.2
Random permutations
3.3
Words in random permutation matrices
3.3.1
Statement of the result and notations
4
Analysis prerequisites
4.1
Markov inequalities
4.2
Chebyshev polynomials
4.3
Compactly supported distributions
5
Weak and strong convergence
5.1
The free group and its reduced algebra