Ramsey graphs and block designs. I
HTML articles powered by AMS MathViewer
- by T. D. Parsons PDF
- Trans. Amer. Math. Soc. 209 (1975), 33-44 Request permission
Abstract:
This paper establishes a connection between a certain class of Ramsey numbers for graphs and the class of symmetric block designs admitting a polarity. The main case considered here relates the projective planes over Galois fields to the Ramsey numbers $R({C_4},{K_{1,n}}) = f(n)$. It is shown that, for every prime power $q,f({q^2} + 1) = {q^2} + q + 2$, and $f({q^2}) = {q^2} + q + 1$.References
- R. W. Ahrens and G. Szekeres, On a combinatorial generalization of 27 lines associated with a cubic surface, J. Austral. Math. Soc. 10 (1969), 485–492. MR 0269524, DOI 10.1017/S144678870000776X
- J. A. Bondy and P. Erdős, Ramsey numbers for cycles in graphs, J. Combinatorial Theory Ser. B 14 (1973), 46–54. MR 317991, DOI 10.1016/s0095-8956(73)80005-x
- W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), 281–285. MR 200182, DOI 10.4153/CMB-1966-036-2
- Stefan A. Burr and John A. Roberts, On Ramsey numbers for stars, Utilitas Math. 4 (1973), 217–220. MR 325435
- Gary Chartrand and Seymour Schuster, On the existence of specified cycles in complementary graphs, Bull. Amer. Math. Soc. 77 (1971), 995–998. MR 289336, DOI 10.1090/S0002-9904-1971-12832-X
- V. Chvátal, Hypergraphs and Ramseyian theorems, Proc. Amer. Math. Soc. 27 (1971), 434–440. MR 270972, DOI 10.1090/S0002-9939-1971-0270972-9
- Václav Chvátal and Frank Harary, Generalized Ramsey theory for graphs, Bull. Amer. Math. Soc. 78 (1972), 423–426. MR 291016, DOI 10.1090/S0002-9904-1972-12927-6
- V. Chvátal and F. Harary, Generalized Ramsey theory for graphs. I. Diagonal numbers, Period. Math. Hungar. 3 (1973), 115–124. Collection of articles dedicated to the memory of Alfred Renyi, II. MR 332560, DOI 10.1007/BF02018466
- Václav Chvátal and Frank Harary, Generalized Ramsey theory for graphs. II. Small diagonal numbers, Proc. Amer. Math. Soc. 32 (1972), 389–394. MR 332559, DOI 10.1090/S0002-9939-1972-0332559-X
- Václav Chvátal and Frank Harary, Generalized Ramsey theory for graphs. III. Small off-diagonal numbers, Pacific J. Math. 41 (1972), 335–345. MR 314696, DOI 10.2140/pjm.1972.41.335
- E. J. Cockayne, An application of Ramsey’s theorem, Canad. Math. Bull. 13 (1970), 145–146. MR 262111, DOI 10.4153/CMB-1970-032-5
- P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294. MR 19911, DOI 10.1090/S0002-9904-1947-08785-1
- P. Erdös and R. Rado, A partition calculus in set theory, Bull. Amer. Math. Soc. 62 (1956), 427–489. MR 81864, DOI 10.1090/S0002-9904-1956-10036-0
- P. Erdős, A. Rényi, and V. T. Sós, On a problem of graph theory, Studia Sci. Math. Hungar. 1 (1966), 215–235. MR 223262
- P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470. MR 1556929
- R. J. Faudree and R. H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974), 313–329. MR 345866, DOI 10.1016/0012-365X(74)90151-4
- R. J. Faudree, S. L. Lawrence, T. D. Parsons, and R. H. Schelp, Path-cycle Ramsey numbers, Discrete Math. 10 (1974), 269–277. MR 357195, DOI 10.1016/0012-365X(74)90122-8 J. Galovich, S. Galovich and S. Schuster, An elementary proof of the Friendship Theorem (to appear).
- L. Gerencsér and A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 10 (1967), 167–170. MR 239997
- Jack E. Graver and James Yackel, Some graph theoretic results associated with Ramsey’s theorem, J. Combinatorial Theory 4 (1968), 125–175. MR 225685, DOI 10.1016/S0021-9800(68)80038-9
- R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canadian J. Math. 7 (1955), 1–7. MR 67467, DOI 10.4153/CJM-1955-001-4
- Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911, DOI 10.21236/AD0705364
- Frank Harary, Recent results on generalized Ramsey theory for graphs, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Math., Vol. 303, Springer, Berlin, 1972, pp. 125–138. MR 0342431
- J. G. Kalbfleisch, Upper bounds for some Ramsey numbers, J. Combinatorial Theory 2 (1967), 35–42. MR 211919, DOI 10.1016/S0021-9800(67)80112-1
- Judith Q. Longyear and T. D. Parsons, The friendship theorem, Nederl. Akad. Wetensch. Proc. Ser. A 75=Indag. Math. 34 (1972), 257–262. MR 0306042, DOI 10.1016/1385-7258(72)90063-7
- T. D. Parsons, The Ramsey numbers $r(P_{m},\,K_{n})$, Discrete Math. 6 (1973), 159–162. MR 321783, DOI 10.1016/0012-365X(73)90045-9
- T. D. Parsons, Path-star Ramsey numbers, J. Combinatorial Theory Ser. B 17 (1974), 51–58. MR 382069, DOI 10.1016/0095-8956(74)90048-3 F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1930), 264-286.
- Vera Rosta, On a Ramsey-type problem of J. A. Bondy and P. Erdős. I, II, J. Combinatorial Theory Ser. B 15 (1973), 94–104; ibid. 15 (1973), 105–120. MR 332567, DOI 10.1016/0095-8956(73)90035-x B. L. Rothschild, A generalization of Ramsey’s theorem, Proc. Sympos. Pure Math., vol. 19, Amer. Math. Soc., Providence, R. I., 1971, pp. 205-213.
- Arunas Rudvalis, $(v,\,k,\,\lambda )$-graphs and polarities of $(v,\,k,\,\lambda )$-designs, Math. Z. 120 (1971), 224–230. MR 294147, DOI 10.1007/BF01117497
- H. J. Ryser, A generalization of the matrix equation $A^{2}=J$, Linear Algebra Appl. 3 (1970), 451–460. MR 269674, DOI 10.1016/0024-3795(70)90036-4
- Seymour Schuster, Progress on the problem of eccentric hosts, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Math., Vol. 303, Springer, Berlin, 1972, pp. 283–290. MR 0360359
- H. L. Skala, A variation of the friendship theorem, SIAM J. Appl. Math. 23 (1972), 214–220. MR 373969, DOI 10.1137/0123023
- K. Walker, Dichromatic graphs and Ramsey numbers, J. Combinatorial Theory 5 (1968), 238–243. MR 231751, DOI 10.1016/S0021-9800(68)80070-5
- James E. Williamson, A Ramsey-type problem for paths in digraphs, Math. Ann. 203 (1973), 117–118. MR 325441, DOI 10.1007/BF01431439
Additional Information
- © Copyright 1975 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 209 (1975), 33-44
- MSC: Primary 05C15; Secondary 05B05
- DOI: https://doi.org/10.1090/S0002-9947-1975-0396317-X
- MathSciNet review: 0396317