Sparse-host induced subdivision extremal conjecture

Let HH be a graph, and let DH\mathcal{D}_H be the property of not containing a subdivision of HH as an induced subgraph. For a graph Γ\Gamma, write ex(Γ,DH)\mathrm{ex}(\Gamma,\mathcal{D}_H) for the maximum number of edges in a subgraph of Γ\Gamma with this property. For c>0c>0, say that Γ\Gamma is (c,t)(c,t)-sparse when it satisfies the sparsity condition used in the paper. Sparse-host induced subdivision extremal conjecture. For every c>0c>0 and a graph HH, there exists C>1C>1 such that, if Γ\Gamma is a (c,t)(c,t)-sparse graph, then

ex(Γ,DH)Ctn.\mathrm{ex}(\Gamma,\mathcal{D}_H)\le Ctn.

The motivation is a result showing that sufficiently dense graphs with no Kt,tK_{t,t} contain an induced subdivision of HH; the stated sparse-host extremal estimate remains open.

Sources & referencesView supporting material

Primary source

Jacob Fox, Rajko Nenadov and Huy Tuan Pham, “The largest subgraph without a forbidden induced subgraph”, arXiv:2405.05902 (2024).

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.