Graphs with many copies of a given subgraph

MaRDI QIDQ1010658zbMATH OpenFDO

Authors Vladimir Nikiforov

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.3493, https://eudml.org/doc/129714, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1n6.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

blow up of subgraphsgraphs containing copies of subgraphsinduced copies of subgraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: We show that if a graph G of order n contains many copies of a given subgraph H, then it contains a blow-up of H of order log n.

Review text

Summary: Let \(c>0\), and \(H\) be a fixed graph of order \(r\). Every graph on \(n\) vertices containing at least \(cn^{r}\) copies of \(H\) contains a ``blow-up of \(H\) with \(r-1\) vertex classes of size \(\lfloor c^{r^{2}}\ln n\rfloor \) and one vertex class of size greater than \(n^{1-c^{r-1}}\). A similar result holds for induced copies of \(H\).

Recommendations

• The inducibility of blow-up graphs
• On the maximum number of copies of H in graphs with given size and order
• Complete partite subgraphs in dense hypergraphs
• H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups
• Many \(T\) copies in \(H\)-free graphs

Cited in

(11)

• Turán's theorem inverted
• Multiplicities of subgraphs
• A new view toward vertex decomposable graphs
• Blowup Ramsey numbers
• Stability for large forbidden subgraphs
• The inducibility of blow-up graphs
• Boolean graphs are Cohen–Macaulay
• On the maximum number of copies of H in graphs with given size and order
• On graphs that contain exactly \(k\) copies of a subgraph, and a related problem in search theory
• Blowing up Dirac's theorem
• The number of graphs with large forbidden subgraphs

This page was built for publication: Graphs with many copies of a given subgraph

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