2-Lift and Zig-Zag Product for Construction of Expander and Ramanujan Graphs

Learn the 2-Lift technique and Zig-zag product methods for constructing expander graphs and Ramanujan graphs in this 30-minute lecture from NPTEL-NOC IITM. Explore these fundamental graph construction techniques that are essential for creating highly connected sparse graphs with optimal expansion properties. Master the mathematical foundations behind 2-Lift operations, which involve creating new graphs by lifting existing ones, and understand how the Zig-zag product combines smaller graphs to produce larger expander graphs while preserving their expansion properties. Discover how these construction methods enable the systematic creation of Ramanujan graphs, which achieve optimal spectral properties and have significant applications in computer science, coding theory, and network design.