UPCommons. Portal del coneixement obert de la UPC
Publication
Artículo científico (JournalArticle)
Counting cliques without generalized theta graphs
The generalized Turán number ex(n,T,F) is the maximum possible number of copies of T in an F-free graph on n vertices for any two graphs T and F. For the book graph Bb, there is a close connection between ex(n,K3,Bt) and the Ruzsa-Szemerédi triangle removal lemma. Motivated by this, in this paper, we study the generalized Turán problem for generalized theta graphs, a natural extension of book graphs. Our main result provides a complete characterization of the magnitude of ex(n,K3,H) when H is a generalized theta graph, indicating when it is quadratic, when it is nearly quadratic, and when it is subquadratic. Furthermore, as an application, we obtain the exact value of ex(n,Kr,kF), where F is an edge-critical generalized theta graph, and 3 <= r <= k+1, extending several recent results., Z. Wu acknowledges the bilateral AEI+DFG research project PCI2024-155080-2: SRC-ExCo– Structure, Randomness and Computational Methods in Extremal Combinatorics, and the PID2023-147202NB-I00 (COCOA: COntemporary COmbinatorics and its Applications), all funded by MICIU/AEI/10.13039/501100011033.