YoVDO

On Perfectly Friendly Bisections of Random Graphs

Offered By: Simons Institute via YouTube

Tags

Graph Theory Courses Combinatorics Courses Probabilistic Methods Courses

Course Description

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore a rigorous mathematical analysis of random graph partitioning in this 57-minute lecture by Mehtaab Sawhney from MIT. Delve into the proof of a constant γ's existence in G(n,1/2) graphs, demonstrating high-probability equipartitions where vertices have (γ - ε)\sqrt{n} more neighbors in their own part. Examine the application of Boolean function tools to prove vertex-isoperimetry expansion for transitive graph subsets, and understand how this boosts constant probability results to high probability. Gain insights into advanced graph theory concepts, including perfectly friendly bisections and their implications for random graph structures.

Syllabus

On Perfectly Friendly Bisections of Random Graphs


Taught by

Simons Institute

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