Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Building Ramanujan Graphs

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 discusses the challenges of using the probabilistic method to construct Ramanujan graphs and proposes a solution involving polynomials. The instructor explains the concept of expander graphs and their role in solving NP-hard problems. The lecture covers topics such as belief negotiation, continuous and discrete distances, and the properties of Ramanujan graphs. It also delves into the interplay between eigenvalues and eigenvectors of matrices, emphasizing the importance of tracking all eigenvalues. The presentation concludes with a detailed analysis of interlacing properties and characteristic polynomials, showcasing their significance in graph theory and linear algebra.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

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.

Color

Color (American English) or colour (Commonwealth English) is the visual perception based on the electromagnetic spectrum. Though color is not an inherent property of matter, color perception is related to an object's light absorption, reflection, emission spectra and interference. For most humans, color are perceived in the visible light spectrum with three types of cone cells (trichromacy). Other animals may have a different number of cone cell types or have eyes sensitive to different wavelength, such as bees that can distinguish ultraviolet, and thus have a different color sensitivity range.

Color theory

In the visual arts, color theory is the body of practical guidance for color mixing and the visual effects of a specific color combination. Color terminology based on the color wheel and its geometry separates colors into primary color, secondary color, and tertiary color. The understanding of color theory dates to antiquity. Aristotle (d. 322 BCE) and Claudius Ptolemy (d. 168 CE) already discussed which and how colors can be produced by mixing other colors. The influence of light on color was investigated and revealed further by al-Kindi (d.

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).

Color blindness

Color blindness or color vision deficiency (CVD) is the decreased ability to see color or differences in color. It can impair tasks such as selecting ripe fruit, choosing clothing, and reading traffic lights. Color blindness may make some academic activities more difficult. However, issues are generally minor, and people with colorblindness automatically develop adaptations and coping mechanisms. People with total color blindness (achromatopsia) may also be uncomfortable in bright environments and have decreased visual acuity.

Related lectures (55)

Spectral Graph Theory: Introduction

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

Matrices and Networks

Explores the application of matrices and eigendecompositions in networks.

Cheeger's Inequalities

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

Spectral Clustering: Theory and Applications

Explores spectral clustering theory, eigenvalue decomposition, Laplacian matrix, and practical applications in identifying clusters.

Linear Algebra: Canonical Basis