Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Ramsey graphs and block designs. I


Author: T. D. Parsons
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
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 42 #4419. MR 0269524 (42:4419)
  • [2] J. A. Bondy and P. Erdös, Ramsey numbers for cycles in graphs, J. Combinatorial Theory Ser. (B) 14 (1973), 46-54. MR 47 #6540. MR 0317991 (47:6540)
  • [3] W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), 281-285. MR 34 #81. MR 0200182 (34:81)
  • [4] S. A. Burr and J. A. Roberts, On Ramsey numbers for stars, Utilitas Math. 4 (1973), 217-220. MR 0325435 (48:3782)
  • [5] G. Chartrand and S. Schuster, On the existence of specified cycles in complementary graphs, Bull. Amer. Math. Soc. 77 (1971), 995-998. MR 44 #6527. MR 0289336 (44:6527)
  • [6] V. Chvátal, Hypergraphs and Ramseyian theorems, Proc. Amer. Math. Soc. 27 (1971), 434-440. MR 42 #5855. MR 0270972 (42:5855)
  • [7] V. Chvátal and F. Harary, Generalized Ramsey theory for graphs, Bull. Amer. Math. Soc. 78 (1972), 423-426. MR 45 #110. MR 0291016 (45:110)
  • [8] -, Generalized Ramsey theory for graphs. I. Diagonal numbers, Per. Math. Hungar. 3 (1973), 113-122. MR 0332560 (48:10887)
  • [9] -, Generalized Ramsey theory for graphs. II. Small diagonal numbers, Proc. Amer. Math. Soc. 32 (1972), 389-394. MR 0332559 (48:10886)
  • [10] -, Generalized Ramsey theory for graphs. III. Small off-diagonal numbers, Pacific J. Math. 41 (1972), 335-345. MR 47 #3248. MR 0314696 (47:3248)
  • [11] E. J. Cockayne, An application of Ramsey's theorem, Canad. Math. Bull. 13 (1970), 145-146. MR 41 #6721. MR 0262111 (41:6721)
  • [12] P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292-294. MR 8, 479. MR 0019911 (8:479d)
  • [13] P. Erdös and R. Rado, A partition calculus in set theory, Bull. Amer. Math. Soc. 62 (1956), 427-489. MR 18, 458. MR 0081864 (18:458a)
  • [14] 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 36 #6310. MR 0223262 (36:6310)
  • [15] P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463-470. MR 1556929
  • [16] R. J. Faudree and R. H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974), 313-329. MR 0345866 (49:10596)
  • [17] R. J. Faudree, S. L. Lawrence, T. D. Parsons and R. H. Schelp, Path-cycle Ramsey numbers, Discrete Math. 10 (1974), 269-277. MR 0357195 (50:9663)
  • [18] J. Galovich, S. Galovich and S. Schuster, An elementary proof of the Friendship Theorem (to appear).
  • [19] L. Gerencsér and A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest Eötövös Sect. Math. 10 (1967), 167-170. MR 39 #1351. MR 0239997 (39:1351)
  • [20] J. E. Graver and J. Yackel, Some graph theoretic results associated with Ramsey's Theorem, J. Combinatorial Theory 4 (1968), 125-175. MR 37 #1278. MR 0225685 (37:1278)
  • [21] R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955), 1-7. MR 16, 733. MR 0067467 (16:733g)
  • [22] F. Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969. MR 41 #1566. MR 0256911 (41:1566)
  • [23] -, Recent results on generalized Ramsey theory for graphs, Graph Theory and Applications, Springer-Verlag, Berlin, 1972, pp. 125-138. MR 0342431 (49:7177)
  • [24] J. G. Kalbfleisch, Upper bounds for some Ramsey numbers, J. Combinatorial Theory 2 (1967), 35-42. MR 35 #2794. MR 0211919 (35:2794)
  • [25] J. Q. Longyear and T. D. Parsons, The friendship theorem, Nederl. Akad. Wetensch. Proc. Ser. A 75 = Indag. Math. 34 (1972), 257-262. MR 46 #5169. MR 0306042 (46:5169)
  • [26] T. D. Parsons, The Ramsey numbers $ r({P_m},{K_n})$, Discrete Math. 6 (1973), 159-162. MR 48 #150. MR 0321783 (48:150)
  • [27] -, Path-star Ramsey numbers, J. Combinatorial Theory Ser. B 17 (1974), 51-58. MR 0382069 (52:2957)
  • [28] F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1930), 264-286.
  • [29] V. Rosta, On a Ramsey type problem of J. A. Bondy and P. Erdös. I, II, J. Combinatorial Theory Ser. B 25 (1973), 94-104, 105-120. MR 0332567 (48:10894)
  • [30] 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.
  • [31] A. Rudvalis, $ (\upsilon ,k,\lambda )$-graphs and polarities of $ (\upsilon ,k,\lambda )$-designs, Math. Z. 120 (1971), 224-230. MR 45 #3220. MR 0294147 (45:3220)
  • [32] H. J. Ryser, A generalization of the matrix equation $ {A^2} = J$, Linear Algebra and Appl. 3 (1970), 451-460. MR 42 #4569. MR 0269674 (42:4569)
  • [33] S. Schuster, Progress on the problem of eccentric hosts. Graph Theory and Applications, Springer-Verlag, Berlin, 1972, pp. 283-290. MR 0360359 (50:12809)
  • [34] H. L. Skala, A variation of the Friendship Theorem, SIAM J. Appl. Math. 23 (1972), 214-220. MR 0373969 (51:10169)
  • [35] K. Walker, Dichromatic graphs and Ramsey numbers, J. Combinatorial Theory 5 (1968), 238-243. MR 38 #79. MR 0231751 (38:79)
  • [36] J. E. Williamson, A Ramsey-type problem for paths in digraphs, Math. Ann. 203 (1973), 117-118. MR 0325441 (48:3788)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C15, 05B05

Retrieve articles in all journals with MSC: 05C15, 05B05


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1975-0396317-X
Keywords: Graph, Ramsey number, block design
Article copyright: © Copyright 1975 American Mathematical Society

American Mathematical Society