2025/03/20 by Yuhao Zhao, Xiande Zhang, Zhao, Yuhao +1 · 2 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2503.16229
openalex publication_date 2025/03/20 · openalex created_date 2025/10/17 · openalex updated_date 2026/07/28
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 recently initiated the systematic study of the function Ψr(n,L) and showed that Ψr(n,L)≤ (1-(1)/(3r)) ∏ℓ∈ L(n-ℓ)/(r-ℓ) for large n, improving the trivial bound from the Deza--Erdős--Frankl theorem by a factor of 1-(1)/(3r). In this article, 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, we show a Hilton--Milner-type stability result.