Abstract: The blow-up of a graph is obtained by replacing every vertex with a finite collection of copies so that the copies of two vertices are adjacent if and only if the originals are. If every vertex is replaced with the same number of copies, then the resulting graph is called a balanced blow-up. We show that any graph which contains the maximum number of induced copies of a sufficiently large balanced blow-up of H is itself essentially a blow-up of H. This gives an asymptotic answer to a question in [BEHJ95].
Recommendations
- Graphs with many copies of a given subgraph
- On the exact maximum induced density of almost all graphs and their inducibility
- Extremal graphs for blow-ups of cycles and trees
- On the density of a graph and its blowup
- On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices
Cites work
- A measure-theoretic approach to the theory of dense hypergraphs
- Flag algebras
- scientific article; zbMATH DE number 4061279 (Why is no real title available?)
- Limits of dense graph sequences
- On the number of pentagons in triangle-free graphs
- Reflection positivity, rank connectivity, and homomorphism of graphs
- Testability and repair of hereditary hypergraph properties
- The inducibility of complete bipartite graphs
- The inducibility of graphs
- The inducibility of graphs on four vertices
- The maximal number of induced \(r\)-partite subgraphs
- The maximal number of induced complete bipartite graphs
Cited in
(32)- Graphs with many copies of a given subgraph
- Duplication of directed graphs and exponential blow up of proofs
- A bound on the inducibility of cycles
- Strong forms of stability from flag algebra calculations
- Extremal graphs for blow-ups of cycles and trees
- On blow-ups and injectivity of quivers
- The feasible region of induced graphs
- On the inducibility of oriented graphs on four vertices
- The edge-statistics conjecture for \(\ell \ll k^{6/5} \)
- Inducibility of \(d\)-ary trees
- Maximising the number of induced cycles in a graph
- On the exact maximum induced density of almost all graphs and their inducibility
- A note on the inducibility of 4-vertex graphs
- Further results on the inducibility of d-ary trees
- Inducibility and universality for trees
- Inducibility in binary trees and crossings in random tanglegrams
- The inducibility of graphs on four vertices
- On the 3-local profiles of graphs
- On the inducibility of cycles
- On the density of a graph and its blowup
- On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices
- Stability from graph symmetrisation arguments with applications to inducibility
- Extremal (balanced) blow-ups of trees with respect to the signless Laplacian index
- Blowup polynomials and delta-matroids of graphs
- Planar graphs with the maximum number of induced 6-cycles
- The inducibility of oriented stars
- The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra
- Inducibility in H-free graphs and inducibility of Turán graphs
- Maximising the number of properly 2-coloured 4-cycles
- A matrix criterion for harmonic morphisms of graphs with applications to graph products
- Some exact inducibility-type results for graphs via flag algebras
- Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
This page was built for publication: The inducibility of blow-up graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q462932)
