A localized approach to generalized Turán problems

Rachel Kirsch¹ ; JD Nir²

¹George Mason University
²Oakland University

The electronic journal of combinatorics, Tome 31 (2024) no. 3

Résumé

Generalized Turán problems ask for the maximum number of copies of a graph $H$ in an $n$-vertex, $F$-free graph, denoted by $ex(n,H,F)$. We show how to extend the new, localized approach of Bradač, Malec, and Tompkins to generalized Turán problems. We weight the copies of $H$ (typically taking $H=K_t$), instead of the edges, based on the size of the largest clique, path, or star containing the vertices of the copy of $H$, and in each case prove a tight upper bound on the sum of the weights. The generalized edge Turán number $mex(m,H,F)$ is the maximum number of copies of a graph $H$ in an $m$-edge, $F$-free graph. A consequence of our new localized theorems is an asymptotic determination of $ex(n,H,K_{1,r})$ for every $H$ having at least one dominating vertex and $mex(m,H,K_{1,r})$ for every $H$ having at least two dominating vertices.

Détail

DOI : 10.37236/12132

Classification : 05C30, 05C35
Mots-clés : extremal graph theory, extremal combinatorics, extremal set theory