We study the generalized Turán problem regarding cliques with restricted intersections, which highlights the motivation from extremal set theory. Let L = {ℓ1,…,ℓs} ⊆ [0, r − 1] be a fixed integer set with ∣L∣ {1, r} and ℓ1 < ⋯ < ℓs, and let Ψr(n, L) denote the maximum number of r-cliques in an n-vertex graph whose r-cliques are L-intersecting as a family of r-subsets. Helliar and Liu (2024) recently initiated the systematic study of the function Ψr(n, L) and showed that <InlineEquation ID="IEq1"> <EquationSource Format="TEX">${\Psi _r}({n,L}) \leqslant ({1 - {1 \over {3r}}})\prod\nolimits_{\ell \in L} {{{n - \ell} \over {r - \ell}}}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <msub> <mi mathvariant="normal">Ψ</mi> <mi>r</mi> </msub> </mrow> <mo stretchy="false">(</mo> <mrow> <mi>n</mi> <mo>,</mo> <mi>L</mi> </mrow> <mo stretchy="false">)</mo> <mo>⩽</mo> <mo stretchy="false">(</mo> <mrow> <mn>1</mn> <mo>−</mo> <mrow> <mfrac> <mn>1</mn> <mrow> <mn>3</mn> <mi>r</mi> </mrow> </mfrac> </mrow> </mrow> <mo stretchy="false">)</mo> <msub> <mo movablelimits="false">∏</mo> <mrow> <mi>ℓ</mi> <mo>∈</mo> <mi>L</mi> </mrow> </msub> <mrow> <mrow> <mfrac> <mrow> <mi>n</mi> <mo>−</mo> <mi>ℓ</mi> </mrow> <mrow> <mi>r</mi> <mo>−</mo> <mi>ℓ</mi> </mrow> </mfrac> </mrow> </mrow> </math></EquationSource> </InlineEquation> for large n, improving the trivial bound from the Deza-Erdős-Frankl theorem by a factor of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">${1 - {1 \over {3r}}}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mn>1</mn> <mo>−</mo> <mrow> <mfrac> <mn>1</mn> <mrow> <mn>3</mn> <mi>r</mi> </mrow> </mfrac> </mrow> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we improve their result by showing that as n goes to infinity, Ψr(n, L) = Θr,L(n∣L∣) if and only if ℓ1,…,ℓs, r form an arithmetic progression and fully determining the corresponding exact values of Ψr(n, L) for sufficiently large n in this case. Moreover, when L = [t, r − 1], for the generalized Turán extension of the Erdős-Ko-Rado theorem given by Helliar and Liu (2024), we show a Hilton-Milner-type stability result.

Counting cliques with prescribed intersection sizes

期刊论文
发表日期：

2026年2月25日

查看全文

Yuhao Zhao,
Xiande Zhang

摘要

We study the generalized Turán problem regarding cliques with restricted intersections, which highlights the motivation from extremal set theory. Let L = {ℓ₁,…,ℓ_s} ⊆ [0, r − 1] be a fixed integer set with ∣L∣ {1, r} and ℓ₁ < ⋯ < ℓ_s, and let Ψ_r(n, L) denote the maximum number of r-cliques in an n-vertex graph whose r-cliques are L-intersecting as a family of r-subsets. Helliar and Liu (2024) recently initiated the systematic study of the function Ψ_r(n, L) and showed that ${\Psi _r}({n,L}) \leqslant ({1 - {1 \over {3r}}})\prod\nolimits_{\ell \in L} {{{n - \ell} \over {r - \ell}}}$ $Ψ_{r} (n, L) ⩽ (1 - \frac{1}{3 r}) \prod_{ℓ \in L} \frac{n - ℓ}{r - ℓ}$ for large n, improving the trivial bound from the Deza-Erdős-Frankl theorem by a factor of ${1 - {1 \over {3r}}}$ $1 - \frac{1}{3 r}$ . In this paper, we improve their result by showing that as n goes to infinity, Ψ_r(n, L) = Θ_r,L(n^∣L∣) if and only if ℓ₁,…,ℓ_s, r form an arithmetic progression and fully determining the corresponding exact values of Ψ_r(n, L) for sufficiently large n in this case. Moreover, when L = [t, r − 1], for the generalized Turán extension of the Erdős-Ko-Rado theorem given by Helliar and Liu (2024), we show a Hilton-Milner-type stability result.