Ramsey numbers

[109]

How many people do you need to invite to a party to ensure that a subset of them, denoted 'm', will know each other and another subset of them, denoted 'n', will not know each other and so be forced to mingle? The required number, R(m,n), is a two color Ramsey number.

If an alien species threatened to destroy the human race unless we could tell them the R(5,5) Ramsey number, our best bet would be to put humankind's best minds to work on the problem, since we should have a chance of getting it.

But if the aliens asked for R(6,6), our best bet would be to launch an immediate all-out strike against the aliens since the calculation would be too difficult to contemplate.

P.S. R(5,5) is still unknown, even today, although mathematicians think it lies between 43 and 49.

Comments

[plakhov.livejournal.com]

and another subset of them

OR another subset of them?

[109.livejournal.com]

эээ... не знаю. я же это скопировал, а не сам написал.

[sasha-gil.livejournal.com]

Мне эта область (комбинаторики? - я имею в виду http://en.wikipedia.org/wiki/Ramsey_theory) попалась с год назад на глаза в некоей философско-математической книжке, которая выложена онлайн. Там была сформулирована некоя теорема из этой области, которая при наличии в аксиоматике аксиомы выбора (то есть в "мэйнстримовой математике") верна и доказуема, а при наличии альтернативной аксиомы (которая тоже makes sense и позволяет доказывать массу вещей из "мэйнстримовой математики") не то чтобы недоказуема, но просто неверна. Если я не напутал, сейчас тот фрагмент вспоминая. Дома есть закладка на книжку.