A Simple Visual Proof of a Powerful Idea in Graph Theory


Via Nautilus.

recent advance in geometry makes heavy use of Ramsey’s theorem, an important idea in another field—graph theory. Ramsey’s theorem states that in any graph where all points are connected by either red lines or blue lines, you’re guaranteed to have a large subset of the graph that is completely uniform—that is, either all red or all blue.

Equivalently, you can go the other way: Pick how big you want your uniform subset to be. Ramsey’s theorem states that somewhere out there there’s a graph in which a subset of that size must arise.

It’s not obvious why this is true. Why can’t there be a graph where lines of different colors remain completely jumbled together?

I put this question to Jonathan Jedwab, a mathematician at Simon Fraser University in British Columbia. He responded with this example, which provides a graphical intuition for why the theorem is true.

Read more.

Join 4,000+ makers on Adafruit’s Discord channels and be part of the community! http://adafru.it/discord

Learn “How Computers Work” with Bill Gates, Ladyada and more – From Code.org !

CircuitPython in 2018 – Python on Microcontrollers is here!

Have an amazing project to share? Join the SHOW-AND-TELL every Wednesday night at 7:30pm ET on Google+ Hangouts.

Join us every Wednesday night at 8pm ET for Ask an Engineer!

Follow Adafruit on Instagram for top secret new products, behinds the scenes and more https://www.instagram.com/adafruit/

Maker Business — Prototyping PCBs with Particle, a guide from a pro in the field #makerbusiness

Wearables — From mat to hat

Electronics — Even lower power!

Biohacking — Nectome’s Brain Preservation and Backup Service Plan

Python for Microcontrollers — Scott ([email protected]) on the Amp Hour podcast!

Get the only spam-free daily newsletter about wearables, running a "maker business", electronic tips and more! Subscribe at AdafruitDaily.com !

No Comments

No comments yet.

Sorry, the comment form is closed at this time.