Title: How to avoid using the Regularity Lemma: Pósa’s conjecture revisited
Abstract: In this paper we investigate how the use of the Regularity Lemma and the Blow-up Lemma can be avoided in certain extremal problems of dense graphs. We present the ideas for the following well-known Pósa conjecture on the square of a Hamiltonian cycle. In 1962 Pósa conjectured that any graph G of order n and minimum degree at least 23n contains the square of a Hamiltonian cycle. In an earlier paper we proved this conjecture with the use of the Regularity Lemma–Blow-up Lemma method for n≥n0 where n0 is very large. Here we present another proof (and a general method) that avoids the use of the Regularity Lemma and thus the resulting n0 is much smaller.
Publication Year: 2010
Publication Date: 2010-02-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 52
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot