Spectral generalized Turán problems
Xizhi Liu · 2025
Read Spectral generalized Turán problems by Xizhi Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-21689.txt.
Introduction
Xizhi Liu presents a 2025 arXiv paper launching the spectral generalized Turán problem. Two classic lines meet here: counting copies of a pattern graph without creating a forbidden one, and bounding a graph's spectral radius under the same ban. Liu proves a general theorem extending a known spectral result into the broader counting setting. The spectral Erdős pentagon theorem falls out as a quick payoff. The paper also defines an entropic density and shows it equals the generalized spectral radius.
Catalog record
| CREATOR | Xizhi Liu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-21689
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Spectral generalized Turán problems Xizhi Liu Abstract Combining two well-studied variants of the classical Turán problem, the generalized Turán problem and the spectral Turán problem, we introduce the spectral generalized Turán problem and establish a general theorem that extends the result of Keevash–Lenz–Mubayi [ KLM14 ] on the spectral Turán problem in this broader setting. As a quick application, we obtain the spectral Erdős Pentagon Theorem. We also introduce the notion of entropic density for generalized Turán problems, and show that it coincides with the generalized spectral radius, extending a recent result of Chao–Hans on entropic Turán density. 1 Introduction For an integer r\geq 2 , an r -uniform hypergraph (henceforth r -graph) \mathcal{H} is a collection of r -subsets of some finite set V . We identify a hypergraph \mathcal{H} with its edge and use |\mathcal{H}| to denote the number of edges in it. The vertex set of \mathcal{H} is denoted by V(\mathcal{H}) , and its size is denoted by v(\mathcal{H}) . Given a family \mathcal{F} of r -graphs, an r -graph \mathcal{H} is \mathcal{F} -free if it does not contain any member of \mathcal{F} as a subgraph. Following the seminal work of Turán [ Tur41 ] , a central problem in extremal combinatorics is to determine the maximum number of edges in an \mathcal{F} -free r -graph on n vertices, known as the Turán number of \mathcal{F} : \displaystyle\mathrm{ex}(n,\mathcal{F}) \displaystyle\coloneqq\max\left\{|\mathcal{H}|\colon\text{$v(\mathcal{H})=n$ and $\mathcal{H}$ is $\mathcal{F}$-free}\right\}. An extensively studied variant of the Turán problem is the generalized Turán problem, initiated by Erdős [ Erd62 ] and studied systematically by Alon–Shikhelman [ AS16 ] . This line of research investigates the maximum number of copies of a fixed r -graph Q , rather than edges, in an \mathcal{F} -free r -graph on n vertices. More specifically, let \mathrm{N}(Q,\mathcal{H}) denote the number of copies 1 1 1 The precise definition will be given in the next subsection. of Q in \mathcal{H} . The generalized Turán problem concerns the following function: \displaystyle\mathrm{ex}(n,Q,\mathcal{F}) \displaystyle\coloneqq\max\left\{\mathrm{N}(Q,\mathcal{H})\colon\text{$v(\mathcal{H})=n$ and $\mathcal{H}$ is $\mathcal{F}$-free}\right\}. Another extensively studied variant is the spectral Turán problem, proposed by Nikiforov (see [ BS86 , Nik07 , Nik10 ] ), which concerns the maximum spectral radius of an n -vertex \mathcal{F} -free r -graph. Formally, given an r -graph \mathcal{H} on the vertex set [n] , the Lagrangian polynomial 2 2 2 Also referred to as the polynomial form of \mathcal{H} in Nikiforov’s survey [ Nik14 ] . of \mathcal{H} is defined by \displaystyle P_{\mathcal{H}}(X_{1},\ldots,X_{n})\coloneqq r!\sum_{e\in\mathcal{H}}\,\prod_{i\in e}X_{i}. (1) For a real number \alpha>0 , define the domain \displaystyle\Delta^{n-1}_{\alpha}\coloneqq\left\{(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}\colon|x_{1}|^{\alpha}+\cdots+|x_{n}|^{\alpha}=1\right\}. The \alpha -spectral radius of \mathcal{H} is then given by \displaystyle\lambda_{\alpha}(\mathcal{H})\coloneqq\max\left\{P_{\mathcal{H}}(x_{1},\ldots,x_{n})\colon(x_{1},\ldots,x_{n})\in\Delta^{n-1}_{\alpha}\right\}. The spectral Turán problem asks for the value of the following function: \displaystyle\mathrm{spex}_{\alpha}(n,\mathcal{F}) \displaystyle\coloneqq\max\left\{\lambda_{\alpha}(\mathcal{H})\colon\text{$v(\mathcal{H})=n$ and $\mathcal{H}$ is $\mathcal{F}$-free}\right\}. In this work, we initiate the study of the spectral generalized Turán problem and extend the general result of Keevash–Lenz–Mubayi [ KLM14 ] on spectral Turán problem to the spectral generalized Turán problem setting. To provide a gentle introduction, we begin with a classical example from the generalized Turán problem. 1.1 Example: the spectral Erdős Pentagon Problem Let C_{5} denote the graph on the vertex set \{1,2,3,4,5\} with edge set \displaystyle\big\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,1\}\big\}. A graph G is said to be C_{5} -colorable if there exists a homomorphism from G to C_{5} , that is, a map \phi\colon V(G)\to V(C_{5}) such that \phi(e)\in C_{5} for every e\in G . Let \mathfrak{C}_{5} denote the collection of all C_{5} -colorable graphs. In 1984, Erdős [ Erd84 ] conjectured that for every n\in\mathbb{N} , the triangle-free graph on n vertices that contains the maximum number of copies of C_{5} is C_{5} -colorable. Building on Razborov’s powerful flag algebra machinery [ Raz07 ] , his conjecture was resolved for large n independently by Grzesik [ Grz12 ] and Hatami–Hladký–Kráľ–Norine–Razborov [ HHK+13 ] , and later for all n by Lidický–Pfender [ LP18 ] . Theorem 1.1 ( [ Grz12 , HHK+13 , LP18 ] ) . For every n\in\mathbb{N} , \displaystyle\mathrm{ex}(n,C_{5},K_{3})=\max\left\{\mathrm{N}(C_{5},G)\colon\text{$G\in\mathfrak{C}_{5}$ and $v(G)=n$}\right\}. We now introduce the spectral version of Theorem 1.1 . Given a graph G , and for convenience assuming that its vertex set is [n] , we define the Lagrangian C_{5} -polynomial of G as \displaystyle P_{C_{5},G}(X_{1},\ldots,X_{n})\coloneqq\sum_{\phi\in\mathrm{Inj}(C_{5},G)}\,\prod_{i\in\phi(V(C_{5}))}X_{i}, where \mathrm{Inj}(C_{5},G) is the collection of all injective homomorphisms from C_{5} to G . For every \alpha\geq 1 , the (\alpha,C_{5}) -spectral radius of G is defined as \displaystyle\lambda_{\alpha,C_{5}}(G)\coloneqq\max\left\{P_{C_{5},G}(x_{1},\ldots,x_{n})\colon(x_{1},\ldots,x_{n})\in\Delta^{n-1}_{\alpha}\right\}. The spectral analogue of the Erdős Pentagon Theorem is as follows. Theorem 1.2 . Let \alpha>1 be a real number. There exists a constant N_{\ref{THM:C5-K3-spectral}} such that for every n\geq N_{\ref{THM:C5-K3-spectral}} , every K_{3} -free graph G on n vertices satisfies \displaystyle\lambda_{\alpha}(G)\leq\max\left\{\lambda_{\alpha}(H)\colon\text{$H\in\mathfrak{C}_{5}$ and $v(H)=n$}\right\}, with equality only if G\in\mathfrak{C}_{5} . 1.2 General definitions and main result In this subsection, we introduce the general definitions for the spectral generalized Turán problems and state the main result. Given two r -graphs Q and \mathcal{H} , a map \phi\colon V(Q)\to V(\mathcal{H}) is called a homomorphism from Q to \mathcal{H} if \phi(e)\in\mathcal{H} for every edge e\in Q . Let \mathrm{Inj}(Q,\mathcal{H}) be the set of all injective homomorphisms 3 3 3 For clarity, we assume that every r -graph is vertex-labeled, with distinct vertices assigned distinct labels. from Q to \mathcal{H} , and write \mathrm{inj}(Q,\mathcal{H})\coloneqq|\mathrm{Inj}(Q,\mathcal{H})| . The number of copies of Q in \mathcal{H} is given by \displaystyle\mathrm{N}(Q,\mathcal{H})\coloneqq\mathrm{inj}(Q,\mathcal{H})/{|\mathrm{Aut}(Q)|}, (2) where \mathrm{Aut}(Q)\coloneqq\mathrm{Inj}(Q,Q) denotes the automorphism group of Q . Following the definition in [ CL24 ] , we define the Lagrangian Q -polynomial of a hypergraph \mathcal{H} as \displaystyle P_{Q,\mathcal{H}}(X_{1},\ldots,X_{n})\coloneqq\sum_{\phi\in\mathrm{Inj}(Q,\mathcal{H})}\prod_{i\in\phi(V(Q))}X_{i}. Note that in the special case where Q=K_{r}^{r} , this reduces to the classical Lagrangian polynomial given in ( 1 ), which was first introduced by Motzkin–Straus [ MS65 ] for graphs and later extended to hypergraphs by Frankl–Rödl [ FR84 ] . Define the (\alpha,Q) -spectral radius of a hypergraph \mathcal{H} by \displaystyle\lambda_{\alpha,Q}(\mathcal{H})\coloneqq\max\left\{P_{Q,\mathcal{H}}(x_{1},\ldots,x_{n})\colon(x_{1},\ldots,x_{n})\in\Delta^{n-1}_{\alpha}\right\}. The (\alpha,Q) -spectral Turán number of \mathcal{F} is then defined as \displaystyle\mathrm{spex}_{\alpha}(n,Q,\mathcal{F}) \displaystyle\coloneqq\max\left\{\lambda_{\alpha,Q}(\mathcal{H})\colon\text{$v(\mathcal{H})=n$ and $\mathcal{H}$ is $\mathcal{F}$-free}\right\}. Suppose that the number of vertices in Q is q . For our purposes, it will be convenient to work with the following definition instead of \mathrm{ex}(n,Q,\mathcal{F}) : \displaystyle\mathrm{inj}(n,Q,\mathcal{F})\coloneqq\max\left\{\mathrm{inj}(Q,\mathcal{H})\colon\text{$v(\mathcal{H})=n$ and $\mathcal{H}$ is $\mathcal{F}$-free}\right\}. Define the limit \displaystyle\hat{\pi}(Q,\mathcal{F})\coloneqq\lim_{n\to\infty}{\mathrm{inj}(n,Q,\mathcal{F})}/{n^{q}}. Note from ( 2 ) that \mathrm{ex}(n,Q,\mathcal{F})={\mathrm{inj}(n,Q,\mathcal{F})}/{|\mathrm{Aut}(Q)|} . Thus \displaystyle\hat{\pi}(Q,\mathcal{F})=q!\cdot|\mathrm{Aut}(Q)|\cdot\pi(Q,\mathcal{F}),\quad\text{where}\quad\pi(Q,\mathcal{F})\coloneqq\lim_{n\to\infty}{\mathrm{ex}(n,Q,\mathcal{F})}/{\binom{n}{q}}. By substituting the vector (n^{-1/\alpha},\ldots,n^{-1/\alpha})\in\Delta_{\alpha}^{n-1} into the polynomial P_{Q,\mathcal{H}} , where \mathcal{H} is an r -graph on n -vertices, we obtain the following simple inequalities. Fact 1.3 . Let \alpha\geq 1 be a real number and r\geq 2 be an integer. Let Q be an r -graph on q vertices. Then, for every n\in\mathbb{N} and every n -vertex r -graph \mathcal{H} , \displaystyle\lambda_{\alpha,Q}(\mathcal{H})\geq|\mathcal{H}|n^{-\frac{q}{\alpha}}. In particular, for every family \mathcal{F} of r -graphs, \displaystyle\mathrm{spex}_{\alpha}(n,Q,\mathcal{F})\geq{\mathrm{inj}(n,Q,\mathcal{F})}\cdot n^{-\frac{q}{\alpha}}. Conversely, Fact 1.3 provides an upper bound on the generalized Turán number: \displaystyle\mathrm{ex}(n,Q,\mathcal{F})\leq\frac{\mathrm{spex}_{\alpha}(n,Q,\mathcal{F})}{|\mathrm{Aut}(Q)|}n^{\frac{q}{\alpha}}. We now introduce definitions that extend the corresponding notions from the work of Keevash–Lenz–Mubayi [ KLM14 ] to the setting of the generalized Turán problem. Fix an r -graph Q and let q\coloneqq v(Q) be the number of vertices in Q . Let \mathcal{F} be a family of r -graphs and \mathfrak{H} be a hereditary family of \mathcal{F} -free r -graphs. Here, hereditary means that for every \mathcal{H}\in\mathfrak{H} , all subgraphs of \mathcal{H} also belong to \mathfrak{H} . For every n\in\mathbb{N} , let \displaystyle\lambda_{\alpha,Q}(n,\mathfrak{H})\coloneqq\max\left\{\lambda_{\alpha,Q}(\mathcal{H})\colon\text{$\mathcal{H}\in\mathfrak{H}$ and $v(\mathcal{H})=n$}\right\}. For