Pósa's Conjecture for graphs of order at least 2\times 10^8

Details Pósa's Conjecture for graphs of order at least 2\times 10^8 Pósa's Conjecture for graphs of order at least 2\times 10^8

2011-04-21

arxiv.org/abs/1104.4367v1

Mathematics

Combinatorics

20 pages, to appear in Random Structures & Algorithms

Scientific paper

In 1962 P\'osa conjectured that every graph G on n vertices with minimum degree at least 2n/3 contains the square of a hamiltonian cycle. In 1996 Fan and Kierstead proved the path version of P\'osa's Conjecture. They also proved that it would suffice to show that G contains the square of a cycle of length greater than 2n/3. Still in 1996, Koml\'os, S\'ark\"ozy, and Szemer\'edi proved P\'osa's Conjecture, using the Regularity and Blow-up Lemmas, for graphs of order n > n_0, where n_0 is a very large constant. Here we show without using these lemmas that n_0=2\times 10^8 is sufficient. We are motivated by the recent work of Levitt, Szemer\'edi and S\'ark\"ozy, but our methods are based on techniques that were available in the 90's.

Affiliated with

Also associated with

No associations

Rating

Pósa's Conjecture for graphs of order at least 2\times 10^8 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pósa's Conjecture for graphs of order at least 2\times 10^8, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pósa's Conjecture for graphs of order at least 2\times 10^8 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-330075