Drawing Blanks

Premature Optimization is a Prerequisite for Success

Some important theorems from combinatorics

leave a comment »

In relation to the problems that I recently presented here – the crocodile dinner problem, the crossing lines  problem and its “schoolgirl” formulation – I’d like to reference a few important and beautiful theorems. Unfortunately, combinatorics is one of those branches of mathematics that I have never been exposed to.

Dilworth’s theorem http://en.wikipedia.org/wiki/Dilworth%27s_theorem

König’s theorem http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_(graph_theory)

(you gotta love wikipedia: “Note that, although Kőnig’s name is properly spelled with a double acute accent, the theorem named after him is customarily spelled with an umlaut”)

Marriage theorem http://en.wikipedia.org/wiki/Marriage_theorem , http://www.cut-the-knot.org/arithmetic/marriage.shtml , http://www.cut-the-knot.org/arithmetic/elegant.shtml 

Apparently, all these theorems are equivalent.

And “combinatorics” has lots of irrelevant anagrams 🙂

Advertisements

Written by bbzippo

03/01/2010 at 5:49 am

Posted in math

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: