【グラフ】　ラムゼー理論・定理　【すごいぜー】

以前、ラムゼー理論の具体例を教育TVで見たときに、エレガントだなあと驚きました。

しかし、時は流れ、その感想しか、もはや記憶にありません。
数学板の皆さんは、ラムゼー理論どうですか？

【次のようなカキコ歓迎】
　・ラムゼー理論、ラムゼー定理について
　・他分野（数学、物理、経済、社会学、政治等）への応用
　・ひとりごと
　・その他

よろぴく。

ラムゼーは夭逝した。

>>3
若くして亡くなったの？

ラムゼーってどんな人だったのかな。
数学者のエッセイとか伝記って読んで面白い。
ラマヌジャンとか。
ラムゼーについては読んだことない〜。

ラッセル、ウィトゲンシュタイン、ケインズ、ハーディ等から絶賛を受けながらも27歳で死んだ。

グラフ以外の対象のRamsey理論はどうですか？
整数についてはHales-Jewettの定理とか。

ラムセス

http://www.combinatorics.org/

のDynamic SurveyのDS2, DS13がRamsey理論に関する記事ですね。

雑誌本編にもRamsey理論に関する論文がいくつか出てます。
（vol.1 R8, vol. 5 R7, R19など）

594

384

728

ラムゼー理論に　グラハムとエルデシュは関係しているだろうか。

グラハムはずばりRamsey Theoryという本を書いてるが。

バルゼー提督「火炎直撃砲!」

543

859

108

262

だれかラムゼイ定理を書いてよ。

裸 夢精

ベムラー

502

628

でっかいグラフの辺を２色で塗ると必ず、
一色からなる小さなクリークがあるんだよ。

age

正確には小さい方のサイズを指定すると、
大きいほうが決まるんだけどね。

age

146

hosh

age

299

Ｒ（３、３；２）ってのはわかるけど、Ｒ（４、２；２）はわからない

だれかいませんか

ラムゼー　顔が強そう

だから理屈がごわごわしてんのか。
Ｒ（３、３；２）は３の個数が色の数なんだけど、３や２の意味がごわごわなんすよ。

こんなこともわかんねーのかよ

773

はげ

452

516

Kingはとっくに研究済みじゃ。

talk:>>42 私を呼んだか？

King!　ラムゼー理論について薀蓄を田飲む。

talk:>>44 巨大な数が出てくるらしいのだが、いったいどういう理論なのだ？

>>45
kingも知らないことがあるのだ！

>>46
kingの知っていることなんてないだろ。

talk:>>46 私を呼んだか？
talk:>>47 お前に何が分かるというのか？

>>47
本当のことを知っている藻前に何が解るというのか。
脳を嫁。

talk:>>49 何やってんだよ？

>>49
kingの脳なんて読みたくねーし。

talk:>>51 何だよ？

>>51
玉菌の脳を夜目。

833

100

645

ラムゼイ現象

名前だけでここに書くのもなんだが、
ラムゼイ基数ってどのぐらい大きいの？

>>58
算術的に定義される関数ではけっして到達できない程度に大きい。

>>59
どんな基数から出発して？可算基数からってことだとなんか変だし。

581

ラムゼー理論って規模が大きくなると完全な無秩序は不可能ってこと？

age

591

グラハム数だったっけ

662

ラムゼー理論って何だよ
誰か分かり易く解説してくれ

このスレに書き込んだやつが５人以上集まってオフ会を開いたとすると、
互いに相手のことをＤＱＮだと思っているやつが３人以上いるか、
互いに相手のことをＤＱＮだとは思っていないやつが３人以上いるかの
どちらかである。ということがラムゼー理論から導かれるのだよ。

221

140

695

二年。

age

975



＞＞68それはラムゼイ理論使わなくてもわかると思いますが……

　　　　／￣￣￣￣＼
　　　（　　人＿＿＿＿）
　　　 |ミ/　　ー◎-◎-）　 　　哀悼！塩沢ときさん(泣)
　　　（６　　　　：(_　_)：）　　漏れたちは君を永遠に忘れないぜ！！　
　　 ノ|/　∴　ノ：　３ ：ﾉ､ 　　以上、越後のパク・ヨンハ浮須田之助でした♪
　/ 　 ＼＿＿＿＿_.ノ　 ヽ　　　　
/　　　,ｨ -っ､　　　　　　　 ヽ
|　 ／　､__ う　人 　･　,.y　 i
| 　　　/　　　　　　 ￣　|　　|
ヽ､__ノ 　　　　　　　　　ﾉ　 ﾉ
　　|　　　　　　x　　　 9　 /
　　 | 　　ヽ､_　　_,ノ　彡ｲ
　　　| 　　　　（U）　　　　|

524

　／￣￣￣￣＼
　　　（　　人＿＿＿＿）
　　　 |ミ/　　ー◎-◎-）　 　　哀悼！塩沢ときさん(泣)
　　　（６　　　　：(_　_)：）　　漏れたちは君を永遠に忘れないぜ！！　
　　 ノ|/　∴　ノ：　３ ：ﾉ､ 　　以上、越後のパク・ヨンハ浮須田之助でした♪
　/ 　 ＼＿＿＿＿_.ノ　 ヽ　　　　
/　　　,ｨ -っ､　　　　　　　 ヽ
|　 ／　､__ う　人 　･　,.y　 i
| 　　　/　　　　　　 ￣　|　　|
ヽ､__ノ 　　　　　　　　　ﾉ　 ﾉ
　　|　　　　　　x　　　 9　 /
　　 | 　　ヽ､_　　_,ノ　彡ｲ
　　　| 　　　　（U）　　　　|

431

１．未知のラムゼー数を２〜３個見つける
２．既知のラムゼー数いくつかと上記１で見つけたラムゼー数に共通する性質で未知のものを見つける
３．上記２の未知の性質について２〜３回論文を書く

こうすると博士号取れるって聞いたんですけどどの程度ホントの話ですか？

68 ：１３２人目の素数さん：2006/09/13(水) 15:29:02
このスレに書き込んだやつが５人以上集まってオフ会を開いたとすると、
互いに相手のことをＤＱＮだと思っているやつが３人以上いるか、
互いに相手のことをＤＱＮだとは思っていないやつが３人以上いるかの
どちらかである。ということがラムゼー理論から導かれるのだよ。

おいおい、だれもつっこまないのかよ。
5人じゃなくて6人だろ？
R(2,2,3)=6

６８はばか

三年二日十八時間。

367

もっと凄い理論は？一般濃度の集合でも通用する様な

>>87
無限型のラムゼー理論ではそういうの結構あるよ

118

グラフ理論スレのファンだったのにいつのまにか消滅してて悲しかったから後釜としてのこのスレ応援age

age

Ramsey theory入手したぜ

R(3,4)=9の証明わかる人いませんか？

Kingまだ〜

Reply:>>94 グラフとはグラフ理論のものか。

ピカーッ　Ｋ１００Ｄ修理失敗感電バカ☆　100w
　　　　　　　　　　　　ζ　　 　 - ,,
　　　　　　　　　――――――ーーヽ　　　　　　〜〜〜∽プワーン　 　　　　　
　　 　　　　／　　　　　　　　　　　＼　　2×2＝8　2×6＝56...　
　　 　　／　　　　　　　 　　　 ＼　
　 i　　　　　　　　　 　　Ｕ !　 〜〜∽　ﾌﾟｰン
　 　 　i　Ｕ 　 i
　 　　 i　　　 　''´　　　　♯ !　 　　打倒nikon　えーあいでぃーえす★
　 　　　j　　 ' ´　　　 ﾉ (　　　　ヽ　| 　　うひゃ〜り♪
　 　 /　　,,=━━・!'　,ﾉ━＝=　! ﾉ 　＜ヲ、おまえ等,ｦ・ｦーﾚ様が
　 　 ヽ |　　’ﾆﾝniii､　:::::i/ｨ7iii=　 i ) 　むぎわら帽子被ってる
てi iヽ　　 ^'　~　　　　　-'　　/｝　　　のはな、禿げ隠しだ
　　｀i_ 　 ､ ＼　ｕ　 　　 　i_　　　　l_j ついでに名無し隠れだよ！
　 　　｀┐　i　　　　／(,,,　,n 〉　　 /＼＼ 　　
　￣￣へ　　　　! '　　　T'' 　　　l |　　＼　　つまり普段はｶｯｺｲｲ
　未 ｜　　!　i　　　　ン=ｪｪi) i　ｿ　)　あ♯　　　禿げ　なんだぜ！
　明　|　 i´＼!　,,　-ｪ｀､＿ﾝ ﾉノ　〈　ら.【貧困】だがカタログ山積み　
　　　|　 |　　＼＼,,　｀―''´／/　　|し　コンデジ偽情報聞いチャリイ　　　　
　　♯|　 つ　 　!､＿'''''''''''''　 /　　 コテ復帰してえよヲヲーン　
　　　　　●北九州市　ひがし小倉尻釜男 ：　ﾀﾞﾒカルターゲリケーン○盛　59才　　　　　　　
(ウソ夜勤)生活保護　 泣かせます、万年3：30未明投稿　被害妄想・認定癖ありの問題
人格障害男　
　
http://love6.2ch.net/test/read.cgi/chiri/1204007635/701-751　　
http://hobby11.2ch.net/test/read.cgi/dcamera/1211333017/901-1000
http://hobby11.2ch.net/test/read.cgi/dcamera/1212718734/1-100　
★http://society6.2ch.net/test/read.cgi/giin/1202214441/607-616
　↑　隔離病棟
http://img5.gazo-ch.net/bbs/5/img/200804/30504.jpg (本人近影　ｸﾞﾛ危険!

>>93
R(3, 4)≦9の証明：

1, 2, ..., R(3, 4)-1 を頂点とする完全グラフが色 1, 2 により、
色1 で塗られる K_3 および 色2 で塗られる K_4 をもたないように塗り分けられたと仮定する。

辺(1, i) (2≦i≦9) が色 j で塗られる i の集合を S_j (j=1, 2) と書く。

i, j∈S_1 ならば、仮定より (i, j) は色2 で塗られなければならない。
つまり、S_1 に属するの頂点同士を結ぶ辺は全て 色2 で塗られる。
色2 で塗られる K_4 をもたないから、|S_1|≦3 である。

ここで、|S_2|≧5を仮定する。

S_2に属する頂点から5つ選び 2, 3, 4, 5, 6 と再度記す。
色2 で塗られる K_4 をもたないから、ある辺 (たとえば (2, 3) )は色1で塗られなければならない。
同様に 3, 4, 5, 6 の二つを結ぶ辺の一つ (たとえば (3, 4) )は色1で塗られなければならない。

仮定より 2, 3, 4 の二つを結ぶ辺が全て色1で塗られることはないから、 (2, 4) は色2で塗られる。
(4, 5) が色2で塗られると、 1, 2, 4, 5 は色2で塗られる K_4 となる。よって (4, 5) は色1で塗られる。
上と同様に (3, 5) は色2で塗られ、 (5, 6) は色1で塗られることがわかる。

今、(4, 6) が色1で塗られていると仮定すると、4, 5, 6 は色1で塗られる K_3 となり、仮定に反する。
しかし (4, 6) が色2で塗られていると仮定すると 1, 2, 4, 6 は色2で塗られる K_4 となり、仮定に反する。

これにより、|S_1|≦3, |S_2|≦4 が示された。これは R(3, 4)-1≦1+3+4 、つまり R(3, 4)≦9 を与える。

R(3, 4)≧9 の証明はすぐには思いつかないorz

>>97
http://science6.2ch.net/test/read.cgi/math/1216746508/
この議論を一般化すると、
R(m-1,n), R(m,n-1) が偶数のとき、R(m,n)≦R(m-1,n)+R(m,n-1)-1 がわかる。

R(3,4)≧9 は 8 頂点からなる反例を作ればよいが、やってみれば結構簡単にできる。

>>99
http://science6.2ch.net/test/read.cgi/math/1216746508/512
だった。

996

age

568

033

922

四年四時間。

何が

なんなんだこのクソスレは

262

933

452

802

267

349

☻

985

218

796

957