Nikiforov's spectral Erdős–Sós conjecture for trees

At least 11 years old · documented by

Let FF be a tree of order ℓ≥4\ell\geq 4. For integers n,k,pn,k,p with n>k>0n>k>0 and p∈{0,…,⌊(n−k)/2⌋}p\in\{0,\dots,\lfloor(n-k)/2\rfloor\}, let Sn,kpS_{n,k}^{p} be the graph obtained from Kk∇(n−k)K1K_k\nabla(n-k)K_1 by embedding pp independent edges into (n−k)K1(n-k)K_1. For n≥ℓ≥4n\geq\ell\geq 4, define

Gn,ℓ=Sn,(ℓ−2)/20G_{n,\ell}=S_{n,(\ell-2)/2}^{0}

if ℓ\ell is even and Gn,ℓ=Sn,(ℓ−3)/21G_{n,\ell}=S_{n,(\ell-3)/2}^{1} otherwise. Nikiforov's conjecture. Let ℓ≥6\ell\geq 6 and let GG be a graph of sufficiently large order nn. If

ρ(G)≥ρ(Gn,ℓ),\rho(G)\geq\rho(G_{n,\ell}),

then GG contains all trees of order ℓ\ell unless G=Gn,ℓG=G_{n,\ell}. This is a spectral analogue of the Erdős–Sós conjecture, which concerns forcing all trees of order ℓ\ell from an average-degree condition. The conjecture is attributed to Nikiforov; its resolution status is not established by the supplied text.

References

Primary source

Longfei Fang, Huiqiu Lin, Jinlong Shu and Zhiyuan Zhang, “Spectral extremal results on trees”, arXiv:2401.05786 (2024).

Additional references

10 papers in this index state this conjecture (2014–2024). The statement above is taken from the most recent of them; the others are arXiv:2209.03120, arXiv:2205.00990, arXiv:2112.13253, arXiv:2111.03309, arXiv:2110.11345, arXiv:2109.11546, arXiv:1707.04810, arXiv:1610.00833, arXiv:1410.2142.

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.