PreprintarXiv licencearXiv
On the large-clique version of the Erdős-Sós theorem
Abstract
For graphs H and F, let ex(n,H,F) denote the maximum number of copies of H in an F-free graph of order n. Motivated by the Erdős-Sós theorem, Gerbner and Palmer and, independently, Zhao and Peng conjectured that for every tree T of order k and every 3≤ r≤ k−1, ex(n,Kr,T)=abinomk−1r+binombr, where n=a(k−1)+b with 0≤ b<k−1. In this paper, we confirm the conjecture for r≥ ⌈ (2k−1)/3⌉ and characterize all extremal graphs.
Related
BibTeX
@misc{cheng2026largeclique,
title = {{On the large-clique version of the Erdős-Sós theorem}},
author = {Kun Cheng and Yurui Tang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.29667},
eprint = {2609.29667},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29667},
}
RIS
TY - UNPB
TI - On the large-clique version of the Erdős-Sós theorem
AU - Kun Cheng
AU - Yurui Tang
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2609.29667
UR - https://arxiv.org/abs/2609.29667
AB - For graphs H and F, let ex(n,H,F) denote the maximum number of copies of H in an F-free graph of order n. Motivated by the Erdős-Sós theorem, Gerbner and Palmer and, independently, Zhao and Peng conjectured that for every tree T of order k and every 3≤ r≤ k−1, ex(n,K_r,T)=abinomk−1r+binombr, where n=a(k−1)+b with 0≤ b<k−1. In this paper, we confirm the conjecture for r≥ ⌈ (2k−1)/3⌉ and characterize all extremal graphs.
ER -