Counting copies of a fixed subgraph in F-free graphs

Gerbner, Dániel and Palmer, Cory (2019) Counting copies of a fixed subgraph in F-free graphs. EUROPEAN JOURNAL OF COMBINATORICS, 82. pp. 1-22. ISSN 0195-6698 (In Press)

Preview

Text 1805.07520.pdf Download (523kB) | Preview

Abstract

Fix graphs F and H and let ex(n, H, F) denote the maximum possible number of copies of the graph H in an n-vertex F-free graph. The systematic study of this function was initiated by Alon and Shikhelman [J. Comb. Theory, B. 121 (2016)]. In this paper, we give new general bounds concerning this generalized Tur´an function. We also determine ex(n, Pk, K2,t) (where Pk is a path on k vertices) and ex(n, Ck, K2,t) asymptotically for every k and t. We also characterize the graphs F that cause the function ex(n, Ck, F) to be linear in n. In the final section we discuss a connection between the function ex(n, H, F) and Berge hypergraph problems

Actions (login required)

Edit Item