A randomly augmented variant starts with a graph of minimum vertex degree
at least , for a fixed , and adds an independent random
graph
on the same vertex set, with each pair of distinct
vertices joined independently with probability. For every , there is a constant
such that
guarantees that
contains the 11th graph power of a Hamiltonian
cycle with probability tending to 1 as . Conversely, for some and , there is a sequence of
graphs meeting the same degree condition for which gives probability
tending to zero. Thus is the threshold scale for this augmentation problem
(Antoniuk et al. 2026, pp. 2, 6).
Antoniuk, S.; Dudek, A.; and Ruciński, A. "Powers of Hamiltonian Cycles in Randomly Augmented Pósa-Seymour Graphs." Elec.
J. Combin.33, P4.26, 2026. https://doi.org/10.37236/15044.Faudree,
R. J.; Gould, R. J.; Jacobson, M. S.; and Schelp, R. H. "On
a Problem of Paul Seymour." In Recent Advances in Graph Theory (Ed. V. R. Kulli).
Vishwa International Publishers, pp. 197-215, 1991.Komlós,
J.; Sárkőzy, G. N.; and Szemerédi, E. "On the Square
of a Hamiltonian Cycle in Dense Graphs." In Random Structures Algorithms9,
193-211, 1996.Komlós, J.; Sárkőzy, G. N.; and
Szemerédi, E. "Proof of the Seymour Conjecture for Large Graphs."
Ann. Comb.2, 43-60, 1998.Seymour, P. Problem Section
in Combinatorics:
Proceedings of the British Combinatorial Conference, 1973 (Ed. T. P. McDonough
and V. C. Mavron). Cambridge, England: Cambridge University Press, pp. 201-202,
1974.
, the Seymour conjecture (Seymour 1974) asserts that
a graph 
of vertex count 
with minimum vertex
degree 
contains the 
th
graph power of a Hamiltonian
cycle, generalizing Pósa's conjecture.
Komlós et al. (1998) proved the conjecture for sufficiently large 
using Szemerédi's
regularity lemma and a technique called the blow-up
lemma.
of minimum vertex degree
at least 
, for a fixed 
, and adds an independent random
graph 
on the same vertex set, with each pair of distinct
vertices joined independently with probability 
. For every 
, there is a constant
such that 
guarantees that 
contains the 11th graph power of a Hamiltonian
cycle with probability tending to 1 as 
. Conversely, for some 
and 
, there is a sequence of
graphs meeting the same degree condition for which 
gives probability
tending to zero. Thus 
is the threshold scale for this augmentation problem
(Antoniuk et al. 2026, pp. 2, 6).
