Article in press
Authors:
Title:
The generalized Turán problem of two intersecting cliques
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-10-03 , Revised: 2024-04-15 , Accepted: 2024-04-15 , Available online: 2024-04-29 , https://doi.org/10.7151/dmgt.2544
Abstract:
For $s<r$, let $B_{r,s}$ be the graph consisting of two copies of $K_r$, which
share exactly $s$ vertices. Denote by $ex(n, K_r, B_{r,s})$ the maximum number
of copies of $K_r$ in a $B_{r,s}$-free graph on $n$ vertices. About fifty years
ago, Erdős and Sós determined $ex(n,K_3,B_{3,1})$. Recently, Gowers and
Janzer showed that $ex(n,K_r,B_{r,r-1})=n^{r-1-o(1)}$. It is a natural question
to ask for $ex(n,K_r,B_{r,s})$ for general $r$ and $s$. In this paper, we mainly
consider the problem for $s=1$. Utilizing Zykov's symmetrization, we determine
the exact value of $ex(n,K_4, B_{4,1})$ for $n\geq 4$. For $r\geq 5$ and $n$
sufficiently large, by the Füredi's structure theorem we show that
$ex(n,K_r,B_{r,1})=\mathcal{N}(K_{r-2},T_{r-2}(n-2))$, where $\mathcal{N}
(K_{r-2},T_{r-2}(n-2))$ represents the number of copies of $K_{r-2}$ in the
$(r-2)$-partite Turán graph on $n-2$ vertices.
Keywords:
generalized Turán number, Zykov's symmetrization, Füredi's structure theorem
References:
- N. Alon and C. Shikhelman, Many $T$ copies in $H$-free graphs, J. Combin. Theory Ser. B 121 (2016) 146–172.
https://doi.org/10.1016/j.jctb.2016.03.004 - M. Deza, P. Erdős and P. Frankl, Intersection properties of systems of finite sets, Proc. Lond. Math. Soc. (3) 36 (1978) 369–384.
https://doi.org/10.1112/plms/s3-36.2.369 - P. Erdős, Problems and results in graph theory and combinatorial analysis, in: Proc. 5th British Combin. Conf. (1975) 169–192.
- P. Frankl and Z. Füredi, Forbidding just one intersection, J. Combin. Theory Ser. A 39 (1985) 160–176.
https://doi.org/10.1016/0097-3165(85)90035-4 - P. Frankl and N. Tokushige, Extremal Problems for Finite Sets, Stud. Math. Libr. 86 (American Mathematical Society, Providence, 2018).
https://doi.org/10.1090/stml/086 - J. Fox, A new proof of the graph removal lemma, Ann. of Math. (2) 174 (2011) 561–579.
https://doi.org/10.4007/annals.2011.174.1.17 - Z. Füredi, On finite set-systems whose every intersection is a kernel of a star, Discrete Math. 47 (1983) 129–132.
https://doi.org/10.1016/0012-365X(83)90081-X - D. Gerbner, Generalized Turán results for disjoint cliques, Discrete Math. 347(7) (2024) 114024.
https://doi.org/10.1016/j.disc.2024.114024 - D. Gerbner and B. Patkós, Generalized Turán results for intersecting cliques, Discrete Math. 347(1) (2024) 113710.
https://doi.org/10.1016/j.disc.2023.113710 - W.T. Gowers and B. Janzer, Generalizations of the Ruzsa-Szemerédi and rainbow Turán problems for cliques, Combin. Probab. Comput. 30 (2021) 591–608.
https://doi.org/10.1017/S0963548320000589 - Z. Lv, E. Győri, Z. He, N. Salia, C. Tompkins, K. Varga and X. Zhu, Generalized Turán numbers for the edge blow-up of a graph, Discrete Math. 347(1) (2024) 113682.
https://doi.org/10.1016/j.disc.2023.113682 - M. Mantel, Problem 28, Wiskundige Opgaven 10 (1907) 60–61.
- I.Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, in: Combinatorics, Proc. Fifth Hungarian Colloq. Keszthely (1976), Colloq. Math. Soc. J. Bolyai 18, (North Holland, Amsterdam-New York, 1978) 939–945..
- P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436–452.
- X. Yuan and W. Yang, On generalized Turán number of two disjoint cliques, Graphs Combin. 38(4) (2022) #116.
https://doi.org/10.1007/s00373-022-02518-7 - F. Zhang, Y. Chen, E. Győri and X. Zhu, Maximum cliques in a graph without disjoint given subgraph, Discrete Math. 347(4) (2024) 113863.
https://doi.org/10.1016/j.disc.2023.113863 - X. Zhu, Y. Chen, D. Gerbner, E. Győri and H.H. Karim, The maximum number of triangles in $F_k$-free graphs, European J. Combin. 114 (2023) 103793.
https://doi.org/10.1016/j.ejc.2023.103793 - A.A. Zykov, On some properties of linear complexes, Mat. Sb. (N.S.) 24(66) (1949) 163–188.
Close