Asymptotic reduction conjecture for graph blow-ups

About 5 years old · traced to

Let HH be a graph on mm edges, let kk be a positive integer, let δ(H)\delta(H) be the minimum degree of HH, and let GC\mathcal{G}_C be the graph class defined in the paper. Write H{k}H\{k\} for the kk-subdivision (edge-blow-up) of HH, and let β(H,k)\beta(H,k) be the associated optimization parameter. Graph-blow-up reduction conjecture. If kδ(H)≥2k\delta(H)\geq 2, then

N⁡GC(n,H{k})=β(H,k)(k!)m⋅nkm+o(nkm).\operatorname{\mathbf{N}}_{\mathcal{G}_C}(n,H\{k\})={\beta(H,k)\over(k!)^m}\cdot n^{km}+o(n^{km}).

This conjecture would establish the expected asymptotic count in the relevant graph class under the stated minimum-degree condition. It is presented as a generalization of the paper's reduction lemmas and remains open in the source.

References

Primary source

Christopher Cox and Ryan R. Martin, “Counting paths, cycles and blow-ups in planar graphs”, arXiv:2101.05911 (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.