Hofmeister–Joret–Wood conjecture on tree densities in minor-closed graph classes

Let s,ts,t be integers with ts1t\geqslant s\geqslant 1, and let Bs,t\mathcal{B}_{s,t} be the class of graphs containing no Ks,tK_{s,t} minor. For a fixed graph HH, define an ss-separation of HH to be a pair (A,B)(A,B) of edge-disjoint subgraphs with AB=HA\cup B=H, V(A)V(B)V(A)\setminus V(B)\neq\emptyset, V(B)V(A)V(B)\setminus V(A)\neq\emptyset, and V(A)V(B)=s|V(A)\cap V(B)|=s. A (s)(\leqslant s)-separation is an ss'-separation for some sss'\leqslant s, and two separations (A,B)(A,B) and (C,D)(C,D) are independent if E(A)E(C)=E(A)\cap E(C)=\emptyset and (V(A)V(B))(V(C)V(D))=(V(A)\setminus V(B))\cap(V(C)\setminus V(D))=\emptyset. Define fs(H):=1f_s(H):=1 if HH has no (s)(\leqslant s)-separation; otherwise, let fs(H)f_s(H) be the maximum number of pairwise independent (s)(\leqslant s)-separations in HH. Hofmeister–Joret–Wood conjecture. For every fixed graph HH with no Ks,tK_{s,t} minor,

C(H,Bs,t,n)Θ(nfs1(H)).C(H,\mathcal{B}_{s,t},n)\in\Theta\bigl(n^{f_{s-1}(H)}\bigr).

This conjecture proposes the correct asymptotic order for the number of copies of an arbitrary fixed graph in graphs excluding a fixed complete bipartite minor. The paper establishes the corresponding asymptotic behaviour for forests in several sparse graph classes, while this assertion concerns general graphs and is presented as an open problem.

Sources & referencesView supporting material

Primary source

Tony Huynh and David R. Wood, “Tree densities in sparse graph classes”, arXiv:2009.12989 (2021).

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.