Local Resilience for Squares of Almost Spanning Cycles in Sparse Random Graphs

[摘要] In 1962, Pósa conjectured that a graph $G=(V, E)$ contains a square of a Hamiltonian cycle if $\delta(G)\ge 2n/3$. Only more than thirty years later Komlós, Sárkőzy, and Szemerédi proved this conjecture using the so-called Blow-Up Lemma. Here we extend th

[学科分类] 离散数学和组合数学

[关键词] Random graphs;Resilience;Almost spanning subgraphs