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
The master inequality: for polynomials
▶
4.1
Markov inequalities
4.2
Non-commutative polynomials with matrix coefficients
4.3
The Master inequality for polynomials
▶
4.3.1
Proof for large values
4.3.2
Bound on the coefficients
4.3.3
Proof for small values
4.4
Special cases
5
The master inequality: extension to smooth functions
▶
5.1
Chebyshev polynomials
5.2
Compactly supported distributions
▶
5.2.1
Support of a distribution
5.2.2
Characterisation of compactly supported distributions
5.2.3
Extension from polynomials to smooth functions
5.3
Proof of the Master inequality II
6
Proof of Friedman’s theorem
▶
6.1
The free group and its reduced algebra
6.2
Support of a real distribution
▶
6.2.1
Stieltjes transform
6.2.2
Spectral radius and support
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
The master inequality: for polynomials
4.1
Markov inequalities
4.2
Non-commutative polynomials with matrix coefficients
4.3
The Master inequality for polynomials
4.3.1
Proof for large values
4.3.2
Bound on the coefficients
4.3.3
Proof for small values
4.4
Special cases
5
The master inequality: extension to smooth functions
5.1
Chebyshev polynomials
5.2
Compactly supported distributions
5.2.1
Support of a distribution
5.2.2
Characterisation of compactly supported distributions
5.2.3
Extension from polynomials to smooth functions
5.3
Proof of the Master inequality II
6
Proof of Friedman’s theorem
6.1
The free group and its reduced algebra
6.2
Support of a real distribution
6.2.1
Stieltjes transform
6.2.2
Spectral radius and support