A Spectral Turán Problem for a Fixed Tree

2025/05/20 by Desai, Dheer Noal, Kaul, Hemanshu, Kudarzi, Bahareh
#05C05 #05C35 #05C50 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2505.14908

Abstract

We study the spectral Turán problem for trees. To avoid limiting our perspective to specific families of trees, we parametrize trees in terms of their unique bipartition. We say T ∈ T_m,l+1^δ if T is a tree of order m, where the order of the smaller partite set A of T is l+1, and δ is the minimum degree of the vertices in A. The motivation for this parametrization comes from the recent proof of the spectral Erdős-Sós conjecture. For a given fixed tree T, we describe SPEX(n,T) and consequently, bound spex(n,T) in terms of m,l,δ for that tree. Our approach combines spectral arguments with new results and constructions on embedding a tree T ∈ T_m,l+1^δ into graphs of the form K_l \vee m S_δ. We give bounds on spex(n,T) within an error of Θ(n^-1/2) and Θ(n^-1) that are based on our embedding results for the given T.

Citations

• Spectral supersaturation: Triangles and bowties
• A spectral Erdős-Faudree-Rousseau theorem
• A general theorem in spectral extremal graph theory
• Spectral extremal results on trees
• Spectral Turán problems for intersecting even cycles
• A spectral Erdős-Sós theorem
• The spectral even cycle problem
• Spectral extremal graphs for intersecting cliques
• The spectral radius of graphs with no odd wheels
• The Colin de Verdi `ere parameter, excluded minors, and the spectral\n radius
• The spectral radius of graphs without trees of diameter at most four
• Eigenvalues of subgraphs of the cube
• The history of degenerate (bipartite) extremal graph problems
• The spectral radius of graphs without paths and cycles of specified length
• Spectral radius and Hamiltonicity of graphs
• A spectral condition for odd cycles in graphs
• Bounds on graph eigenvalues II

Related

• Spectral Turán problems for suspensions of balanced trees
• The spectral Turán problem: Characterizing spectral-consistent graphs
• A spectral Erdős-Sós theorem
• The bipartite Turan number and spectral extremum for linear forests
• Bipartite Turán number of trees