Numbers and topologies [Elektronische Ressource] : two aspects of ramsey theory / von Lingsheng Shi

Numbers and Topologies:Two Aspects of Ramsey TheoryD I S S E R T A T I O Nzur Erlangung des akademischen Gradesdoctor rerum naturalium(dr. rer. nat.)im Fach Informatikeingereicht an derMathematisch-Naturwissenschaftlichen Fakult¨at IIHumboldt-Universit¨at zu BerlinvonHerr M.S. Lingsheng Shigeboren am 7.1.1975 in Anhui, ChinaPr¨asident der Humboldt-Universit¨at zu Berlin:Prof. Dr. Jurg¨ en MlynekDekan der Mathematisch-Naturwissenschaftlichen Fakult¨at II:Prof. Dr. Elmar KulkeGutachter:1. Prof. Dr. Hans Jurg¨ en Pr¨omel2. Prof. Dr. Hanno Lefmann3. Prof. Dr. Anusch Tarazeingereicht am: 12. Mai 2003Tag der mundlic¨ hen Prufung:¨ 10. Juli 2003AbstractIn graph Ramsey theory, Burr and Erd˝os in 1970s posed two conjectureswhich may be considered as initial steps toward the problem of character-izing the set of graphs for which Ramsey numbers grow linearly in theirorders. One conjecture is that Ramsey numbers grow linearly for all de-generate graphs and the other is that Ramsey numbers grow linearly forcubes. Though unable to settle these two conjectures, we have contributedmany weaker versions that support the likely truth of the first conjectureand obtained a polynomial upper bound for the Ramsey numbers of cubesthat considerably improves all previous bounds and comes close to the linearbound in the second conjecture.