YoVDO

Explicit Near-Fully X-Ramanujan Graphs

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Combinatorics Courses Graph Theory Courses Spectral Graph Theory Courses

Course Description

Overview

Explore the concept of explicit near-fully X-Ramanujan graphs in this 22-minute IEEE conference talk by Ryan O'Donnell and Xinyu Wu from Carnegie Mellon University. Delve into the fascinating world of finite graphs that resemble infinite graphs, and discover how random finite graphs can exhibit similar properties. Examine the concept of d-regular trees and learn about graphs that spectrally resemble infinite structures. Investigate the role of adjacency matrices and formal polynomials in graph theory. Gain insights into the approach using finite permutations and matrix-weighted polynomials. Conclude with a discussion of the presenters' results and potential open problems in this field of study.

Syllabus

Intro
Ramanujan graphs: Finite graphs which resemble infinite graphs
Random finite graphs which resemble infinite graphs
Beyond d-regular trees
Spectrally resembling infinite graphs
Adjacency matrix
Consider the formal polynomial
Approach: finite permutations
Matrix-weighted polynomials
Our results
Open problems


Taught by

IEEE FOCS: Foundations of Computer Science

Tags

Related Courses

Aplicaciones de la teoría de grafos a la vida real
Miríadax
Aplicaciones de la Teoría de Grafos a la vida real
Universitat Politècnica de València via UPV [X]
Introduction to Computational Thinking and Data Science
Massachusetts Institute of Technology via edX
Genome Sequencing (Bioinformatics II)
University of California, San Diego via Coursera
Algorithmic Information Dynamics: From Networks to Cells
Santa Fe Institute via Complexity Explorer