Asymptotic reduction conjecture for graph blow-ups

From papers

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

NGC(n,H{k})=β(H,k)(k!)mnkm+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.

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

Christopher Cox and Ryan R. Martin, “Counting paths, cycles and blow-ups in planar graphs”, arXiv:2101.05911 (2022).

Solutions 0

No solutions have been posted yet.