Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Hypergraphs and Ramseyian theorems


Author: V. Chvátal
Journal: Proc. Amer. Math. Soc. 27 (1971), 434-440
MSC: Primary 05.55
DOI: https://doi.org/10.1090/S0002-9939-1971-0270972-9
MathSciNet review: 0270972
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A $ k$-graph is an ordered couple $ (V,E)$ where $ V$ is a set and $ E$ a set of $ k$-tuples of elements of $ V$; thus, a $ 2$-graph is an ordinary graph. If the notions of the independent set and the chromatic number are generalized for $ k$-graphs then one can ask what is the least number of edges in a $ k$-graph having $ p$ vertices and no independent set of size $ b$ (the problem of Turán) and what is the least number of edges in a $ k$-graph whose chromatic number exceeds a given number (the generalized problem of Erdös and Hajnal). As in graphs, there is a relationship between independent sets and chromatic numbers--actually, our results for the first problem are applicable to the second one. The theorems of Ramsey's type are, in fact, theorems on the chromatic number of certain $ k$-graphs; thus, the results for the problem of Erdös and Hajnal yield lower bounds for the general ``Ramseyian numbers".


References [Enhancements On Off] (What's this?)

  • [1] V. Chvátal, On finite polarized partition relations, Canad. Math. Bull. 12 (1969), 321-326. MR 0260606 (41:5230)
  • [2] 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)
  • [3] -, On a combinatorial problem, Nordisk. Mat. Tidskr. 11 (1963), 5-10, 40. MR 26 #6061. MR 0148554 (26:6061)
  • [4] -, On a combinatorial problem. II, Acta Math. Acad. Sci. Hungar. 15 (1964), 445-447. MR 0167427 (29:4700)
  • [5] P. Erdös and A. Hajnal, On a property of families of sets, Acta Math. Acad. Sci. Hungar. 12 (1961), 87-123. MR 27 #50. MR 0150047 (27:50)
  • [6] -, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61-99. MR 33 #1247. MR 0193025 (33:1247)
  • [7] P. Erdös and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc. (3) 2 (1952), 417-439. MR 16, 455. MR 0065615 (16:455d)
  • [8] -, Partition calculus in set theory, Bull. Amer. Math. Soc. 62 (1956), 427-489. MR 18, 458. MR 0081864 (18:458a)
  • [9] G. Katona, T. Nemetz and M. Simonovits, On a problem of Turán in the theory of graphs, Mat. Lapok 15 (1964), 228-238. (Hungarian) MR 30 #2483. MR 0172263 (30:2483)
  • [10] W. M. Schmidt, Ein kombinatorisches Problem von P. Erdös und A. Hajnal, Acta Math. Acad. Sci. Hungar. 15 (1964), 373-374. MR 29 #4701. MR 0167428 (29:4701)
  • [11] J. Schönheim, On coverings, Pacific J. Math. 14 (1964), 1405-1411. MR 30 #1954. MR 0171727 (30:1954)
  • [12] P. Turán, Ein Extremslaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436-452. (Hungarian) MR 8, 284. See also: On the theory of graphs, Colloq. Math. 3 (1954), 19-30. MR 15, 976.
  • [13] -, Research problems, Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 417-423. MR 31 #2107. MR 0177847 (31:2107)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05.55

Retrieve articles in all journals with MSC: 05.55


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1971-0270972-9
Keywords: Hypergraph, Turán's problem, covering problems, independent sets, chromatic number, Ramsey type theorems
Article copyright: © Copyright 1971 American Mathematical Society

American Mathematical Society