The asymptotic minimum-degree characterization for H-factors with acyclic-partition hcf 1

From papers

Let HH be a graph, let AP\mathrm{AP} denote the family of all acyclic partitions of HH with ar(H)ar(H) parts, and let hcf(H,AP)\mathrm{hcf}(H,\mathrm{AP}) be the associated gcd parameter. For a graph HH, define its critical arboricity by

arcr(H)=(ar(H)1)V(H)V(H)σ(H),ar_{cr}(H)=\frac{(ar(H)-1)|V(H)|}{|V(H)|-\sigma(H)},

where σ(H)\sigma(H) is the minimum size of a part over all optimal acyclic partitions of HH.

The asymptotic HH-factor conjecture. Given μ>0\mu>0, hNh\in\mathbb{N}, and an hh-vertex graph HH with hcf(H,AP)=1\mathrm{hcf}(H,\mathrm{AP})=1, there exists α>0\alpha>0 such that, for all sufficiently large nhNn\in h\mathbb{N}, every nn-vertex graph GG satisfying

δ(G)max{(11arcr(H)+μ)n,(12+μ)n}\delta(G)\geq\max\left\{\left(1-\frac{1}{ar_{cr}(H)}+\mu\right)n,\left(\frac{1}{2}+\mu\right)n\right\}

and α(G)αn\alpha(G)\leq\alpha n contains an HH-factor.

The conjecture proposes the missing converse to the paper's asymptotic sharpness results for the minimum-degree condition in the HH-factor problem. The lower bound from the space barrier establishes sharpness for graphs with critical arboricity attaining the relevant threshold, while the case hcf(H,AP)1\mathrm{hcf}(H,\mathrm{AP})\neq1 is already covered by the stated dichotomy; the general hcf(H,AP)=1\mathrm{hcf}(H,\mathrm{AP})=1 case remains open.

Progress summary

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

Sources & referencesView supporting material

Primary source

Ming Chen, Jie Han, Guanghui Wang and Donglei Yang, “H-factors in graphs with small independence number”, arXiv:2207.03058 (2022).

Solutions 0

No solutions have been posted yet.