Existence of Graphs with High Girth and High Chromatic Number // TRAIN BRAIN

Existence of Graphs with High Girth and High Chromatic Number

MIT 18.226 Probabilistic Methods in Combinatorics, Fall 2024
Instructor: Yufei Zhao
View the complete course: https://ocw.mit.edu/courses/18-226-probabilistic-methods-in-combinatorics-fall-2022/
YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP61cYB5ymvFiEbIb-wWHfaqO
Application of the probabilistic method in combinatorics to graph theory. Proof of a classic and ingenious result of Erdős that there exists graph with arbitrarily high girth and chromatic number.
License: Creative Commons BY-NC-SA
More information at https://ocw.mit.edu/terms
More courses at https://ocw.mit.edu
Support OCW at http://ow.ly/a1If50zVRlQ
We encourage constructive comments and discussion on OCW’s YouTube and other social media channels. Personal attacks, hate speech, trolling, and inappropriate comments are not allowed and may be removed. More details at https://ocw.mit.edu/comments.

MIT OpenCourseWare

A free and open online publication of educational material from thousands of MIT courses, covering the entire MIT curriculum, ranging from introductory to the most advanced graduate courses. On the OCW website, each course includes a syllabus, instruction...

MIT Milestone Celebration | Keynote Address (480p)

MIT Milestone Celebration | The Future of OCW and Education (480p)

MIT Milestone Celebration | Welcome (480p)

Sujood from Sudan: An Open Learner's Story

Lecture 16: Liquid-Vapor Equilibria in Mixtures; Ideal and Excess Chemical Potentials

Lecture 15: Stratification in Gas and Liquid Mixtures; Liquid-Vapor Spinodal Decomposition

Lecture 19: Affinity and Nonequilibrium Law of Mass Action; Potential Energy Surface

Lecture 25: Thermodiffusive Effects; Multicomponent Transport

Lecture 9: Minimum Work of Partitioning Small Systems; The Gibbs Phase Rule; The Van der Waals Model

Lecture 1: Definitions of System, Property, State, and Weight Process; First Law and Energy

Lecture 2: Second Law and Entropy; Adiabatic Availability; Maximum Entropy Principle

Lecture 24: Relative Diffusion Fluxes; Thermoelectric Effects

Lecture 21: Introduction to Nonequilibrium Theory; Onsager Reciprocity and Maximum Entropy...

Lecture 23: Direct and Cross Effects; General Principles of Entropy Production; The Fourth Law

Lecture 22: Definition of “Heat&Diffusion” Interaction; Diffusive and Convective Fluxes

Lecture 25 video (old)

Lecture 15 video (old)

Lecture 3: Energy vs Entropy Diagrams to Represent Equilibrium and Nonequilibrium States

Lecture 12: Ideal Mixture Behavior; Work from Reversible Mixing; Entropy of Irreversible Mixing

Lecture 7: Availability Functions and the LeChatelier-Braun Principle

Open Learners 105 Jerry

2026 OE Global Conference Announcement

Lotfullah from Afghanistan: An Open Learner's Story

Bounded Differences Inequality (aka Azuma-Hoeffding Inequality)

Large Bipartite Subgraph

Linearity of Expectations

Extremal Set Theory: Sperner's Theorem

Existence of Graphs with High Girth and High Chromatic Number

Extremal Set Theory: Intersecting Families

Lower Bounds to Ramsey Numbers

Markov, Chebyshev, and Chernoff

Threshold for a Random Graph to Contain a Triangle

Independent Sets and Turán's Theorem

Crossing Number Inequality

Nader from Jordan: An Open Learner's Story

Jae-Min from South Korea: An Open Learner's Story

OCW Viajes de aprendizaje: La historia de Tomás

Maria From Brazil: An Open Learner’s Story

Lecture 12: Ethics and Markets

Lecture 22: Auctions, Part 1

Lecture 09: Search, Part 1

Lecture 14: Dynamic Competition, Part 1

Lecture 10: Search, Part 2

Lecture 13: Search, Part 3

Lecture 03: Price Discrimination, Part 1

Lecture 24: Advertising

Lecture 23: Auctions, Part 2

Lecture 15: Dynamic Competition, Part 2

Lecture 25: Online Markets, Part 1 (old)

Lecture 25: Online Markets, Part 1

Lecture 04: Price Discrimination, Part 2

Lecture 18: Strategic Investment, Part 1

Lecture 21: Bounded Rationality, Part 2

Introducing the Open Learners Podcast

Lecture 8: Refractive Index Diagnostics IV

Lecture 19: Nuclear Diagnostics

Lecture 6: Refractive Index Diagnostics II

Lecture 4: Langmuir Probe

Lecture 19: Nuclear Diagnostics (old)

Lecture 23: Thomson Scattering: Advanced

Lecture 1: Introduction to Principles of Plasma Diagnostics

Lecture 2: Magnetics I

Lecture 8: Refractive Index Diagnostics IV (OG old)

Lecture 6: Refractive Index Diagnostics II (OG old)

Lecture 12: Electron Cyclotron Emission

Lecture 13: CECE and Bolometry

Lecture 3: Magnetics II

Lecture 22: Thomson Scattering: Collective

Lecture 11: Radiation

Lecture 1: Introduction to CS and Programming Using Python