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)

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

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)