The inducibility of blow-up graphs

DOI10.1016/J.JCTB.2014.06.005MaRDI QIDQ462932zbMATH OpenOpenAlexFDO

Authors Hamed Hatami, James Hirst, Serguei Norine

Publication date 22 October 2014

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

blow-upinduced subgraphsinducibility

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35)

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

• scientific article; zbMATH DE number 4061279 (Why is no real title available?)
• A measure-theoretic approach to the theory of dense hypergraphs
• Flag algebras
• 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

(28)

• Strong forms of stability from flag algebra calculations
• On the exact maximum induced density of almost all graphs and their inducibility
• On blow-ups and injectivity of quivers
• The inducibility of graphs on four vertices
• On the inducibility of oriented graphs on four vertices
• Maximising the number of induced cycles in a graph
• Inducibility and universality for trees
• Inducibility in binary trees and crossings in random tanglegrams
• The edge-statistics conjecture for \(\ell \ll k^{6/5} \)
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• On the inducibility of cycles
• Extremal graphs for blow-ups of cycles and trees
• Inducibility of \(d\)-ary trees
• Duplication of directed graphs and exponential blow up of proofs
• A bound on the inducibility of cycles
• On the density of a graph and its blowup
• Planar graphs with the maximum number of induced 6-cycles
• Graphs with many copies of a given subgraph
• The feasible region of induced graphs
• Further results on the inducibility of \(d\)-ary trees
• A note on the inducibility of 4-vertex graphs
• Stability from graph symmetrisation arguments with applications to inducibility
• Blowup polynomials and delta-matroids of graphs
• On the 3-local profiles of graphs
• The inducibility of oriented stars
• Extremal (balanced) blow-ups of trees with respect to the signless Laplacian index
• The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra
• On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices

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)