The Summer Undergraduate Research Fellowship (SURF) program allows students to research under the guidance of professors.
I worked with professor Richard M. Wilson the summer of 2006.
The general area of research is combinatorics, more specifically, graph theory.
The topics of this project includes hypertournaments, digraphs, Hamiltonian paths and cycles, and (vertex-)pancyclicity.
For terminology, refer to the final report above.
For a k-tournament on n vertices, Gutin and Yeo [2] proved that it has a Hamiltonian path when n > k + 1 and a Hamiltonian cycle when n > k + 2 if and only if it is strong. Gutin and Yeo also showed that these bounds are tight. They also mentioned as unsolved the problem of deciding whether a hypertournament is (vertex-)pancyclic.
Petrovic and Thomassen [3] proved that an k-tournament on n > k + 24d + 1 vertices, when k > 4, or on n > 30d + 2 vertices, when k = 3 has d edge-disjoint Hamiltonian cycles if and only if it is d-edge-connected (Theorem 2 in [3]). Note that when d = 1, 1-edge-connectedness is simply strong. They claimed that from the proof of Theorem 2 in [3], vertex-pancyclicity is implied as well. However, their characterization is incomplete because it requires n large compared to k.
My main problem is therefore to find the bounds of the number of vertices n of a k-tournament such that it is vertex-pancyclic if and only if it is strong. A generalized version is to change strong to d-edge-connected and in vertex-pancyclicity requires d edge-disjoint cycles of each length from 3 up to n. In the progress section below, when we say "For d = 1, k > 8, we lowered it to n > k + 3," we are referring to this bound of the main problem. If possible, we will also show that the bound is tight, but we will mention it explicitly, otherwise, assume that the bounds have not been shown to be tight.
The first few few days were spent reading background information and understanding known results and proofs. 2006.06.12 - Re-read my SURF proposal, and read the primary reference [3] of my problem. The current goal is to understand Theorem 2 in this paper, reading other papers as needed. 2006.06.13 - Read [2], that which the original open question was posed. 2006.06.16 - Met with my Mentor. Upon being asked to talk about the case of tournaments (k = 2), cited Redei's theorem and Camion's theorem. Asked to find out the proofs and present them Tuesday. 2006.06.17 - Found Camion's theorem in [1] as a corollary to Moon's theorem. Cannot find proof of Redei's theorem, thus attempted and succeeded to prove it myself. 2006.06.23 - Used the insight gained in reading [2] to understand Theorem 2 in [3]. The next few days will be spent trying to extend the Remark of Theorem 2 as in the original proposal. 2006.06.26 - For d = 1, k = 3, the main problem is answered for n > 32 in [3], we lowered it to 29. 2006.06.30 - For d = 1, k = 3, we lowered it to n > 15. 2006.07.06 - For d = 1, k > 4, [3] answered it for n > k + 25. For k = 4, we lowered it to n > 11. For 5 < k < 7, we lowered it to n > k + 4. For k > 8, we lowered it to n > k + 3. Note that [2] constructed a non-Hamiltonian k-tournament on n = k + 1 vertices that is strong. Hence the only work left for k > 8 is the n = k + 2 case. 2006.07.10 - Previously, we have only considered d = 1, and for k = 3, we got n > 15 as the bound. For any d > 1, we showed the bound to be n > 14d + 1, thus reducing my work on 6/26 to a specific case. 2006.07.17 - For d > 1, k > 8, the bound is n > k + 2d + 1; this requires insane amount of calculations. 2006.08.03 - Proved that for d = 1, k > 7, it is pancyclic if n > k + 2; this bound is tight.