Ramsey graphs and block designs. I

Parsons, T. D.

doi:10.1090/S0002-9947-1975-0396317-X

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

An elementary proof of the Friendship Theorem

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

On a problem of formal logic

30

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

A generalization of Ramsey’s theorem

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