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

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