On Turán’s theorem for sparse graphs
Tóm tắt
For a graphG withn vertices and average valencyt, Turán’s theorem yields the inequalityα≧n/(t+1) whereα denotes the maximum size of an independent set inG. We improve this bound for graphs containing no large cliques.
Tài liệu tham khảo
M. Ajtai, J. Komlós, J. Pintz, J. Spencer andE. Szemerédi, Extremal uncrowded hypergraphs, in manuscript.
M. Ajtai, J. Komlós andE. Szemerédi, A dense infinite Sidon sequence,European Journal of Combinatorics,2 (1981) 1–11.
M. Ajtai, J. Komlós andE. Szemerédi, A note on Ramsey numbers,Journal of Combinatorial Theory A 29 (1980), 354–360.
J. Komlós, J. Pintz andE. Szemerédi, A lower bound for Heilbronn’s problem,Journal of the London Math. Soc., to appear.
J. Spencer, Turán’s theorem fork-graphs,Discrete Math. 2 (1972), 183–186.
P. Turán, Egy gráfelméleti szélsőértékfeladatról,Mat. Fiz. Lapok 48 (1941), 436–452; see also:On the Theory of Graphs, Colloq. Math. 3 (1954), 19–30.