Concept

Expander graph

Related lectures (31)

Expander Graphs: Properties and Eigenvalues

Explores expanders, Ramanujan graphs, eigenvalues, Laplacian matrices, and spectral properties.

Ramanujan Graphs: Generating Functions and Expander Graphs

Explores Ramanujan graphs, generating functions, non-backtracking walks, and expander graphs in relation to NP-hard problems.

Pseudorandomness: Expander Mixing Lemma

Explores pseudorandomness and the Expander Mixing Lemma in the context of d-regular graphs.

Sparsest Cut and Concurrent Flow

Covers sparsest cut, NP-completeness, Bougains Theorem, and concurrent flow in graphs.

Building Ramanujan Graphs

Explores the construction of Ramanujan graphs using polynomials and addresses challenges with the probabilistic method.

Bethe Free Entropy

Covers the computation of Bethe free entropy and the interpretation of messages between variables and factors.

Sparsest Cut: ARV Theorem

Covers the proof of the Bourgain's ARV Theorem, focusing on the finite set of points in a semi-metric space and the application of the ARV algorithm to find the sparsest cut in a graph.

The Increment Theorem: Understanding Derivatives

Explores the increment theorem and derivatives in calculus, focusing on polygonal valleys and curve traces.

Cheeger's Inequalities

Covers Cheeger's inequalities and the combinatorial properties of graphs.

Bipartite Graphs: Independent Sets

Explores bipartite graphs, independent sets, Shearer's Lemma, labeled graphs, and entropy analysis.

Graph Alignment: Wasserstein-based

Discusses challenges in comparing non-Euclidean data, proposing a Laplacian-based solution for graph alignment and exploring optimal transport for graph distance computation.

Interlacing Families and Ramanujan Graphs

Explores interlacing families of polynomials and 1-sided Ramanujan graphs, focusing on their properties and construction methods.

Interlacing Families and Ramanujan Graphs

Explores interlacing families, Ramanujan graphs, and their construction using signed adjacency matrices.

Binary Relations and Cartesian Products

Explores binary relations, Cartesian products, and applications between sets, emphasizing their properties and significance.

Graphical Basics: MATLAB and Octave for Beginners

Covers the basics of creating 2D graphs using MATLAB and Octave.

Isogenic Graphs: Spectral Analysis and Mathematical Applications

Explores isogenic graphs, spectral properties, and mathematical applications in modular forms and cryptography.

Epidemics and Bootstrap Percolation in Square Lattice

Explores epidemics spread models and Bootstrap Percolation in square lattice networks, focusing on the Kolmogorov equation and probability generating functions.

Belief Propagation on Graphs

Covers belief propagation on graphs, exploring computation challenges and heuristics, focusing on sparse random graphs' loop properties.

Spectral Graph Theory: Introduction

Introduces Spectral Graph Theory, exploring eigenvalues and eigenvectors' role in graph properties.

Pseudo Randomness in Graphs

Explores pseudo randomness in graphs using eigenvalues and polynomials, emphasizing the significance of bunched roots and common interlacers.