“Ramsey Number”的概念、定义、习题解题方法及翻译-数学辞典

单词

Ramsey Number

释义

Ramsey Number

The Ramsey number gives the solution to the Party Problem, which asks the minimum number of guests that must be invited so that at least will know each other (i.e., there exists a Clique of order ) or at least will not know each other (i.e., there exists an independent set of order ). By symmetry, it is true that

(1)

It also must be true that

(2)

A generalized Ramsey number is written

(3)

and is the smallest Integer

such that, no matter how each

-element Subset of an

-element Set iscolored with

colors, there exists an

such that there is a Subset of size

, all of whose

-elementSubsets are color

. The usual Ramsey numbers are then equivalent to

Bounds are given by

(4)

and

(5)

(Chung and Grinstead 1983). Erdös proved that for diagonal Ramsey numbers

(6)

This result was subsequently improved by a factor of 2 by Spencer (1975).

was known since 1980 to be bounded fromabove by

, and Griggs (1983) showed that

was an acceptable limit. J.-H. Kim (Cipra 1995)subsequently bounded

by a similar expression from below, so

(7)

Burr (1983) gives Ramsey numbers for all 113 graphs with no more than 6 Edges and no isolatedpoints.

A summary of known results up to 1983 for is given in Chung and Grinstead (1983). Radziszowski maintains anup-to-date list of the best current bounds, reproduced in part in the following table for .

			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 1989, Radziszowski and Kreher 1988
3	11	[46, 51]	Radziszowski and Kreher 1988
3	12	[52, 60]	Exoo 1993, Radziszowski and Kreher 1988, Exoo 1998
3	13	[60, 69]	XZ, Radziszowski and Kreher 1988
3	14	[66, 78]	Exoo (unpub.), Radziszowski and Kreher 1988
3	15	[73, 89]	Wang and Wang 1989, Radziszowski (unpub.)
3	16	[79, ]	Wang and Wang 1989
3	17	[92, ]	WWY
3	18	[98, ]	WWY
3	19	[106, ]	WWY
3	20	[109, ]	WWY
3	21	[122, ]	WWY
3	22	[125, ]	WWY
3	23	[136, ]	WWY
4	4	18	Greenwood and Gleason 1955
4	5	25	Mckay and Radziszowski 1995
4	6	[35, 41]	Ex8, MR4
4	7	[49, 62]
4	8	[55, 85]	Exoo 1998
4	9	[69, 116]
4	10	[80, 151]
4	11	[93, 191]
4	12	[98, 238]
4	13	[112, 291]
4	14	[119, 349]
4	15	[128, 417]
5	5	[43, 49]	Ex4, MR4
5	6	[58, 87]	Exoo 1993, Walker 1971
5	7	[80, 143]
5	8	[95, 216]
5	9	[116, 371]	Exoo 1998
5	10	[1, 445]
6	6	[102, 165]	Kalbfleisch 1965, Mac
6	7	[109, 300]	Exoo 1998
6	8	[122, 497]	Exoo 1998
6	9	[153, 784]
6	10	[167, 1180]
7	7	[205, 545]	Hill and Irving 1982, Giraud 1973
7	8	[1, 1035]
7	9	[1, 1724]
7	10	[1, 2842]
8	8	[282, 1874]
8	9	[1, 3597]
8	10	[1, 6116]
9	9	[565, 6680]
9	10	[1, 12795]
10	10	[798, 23981]	Guldan and Tomasta ?
11	11	[522, ]	Guldan and Tomasta ?

Known values for generalized Ramsey numbers are given in the following table.

	Bounds	Reference
	17	Greenwood and Gleason 1955
	[30, 32]
	[45, 59]
		Exoo 1998
	[55, 81]
	[128, 242]	Hill and Irving 1982, Giraud 1973
	[51, 64]	Chung 1973, Sanchez-Flores 1995
	[87, 159]	Exoo 1998
	[162, 317]
	[1, 500]

	Bounds
	[14, 15]

See also Clique, Complete Graph,Extremal Graph, Irredundant Ramsey Number, Schur Number

References

Burr, S. A. ``Generalized Ramsey Theory for Graphs--A Survey.'' In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). New York: Springer-Verlag, pp. 52-75, 1964.

Burr, S. A. ``Diagonal Ramsey Numbers for Small Graphs.'' J. Graph Th. 7, 57-69, 1983.

Chartrand, G. ``The Problem of the Eccentric Hosts: An Introduction to Ramsey Numbers.'' §5.1 in Introductory Graph Theory. New York: Dover, pp. 108-115, 1985.

Chung, F. R. K. ``On the Ramsey Numbers .'' Discrete Math. 5, 317-321, 1973.

Chung, F. and Grinstead, C. G. ``A Survey of Bounds for Classical Ramsey Numbers.'' J. Graph. Th. 7, 25-37, 1983.

Cipra, B. ``A Visit to Asymptopia Yields Insights into Set Structures.'' Science 267, 964-965, 1995.

Exoo, G. ``On Two Classical Ramsey Numbers of the Form .'' SIAM J. Discrete Math. 2, 488-490, 1989.

Exoo, G. ``Announcement: On the Ramsey Numbers , and .'' Ars Combin. 35, 85, 1993.

Exoo, G. ``Some New Ramsey Colorings.'' Electronic J. Combinatorics 5, No. 1, R29, 1-5, 1998.http://www.combinatorics.org/Volume_5/v5i1toc.html.

Folkmann, J. ``Notes on the Ramsey Number .'' J. Combinat. Theory. Ser. A 16, 371-379, 1974.

Gardner, M. ``Mathematical Games: In Which Joining Sets of Points by Lines Leads into Diverse (and Diverting) Paths.'' Sci. Amer. 237, 18-28, 1977.

Gardner, M. Penrose Tiles and Trapdoor Ciphers... and the Return of Dr. Matrix, reissue ed. New York: W. H. Freeman, pp. 240-241, 1989.

Giraud, G. ``Une minoration du nombre de quadrangles unicolores et son application a la majoration des nombres de Ramsey binaires bicolors.'' C. R. Acad. Sci. Paris A 276, 1173-1175, 1973.

Graham, R. L.; Rothschild, B. L.; and Spencer, J. H. Ramsey Theory, 2nd ed. New York: Wiley, 1990.

Graver, J. E. and Yackel, J. ``Some Graph Theoretic Results Associated with Ramsey's Theorem.'' J. Combin. Th. 4, 125-175, 1968.

Greenwood, R. E. and Gleason, A. M. ``Combinatorial Relations and Chromatic Graphs.'' Canad. J. Math. 7, 1-7, 1955.

Griggs, J. R. ``An Upper Bound on the Ramsey Numbers .'' J. Comb. Th. A 35, 145-153, 1983.

Grinstead, C. M. and Roberts, S. M. ``On the Ramsey Numbers and .'' J. Combinat. Th. Ser. B 33, 27-51, 1982.

Guldan, F. and Tomasta, P. ``New Lower Bounds of Some Diagonal Ramsey Numbers.'' J. Graph. Th. 7, 149-151, 1983.

Hanson, D. ``Sum-Free Sets and Ramsey Numbers.'' Discrete Math. 14, 57-61, 1976.

Harary, F. ``Recent Results on Generalized Ramsey Theory for Graphs.'' Graph Theory and Applications (Ed. Y. Alai, D. R. Lick, and A. T. White). New York: Springer-Verlag, pp. 125-138, 1972.

Hill, R. and Irving, R. W. ``On Group Partitions Associated with Lower Bounds for Symmetric Ramsey Numbers.'' European J. Combin. 3, 35-50, 1982.

Kalbfleisch, J. G. Chromatic Graphs and Ramsey's Theorem. Ph.D. thesis, University of Waterloo, January 1966.

McKay, B. D. and Min, Z. K. ``The Value of the Ramsey Number .'' J. Graph Th. 16, 99-105, 1992.

McKay, B. D. and Radziszowski, S. P. ``.'' J. Graph. Th 19, 309-322, 1995.

Piwakowski, K. ``Applying Tabu Search to Determine New Ramsey Numbers.'' Electronic J. Combinatorics 3, R6 1-4, 1996.http://www.combinatorics.org/Volume_3/volume3.html#R6.

Radziszowski, S. P. ``Small Ramsey Numbers.'' Electronic J. Combin. 1, DS1 1-29, Rev. Mar. 25, 1996. http://ejc.math.gatech.edu:8080/Journal/Surveys/ds1.ps.

Radziszowski, S. and Kreher, D. L. ``Upper Bounds for Some Ramsey Numbers .'' J. Combinat. Math. Combin. Comput. 4, 207-212, 1988.

Spencer, J. H. ``Ramsey's Theorem--A New Lower Bound.'' J. Combinat. Theory Ser. A 18, 108-115, 1975.

Wang, Q. and Wang, G. ``New Lower Bounds for the Ramsey Numbers .'' Beijing Daxue Xuebao 25, 117-121, 1989.

Whitehead, E. G. ``The Ramsey Number .'' Discrete Math. 4, 389-396, 1973.

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。