The inducibility of blow-up graphs
From MaRDI portal
Publication:462932
DOI10.1016/J.JCTB.2014.06.005zbMATH Open1301.05234arXiv1108.5699OpenAlexW2093635261MaRDI QIDQ462932FDOQ462932
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)
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].
Full work available at URL: https://arxiv.org/abs/1108.5699
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
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35)
Cites Work
- Limits of dense graph sequences
- On the number of pentagons in triangle-free graphs
- Reflection positivity, rank connectivity, and homomorphism of graphs
- Flag algebras
- A measure-theoretic approach to the theory of dense hypergraphs
- Testability and repair of hereditary hypergraph properties
- The maximal number of induced complete bipartite graphs
- The inducibility of graphs
- The maximal number of induced \(r\)-partite subgraphs
- Title not available (Why is that?)
- The inducibility of complete bipartite graphs
- The inducibility of graphs on four vertices
Cited In (28)
- The feasible region of induced graphs
- The inducibility of oriented stars
- 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 edge-statistics conjecture for \(\ell \ll k^{6/5} \)
- On the exact maximum induced density of almost all graphs and their inducibility
- Further results on the inducibility of \(d\)-ary trees
- Maximising the number of induced cycles in a graph
- Blowup polynomials and delta-matroids of graphs
- Graphs with many copies of a given subgraph
- Inducibility in binary trees and crossings in random tanglegrams
- On the inducibility of oriented graphs on four vertices
- On the 3-local profiles of graphs
- Extremal (balanced) blow-ups of trees with respect to the signless Laplacian index
- Inducibility of \(d\)-ary 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
- Extremal graphs for blow-ups of cycles and trees
- Planar graphs with the maximum number of induced 6-cycles
- The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra
- Strong forms of stability from flag algebra calculations
- On blow-ups and injectivity of quivers
- The inducibility of graphs on four vertices
- On the inducibility of cycles
- Stability from graph symmetrisation arguments with applications to inducibility
- A note on the inducibility of 4-vertex graphs
- 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)
