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

About 4 years old · traced to

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, h∈Nh\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 n∈hNn\in h\mathbb{N}, every nn-vertex graph GG satisfying

δ(G)≥max⁡{(1−1arcr(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.

References

Primary source

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

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.