Applications of Ramsey theory. (English) Zbl 0561.05040
This article attempts to demonstrate that Ramsey theory does have useful applications. Four examples are used, two involving communication problems, one involving a problem of information retrieval in computer science, and one a problem in decisionmaking. The examples given use one of the following: (1) the exact value of a specific Ramsey number, (2) a bound on a specific Ramsey number, and (3) knowledge that a certain Ramsey number exists.
Reviewer: R.Schelp
Keywords:
Ramsey theory; communication problems; information retrieval; decisionmaking; Ramsey numberReferences:
| [1] | Baker, K. A.; Fishburn, P. C.; Roberts, F. S., Partial orders of dimension 2, interval orders, and interval graphs, Paper P-4376 (1970), The RAND Corporation: The RAND Corporation Santa Monica, CA · Zbl 0247.06002 |
| [2] | Baker, K. A.; Fishburn, P. C.; Roberts, F. S., Partial orders of dimension 2, Networks 2, 11-28 (1972) · Zbl 0247.06002 |
| [3] | Berge, C., Graphs and Hypergraphs (1973), American Elsevier: American Elsevier New York · Zbl 0483.05029 |
| [4] | Bogart, K. P.; Rabinovitch, I.; Trotter, W. T., A bound on the dimension of interval orders, J. Combin. Theory, 21, 319-328 (1976) · Zbl 0351.06004 |
| [5] | Chandra, A. K.; Furst, M. L.; Lipton, R. J., Multi-party protocols, (Proc. 15th Annual ACM Symp. Theory of Computing (1983), Assoc. Comput. Mach.,: Assoc. Comput. Mach., New York), 94-99 |
| [6] | Chung, F. R.K.; Graham, R. L., On multicolor Ramsey numbers for complete bipartite graphs, J. Combin. Theory, 18, B, 164-169 (1975) · Zbl 0298.05122 |
| [7] | Dushnik, B.; Miller, E. W., Partially ordered sets, Amer. J. Math., 63, 600-610 (1941) · Zbl 0025.31002 |
| [8] | Faudree, R. J.; Schelp, R. H., All Ramsey numbers for cycles in graphs, Discrete Math., 8, 313-329 (1974) · Zbl 0294.05122 |
| [9] | Fishburn, P. C., Intransitive indifference with unequal indifference intervals, J. Math. Psychol., 7, 144-149 (1970) · Zbl 0191.31501 |
| [10] | Graham, R. L., Rudiments of Ramsey Theory, CBMS Regional Conf. Series in Math, 45 (1981), Amer. Math. Soc.,: Amer. Math. Soc., Providence, RI · Zbl 0458.05043 |
| [11] | Graham, R. L.; Rothschild, B. L.; Spencer, J. H., Ramsey Theory (1980), Wiley: Wiley New York · Zbl 0455.05002 |
| [12] | Haemers, W., On some problems of Lovász concerning the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 231-232 (1979) · Zbl 0402.94029 |
| [13] | Hedrlin, Z., An application of the Ramsey theorem to the topological product, Bull. Acad. Pol. Sci., 14, 25-26 (1966) · Zbl 0152.39702 |
| [14] | Kelly, D.; Trotter, W. T., Dimension theory for ordered sets, (Rival, I., Ordered Sets (1982), Reidel: Reidel Boston), 171-211 · Zbl 0499.06003 |
| [15] | Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 1-7 (1979) · Zbl 0395.94021 |
| [16] | Roberts, F. S., What if utility functions do not exist?, Theory and Decision, 3, 126-139 (1972) · Zbl 0252.90008 |
| [17] | Roberts, F. S., Applied Combinatorics (1984), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0547.05001 |
| [18] | Rosenfeld, M., On a problem of C.E. Shannon in graph theory, Proc. Amer. Math. Soc., 18, 315-319 (1967) · Zbl 0147.42801 |
| [19] | Rosta, V., On a Ramsey type problem of J.A. Bondy and P. Erdös, I, J. Combin. Theory (B), 15, 94-104 (1973) · Zbl 0261.05118 |
| [20] | Rosta, V., On a Ramsey type problem of J.A. Bondy and P. Erdös, II, J. Combin. Theory (B), 15, 105-120 (1973) · Zbl 0261.05119 |
| [21] | Schrijver, A., A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inf. Theory, 25, 425-429 (1979) · Zbl 0444.94009 |
| [22] | Shannon, C. E., The zero-error capacity of a noisy channel, IRE Trans. Inf. Theory, 2, 8-19 (1956) |
| [23] | Szpilrajn, E., Sur l’extension de l’ordre partiel, Fund. Math., 16, 386-389 (1930) · JFM 56.0843.02 |
| [24] | Trotter, W. T.; Moore, J. I., Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Discrete Math., 15, 361-368 (1976) · Zbl 0356.06007 |
| [25] | Yao, A. C., Should tables be sorted? (preliminary version), Proc. 1978 IEEE Symp. Foundations of Computer Science, Ann Arbor, MI (October 1978) |
| [26] | Yao, A. C., Should tables be sorted?, J. ACM, 28, 615-628 (1981) · Zbl 0462.68079 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
