Many H-copies in graphs with a forbidden tree

DOI10.1137/19M1239052zbMATH Open1428.05056arXiv1811.04287OpenAlexW2992144822MaRDI QIDQ5204067FDOQ5204067

Authors: Shoham Letzter 

Publication date: 9 December 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: For graphs $H$ and $F$, let $operatornameex(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'an numbers of graphs, was initiated recently by Alon and Shikhelman. We show that if $F$ is a tree then $operatornameex(n,H,F)=Theta(n^r)$ for some integer $r=r(H,F)$, thus answering one of their questions.

Full work available at URL: https://arxiv.org/abs/1811.04287

Recommendations

• Many \(T\) copies in \(H\)-free graphs
• Many \(T\) copies in \(H\)-free graphs
• Counting copies of a fixed subgraph in \(F\)-free graphs
• Generalized Turán problems for disjoint copies of graphs
• Generalized Turán problems for \(K_{2,t}\)

zbMATH Keywords

treesextremal graph theoryTurán

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Cites Work

• On the number of pentagons in triangle-free graphs
• On the maximum number of five-cycles in a triangle-free graph
• Title not available (Why is that?)
• Maximizing the number of independent sets of a fixed size
• Counting independent sets of a fixed size in graphs with a given minimum degree
• Pentagons vs. triangles
• On complete subgraphs of different orders
• The maximum number of triangles in \(C_{2k+1}\)-free graphs
• Many \(T\) copies in \(H\)-free graphs
• Title not available (Why is that?)
• The maximum number of cliques in graphs without long cycles
• Generalized forbidden subposet problems
• A note on the maximum number of triangles in a \(C_5\)-free graph
• Generalized Turán problems for disjoint copies of graphs
• Generalized Turán problems for even cycles
• Some sharp results on the generalized Turán numbers
• A generalized Turán problem and its applications
• Counting copies of a fixed subgraph in \(F\)-free graphs
• The maximum number of $P_\ell$ copies in $P_k$-free graphs
• The shifting method and generalized Turán number of matchings

Cited In (11)

• The maximum number of $P_\ell$ copies in $P_k$-free graphs
• Triangles in C5‐free graphs and hypergraphs of girth six
• Generalized planar Turán numbers
• Forbidding multiple copies of forestable graphs
• Many triangles in \(C_5\)-free graphs
• Tree densities in sparse graph classes
• Counting copies of a fixed subgraph in \(F\)-free graphs
• Unified approach to the generalized Turán problem and supersaturation
• Exact results on generalized Erdős-Gallai problems
• Many \(T\) copies in \(H\)-free graphs
• Many \(T\) copies in \(H\)-free graphs

This page was built for publication: Many H-copies in graphs with a forbidden tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5204067)