Skip to content
All tags

#pigeonhole-principle

2 posts
learningdeep-diveReading Stanford CS103 Mathematical Foundations of Computing

Walks, Graph Complements, and the Pigeonhole Principle | Stanford CS103 Lecture 10

Starting with walks, paths, cycles, and components, this lecture proves that a graph or its complement is connected and develops the pigeonhole principle through degrees and monochromatic triangles.

#cs103#graph-theory#pigeonhole-principle#discrete-mathematics
learningdeep-diveReading Stanford CS103 Mathematical Foundations of Computing

Generalized Pigeonhole, Ramsey Theory, and Average Load | Stanford CS103 Lecture 11

Use the generalized pigeonhole principle to force a monochromatic triangle at a six-person party, then solve a movie-preference puzzle through average load and contradiction.

#cs103#graph-theory#pigeonhole-principle#ramsey-theory