Many H-copies in graphs with a forbidden tree

DOI10.1137/19M1239052MaRDI QIDQ5204067zbMATH OpenOpenAlexFDO

Authors Shoham Letzter

Publication date 9 December 2019

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

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

zbMATH Keywords

treesextremal graph theoryTurán

Mathematics Subject Classification ID

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

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.

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}\)

Cites work

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

Cited in

(11)

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

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)