Lecture

Interlacing Families and Ramanujan Graphs

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

MATH-467: Probabilistic methods in combinatorics

The 'probabilistic method' is a fundamental tool in combinatorics. The basic idea is as follows: to prove that an object (for example, graph) with certain properties exists, it suffices to prove that if the object is chosen at random, then it has the desir ...

Description

This lecture covers the concept of interlacing families of polynomials, focusing on 1-sided Ramanujan graphs. The instructor explains the properties of these graphs, such as d-regularity and eigenvalues. The lecture delves into two approaches for constructing interlacing families, including the use of matching polynomials. The connection between characteristic polynomials and matching polynomials in trees and graphs is explored, along with theorems by Godsil and Gutman. The lecture concludes with discussions on weighted adjacency matrices and the significance of real roots in matching polynomials.

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

Color space

A color space is a specific organization of colors. In combination with color profiling supported by various physical devices, it supports reproducible representations of color - whether such representation entails an analog or a digital representation. A color space may be arbitrary, i.e. with physically realized colors assigned to a set of physical color swatches with corresponding assigned color names (including discrete numbers in - for example - the Pantone collection), or structured with mathematical rigor (as with the NCS System, Adobe RGB and sRGB).

Line segment

In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between its endpoints. A closed line segment includes both endpoints, while an open line segment excludes both endpoints; a half-open line segment includes exactly one of the endpoints. In geometry, a line segment is often denoted using a line above the symbols for the two endpoints (such as ).

Line (geometry)

In geometry, a line is an infinitely long object with no width, depth, or curvature. Thus, lines are one-dimensional objects, though they may exist embedded in two, three, or higher dimensional spaces. The word line may also refer to a line segment in everyday life that has two points to denote its ends (endpoints). A line can be referred to by two points that lie on it (e.g. ) or by a single letter (e.g. ).

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Related lectures (64)

Building Ramanujan Graphs

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

Pseudorandomness: Theory and Applications

Explores pseudorandomness theory, AI challenges, pseudo-random graphs, random walks, and matrix properties.

Interlacing Families and Ramanujan Graphs

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

Spectral Graph Theory: Introduction

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

Expander Graphs: Properties and Eigenvalues

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