Counting cliques with prescribed intersection sizes
Preprint
Abstract
We study the generalized Turán problem regarding cliques with restricted intersections, which highlights the motivation from extremal set theory. Let $L=\{\ell_1,\dots,\ell_s\}\subset [0,r-1]$ be a fixed integer set with $|L|\notin \{1,r\}$ and $\ell_1<\dots<\ell_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)\le \left(1-\frac{1}{3r}\right) \prod_{\ell\in L}\frac{n-\ell}{r-\ell}$ for large $n$, improving the trivial bound from the Deza--Erdős--Frankl theorem by a factor of $1-\frac{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 $\ell_1,\dots,\ell_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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Maximum cliques in a graph without disjoint given subgraphDiscrete Mathematics, 2024
- Invitation to intersection problems for finite setsJournal of Combinatorial Theory, Series A, 2016
- Many T copies in H-free graphsJournal of Combinatorial Theory, Series B, 2016
- Uniform eventown problemsEuropean Journal of Combinatorics, 2016
- An -system on the small Witt designJournal of Combinatorial Theory, Series A, 2006
- The Complete Nontrivial-Intersection Theorem for Systems of Finite SetsJournal of Combinatorial Theory, Series A, 1996
- Families of finite sets in which no set is covered by the union ofr othersIsrael Journal of Mathematics, 1985
- On finite set-systems whose every intersection is a Kernel of a starDiscrete Mathematics, 1983
- On intersecting families of finite setsJournal of Combinatorial Theory, Series A, 1978
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETSThe Quarterly Journal of Mathematics, 1961