On Perfectly Friendly Bisections of Random Graphs
Offered By: Simons Institute via YouTube
Course Description
Overview
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 realMirí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