Ramsey Number Graph

Ramsey's theorem and Graph theorem

The research about Ramsey Numbers.

In combinatorial mathematics, Ramsey's theorem states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)

Ramsey's theorem is a foundational result in combinatorics. The first version of this result was proved by F. P. Ramsey. This initiated the combinatorial theory now called Ramsey theory, that seeks regularity amid disorder: general conditions for the existence of substructures with regular properties. In this application it is a question of the existence of monochromatic subsets, that is, subsets of connected edges of just one colour.

An extension of this theorem applies to any finite number of colours, rather than just two. More precisely, the theorem states that for any given number of colours, c, and any given integers n1, …, nc, there is a number, R(n1, …, nc), such that if the edges of a complete graph of order R(n1, ..., nc) are coloured with c different colours, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all colour i. The special case above has c = 2 (and n1 = r and n2 = s).

m	n	R(m,n)	Reference
3	3	6	Greenwood and Gleason 1955
3	4	9	Greenwood and Gleason 1955
3	5	14	Greenwood and Gleason 1955
3	6	18	Graver and Yackel 1968
3	7	23	Kalbfleisch 1966
3	8	28	McKay and Min 1992
3	9	36	Grinstead and Roberts 1982
3	10	[40, 43]	Exoo 1989c, Radziszowski and Kreher 1988
3	11	[46, 51]	Radziszowski and Kreher 1988
3	12	[52, 59]	Exoo 1993, Radziszowski and Kreher 1988, Exoo 1998, Lesser 2001
3	13	[59, 69]	Piwakowski 1996, Radziszowski and Kreher 1988
3	14	[66, 78]	Exoo (unpub.), Radziszowski and Kreher 1988
3	15	[73, 88]	Wang and Wang 1989, Radziszowski (unpub.), Lesser 2001
3	16	[79, 135]	Wang and Wang 1989
3	17	[92, 152]	Wang et al. 1994
3	18	[98, 170]	Wang et al. 1994
3	19	[106, 189]	Wang et al. 1994
3	20	[109, 209]	Wang et al. 1994
3	21	[122, 230]	Wang et al. 1994
3	22	[125, 252]	Wang et al. 1994
3	23	[136, 275]	Wang et al. 1994
4	4	18	Greenwood and Gleason 1955
4	5	25	McKay and Radziszowski 1995
4	6	[35, 41]	Exoo (unpub.), McKay and Radziszowski 1995
4	7	[49, 61]	Exoo 1989a, Mackey 1994
4	8	[56, 84]	Exoo 1998, Exoo 2002
4	9	[73, 115]	Radziszowski 1988, Mackey 1994
4	10	[92, 149]	Piwakowski 1996, Mackey 1994, Harboth and Krause 2003
4	11	[97, 191]	Piwakowski 1996, Spencer 1994, Burr et al. 1989
4	12	[128, 238]	Su et al. 1998, Spencer 1994
4	13	[133, 291]	Xu and Xie 2002
4	14	[141, 349]	Xu and Xie 2002
4	15	[153, 417]	Xu and Xie 2002
4	16	[153, 815]
4	17	[182, 968]	Luo et al. 2001
4	18	[182, 1139]
4	19	[198, 1329]	Luo et al. 2002
4	20	[230, 1539]	Su et al. 1999
4	21	[242, 1770]	Su et al. 1999
4	22	[282, 2023]	Su et al. 1999
5	5	[43, 49]	Exoo 1989b, McKay and Radziszowski 1995
5	6	[58, 87]	Exoo 1993, Walker 1971
5	7	[80, 143]	CET, Spencer 1994
5	8	[101, 216]	Piwakowski 1996, Spencer 1994, Harborth and Krause 2003
5	9	[125, 316]	Exoo 1998, Haanpää 2000
5	10	[143, 442]	Exoo 1998, Mackey 1994
5	11	[157, 1000]	Exoo 1998, Xiaodong et al. 2004
5	12	[181, 1364]	Exoo 1998
5	13	[205, 1819]	Exoo 1998, Xiaodong et al. 2004
5	14	[233, 2379]	Exoo 1998, Xiaodong et al. 2004
5	15	[261, 3059]	Su et al. 2002, Xiaodong et al. 2004
5	16	[278, 3875]	Luo et al. 2001
5	17	[284, 4844]	Exoo 2002
5	18	[284, 5984]
5	19	[338, 7314]	Su et al. 1999
5	20	[380, 8854]	Luo et al. 2001
5	21	[380, 10625]
5	22	[422, 12649]	Luo et al. 2000
5	23	[434, 14949]	Luo et al. 2000
5	24	[434, 17549]
5	25	[434, 20474]
5	26	[464, 23750]
6	6	[102, 165]	Kalbfleisch 1965, Mackey 1994
6	7	[113, 298]	Exoo 1998, Xu and Xie 2002
6	8	[127, 495]	Exoo 1998, Xu and Xie 2002
6	9	[169, 780]	Exoo 1998, Mackey 1994, Xiaodong et al. 2004
6	10	[179, 1171]	Xu and Xie 2002
6	11	[253, 3002]	Xu and Xie 2002
6	12	[262, 4367]	Xu and Xie 2002
6	13	[317, 6187]	Xu and Xie 2002, Xiaodong et al. 2004
6	14	[317, 8567]	Xu and Xie 2002
6	15	[401, 11627]	Su et al. 2002, Xiaodong et al. 2004
6	16	[434, 15503]	Su et al. 2002
6	17	[548, 20348]	Su et al. 2002
6	18	[614, 26333]	Su et al. 2002
6	19	[710, 33648]	Su et al. 2002
6	20	[878, 42503]	Su et al. 2002
6	21	[878, 53129]
6	22	[1070, 65779]	Su et al. 2002
7	7	[205, 540]	Hill and Irving 1982, Giraud 1973
7	8	[216, 1031]	Xu and Xie 2002
7	9	[233, 1713]	Huang and Zhang 1998, Xiaodong and Zheng 2002
7	10	[232, 2826]	Mackey 1994
7	11	[405, 8007]	Xu and Xie 2002, Xiaodong and Zheng 2002
7	12	[416, 12375]	Xu and Xie 2002
7	13	[511, 18563]	Xu and Xie 2002
7	14	[511, 27131]
7	15	[511, 38759]
7	16	[511, 54263]
7	17	[628, 74612]	Xu and Xie 2002
7	18	[722, 100946]	Xu and Xie 2002
7	19	[908, 134595]	Su et al. 2002
7	20	[908, 177099]
7	21	[1214, 230229]	Su et al. 2002
8	8	[282, 1870]	Burling and Reyner 1972, Mackey 1994
8	9	[317, 3583]	Radziszowski 2002, Xiaodong et al. 2004
8	10	[377, 6090]	Xu and Xie 2002, Huang and Zhang 1998, Xiaodong et al. 2004
8	11	[377, 19447]
8	12	[377, 31823]
8	13	[817, 50387]	Xu and Xie 2002, Xiaodong et al. 2004
8	14	[817, 77519]
8	15	[861, 116279]	Xu and Xie 2002, Xiaodong et al. 2004
8	16	[861, 170543]
8	17	[861, 245156]	Xu and Xie 2002
8	18	[871, 346103]	Xu and Xie 2002
8	19	[1054, 480699]	Xu and Xie 2002
8	20	[1094, 657799]	Su et al. 2002
8	21	[1328, 888029]	Su et al. 2002
9	9	[565, 6588]	Shearer 1986, Shi and Zheng 2001
9	10	[580, 12677]	Xu and Xie 2002
10	10	[798, 23556]	Shearer 1986, Shi 2002
11	11	[1597, 184755]	Mathon 1987
12	12	[1637, 705431]	Xu and Xie 2002
13	13	[2557, 2704155]	Mathon 1987
14	14	[2989, 10400599]	Mathon 1987
15	15	[5485, 40116599]	Mathon 1987
16	16	[5605, 155117519]	Mathon 1987
17	17	[8917, 601080389]	Luo et al. 2002
18	18	[11005, 2333606219]	Luo et al. 2002
19	19	[17885, 9075135299]	Luo et al. 2002

The Ramsey number R(m,n) gives the solution to the party problem, which asks the minimum number of guests R(m,n) that must be invited so that at least m will know each other or at least n will not know each other. In the language of graph theory, the Ramsey number is the minimum number of vertices v=R(m,n) such that all undirected simple graphs of order v contain a clique of order m or an independent set of order n. Ramsey's theorem states that such a number exists for all m and n.

Ramsey Number

---

============> 1, 2, 3

• :::::>1, 2
• :::::>1, 3
• :::::>2, 3

============> 1, 2, 4

• :::::>1, 2
• :::::>1, 4
• :::::>2, 4

============> 1, 2, 5

• :::::>1, 2
• :::::>1, 5
• :::::>2, 5

============> 1, 3, 4

• :::::>1, 3
• :::::>1, 4
• :::::>3, 4

============> 1, 3, 5

• :::::>1, 3
• :::::>1, 5
• :::::>3, 5

============> 1, 4, 5

• :::::>1, 4
• :::::>1, 5
• :::::>4, 5

============> 2, 3, 4

• :::::>2, 3
• :::::>2, 4
• :::::>3, 4

============> 2, 3, 5

• :::::>2, 3
• :::::>2, 5
• :::::>3, 5

============> 2, 4, 5

• :::::>2, 4
• :::::>2, 5
• :::::>4, 5

============> 3, 4, 5

• :::::>3, 4
• :::::>3, 5
• :::::>4, 5