Shifted Chvátal-resilience conjecture for Hamilton cycles in random graphs

Let G=Gn,pG=G_{n,p} be a random graph, and let (ε,δ)(\boldsymbol{\varepsilon},\boldsymbol{\delta})-Chvátal-resilience mean resilience with respect to subgraphs satisfying the shifted Chvátal degree condition: there is an ordering v1,,vnv_1,\ldots,v_n with dH(v1)dH(vn)d_H(v_1)\geq\cdots\geq d_H(v_n) such that, for every i<n/2i<n/2, either

dH(vi)(ni)pεnpd_H(v_i)\leq (n-i)p-\boldsymbol{\varepsilon}np

or

dH(vniδn)ipεnp.d_H(v_{n-i-\boldsymbol{\delta} n})\leq ip-\boldsymbol{\varepsilon}np.

Shifted Chvátal-resilience conjecture. For every ε>0\varepsilon>0, there exists C>0C>0 such that, for pClogn/np\geq C\log n/n, a.a.s. the random graph Gn,pG_{n,p} is (ε,ε)(\varepsilon,\varepsilon)-Chvátal-resilient with respect to Hamiltonicity.

This conjecture proposes the Hamilton-cycle analogue of the preceding theorem for perfect matchings, extending Chvátal-type resilience to Hamiltonicity in sparse random graphs. Its resolution status is not specified in the supplied text.

Sources & referencesView supporting material

Primary source

Padraig Condon, Alberto Espuny Díaz, Jaehoon Kim, Daniela Kühn and Deryk Osthus, “Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs”, arXiv:1810.12433 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.