Given graphs $H$ and $F$, the generalized Tur\'{a}n number ${\rm ex}(n,H,F)$ is the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Alon and Shikhelman (J. Combin. Theory Ser. B, 2016) initiated the systematic study of generalized Tur\'{a}n problems. Recently, Gao, Wu and Xue (J. Graph Theory, 2026) asked whether every graph $F$ with chromatic number $\chi(F)=r\geq3$ and treewidth ${\rm tw}(F)\geq r$ satisfies ${\rm ex}(n,K_r,F)=\Omega(n^{r-1})$. In this note, we give a negative answer to this question for every $r\geq3$. More precisely, we prove that the graph $F_r=K_{r-3}\vee H$, where $H$ is obtained from $K_4$ by subdividing one edge once, satisfies $\chi(F_r)={\rm tw}(F_r)=r$ and \[ n^{r-1}e^{-O(\sqrt{\log n})}\leq {\rm ex}(n,K_r,F_r)=o(n^{r-1}). \] This result also disproves Conjecture 6.3 in the recent survey of Gerbner and Palmer (Electron. J. Combin., 2026).
For a family $\mathcal{F}$ of $k$-graphs, $\ex_k(n,\mathcal{F})$ denotes the maximum number of edges in an $n$-vertex $\mathcal{F}$-free $k$-graph. Let $M_{s+1}^k$ denote a matching of size $s+1$ in $k$-uniform hypergraphs. Recently, Alon and Frankl (JCTB, 2024) determined $\ex_2(n,\{M_{s+1}^2,K_{\ell+1}\})$ for all $n...
For fixed graphs $H$ and $F$, let $\ex(n,H,F)$ denote the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. In this note, we prove the generalized rational exponents conjecture, posed by Gerbner and Palmer, showing that for every rational number $\alpha\ge1$, there exist fixed graphs $H_\alpha$ and $F_\a...
For an $r$-uniform hypergraph $H$, let $\nu(H)$ be the maximum number of edges no two of which share $r-1$ vertices, and $\tau(H)$ the minimum number of $(r-1)$-sets such that every edge contains one of them. Aharoni and Zerbib conjectured that $\tau(H)\le\lceil\frac{r+1}{2}\rceil\,\nu(H)$, which for $r=3$ generalizes...
For graphs $H$ and $F$, let $\text{ex}(n,H,F)$ denote the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Gerbner, Gy\H{o}ri, Methuku, and Vizer proved that $\text{ex}(n,C_{2\ell},C_{2k})=\Theta(n^\ell)$ for $k>\ell\ge2$. They determined the leading term for $\ell=2$, but for $k>\ell\ge3$ their general...
Let $G$ be a simple graph on $n$ vertices and $e(G)$ edges. Let $\mu_1\geq \cdots \geq \mu_{n-1}\geq \mu_n=0$ be the Laplacian eigenvalues of $G$. For $k=1, \ldots, n$, let $S_k(G)=\sum_{i=1}^{k}\mu_i$. Brouwers conjecture asserts that for any $k\in\{1,\ldots, n\}$, $S_k(G)\leq e(G)+\binom{k+1}{2}$. In [Bounding the su...
For a graph $H$ and a family of graphs $\mathcal F$, let $\text{ex}(n,H,\mathcal F)$ denote the maximum number of copies of $H$ in an $\mathcal F$-free graph on $n$ vertices. For every integer $i\ge 3$, let $C_i$ denote the cycle of length $i$. For $r\ge 3$, set $\mathscr {C}_r=\{C_3,C_4,\ldots,C_r\},$ and set $\mathsc...
Zhen Liu, Chuan-Shu Wu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
