6人の人々がいるとき、互いに知り合いか、互いに見知らぬか、どちらかを満たす3人が存在しなければならない。

互いに知り合いのa人か、互いに見知らぬb人かを満たすためにはどれだけ多くの人々が必要であろうか？

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

その必要とされる最小の数をR(a,b)と記す。

R(3,3)=6

R(a,2)=a

R(4,4)=18

R(5,5)は知られていない。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

エルデシュとセケレシュは

R(a,b)<=C(a+b-2,a-1)であることを示した。

R(3,3)<=C(4,2)=4

R(a,2)<=C(a,a-1)=a

R(4,4)<=C(6,3)=20

R(5,5)<=C(8,4)=70

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ファン・リント、ウィルソンの「組み合わせ論」では

R(3,3)=6→N(3,3;2)=6となっている。

N(p,q;2)≦N(p-1,q;2)+N(p,q-1;2)

N(p,q;2)≦C(p+q-2,p-1)

N(p,p;2)≦C(2p-2,p-1)≦2^(2p-2)

2^(p/2)≦N(p,p;2)≦C(2p-2,p-1)≦2^(2p-2)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

N(4,4;2)=18

N(3,5;2)=14

N(3,6;2)=18

N(3,7;2)=23

N(3,8;2)=28

N(3,9;2)=36

N(4,5;2)=25

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝