Hypergraphs and Ramseyian theorems

Chvátal, V.

doi:10.1090/S0002-9939-1971-0270972-9

Hypergraphs and Ramseyian theorems
HTML articles powered by AMS MathViewer

by V. Chvátal PDF

Proc. Amer. Math. Soc. 27 (1971), 434-440 Request permission

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

V. Chvátal, On finite polarized partition relations, Canad. Math. Bull. 12 (1969), 321–326. MR 260606, DOI 10.4153/CMB-1969-040-1
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, On a combinatorial problem, Nordisk Mat. Tidskr. 11 (1963), 5–10, 40. MR 148554
P. Erdős, On a combinatorial problem. II, Acta Math. Acad. Sci. Hungar. 15 (1964), 445–447. MR 167427, DOI 10.1007/BF01897152
P. Erdős and A. Hajnal, On a property of families of sets, Acta Math. Acad. Sci. Hungar. 12 (1961), 87–123 (English, with Russian summary). MR 150047, DOI 10.1007/BF02066676
P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99. MR 193025, DOI 10.1007/BF02020444
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 65615, DOI 10.1112/plms/s3-2.1.417
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
Gyula Katona, Tibor Nemetz, and Miklós Simonovits, On a problem of Turán in the theory of graphs, Mat. Lapok 15 (1964), 228–238 (Hungarian, with English and Russian summaries). MR 172263
W. M. Schmidt, Ein kombinatorisches Problem von P. Erdős und A. Hajnal, Acta Math. Acad. Sci. Hungar. 15 (1964), 373–374 (German). MR 167428, DOI 10.1007/BF01897145
J. Schönheim, On coverings, Pacific J. Math. 14 (1964), 1405–1411. MR 171727, DOI 10.2140/pjm.1964.14.1405

Ein Extremslaufgabe aus der Graphentheorie

48

8

On the theory of graphs

3

15

Paul Turán, Research problems, Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 417–423. MR 177847, DOI 10.1007/BF02017934