Many H-copies in graphs with a forbidden tree

2018/11/10 by Letzter, Shoham · 1 citation
#05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1811.04287

Abstract

For graphs H and F, let ex(n, H, F) be the maximum possible number of copies of H in an F-free graph on n vertices. The study of this function, which generalises the well-studied Turán numbers of graphs, was initiated recently by Alon and Shikhelman. We show that if F is a tree then ex(n, H, F) = Θ(n^r) for some integer r = r(H, F), thus answering one of their questions.

Cited by

• Counting large cliques in graphs with a forbidden tree

Related

• Counting large cliques in graphs with a forbidden tree
• Many T copies in H-free graphs
• Some extremal results on K_s,t-free graphs
• Survey of generalized Turán problems -- counting subgraphs
• Some sharp results on the generalized Turán numbers