Fetching the paper…

Reading the bibliography…

2011

The inducibility of blow-up graphs

Hatami, Hamed, Hirst, James, Norine, Serguei

Original
PDF
Post on X

Understand

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].

The inducibility of blow-up graphs · Around

Built on

The inducibility of graphs
Nicholas Pippenger and Martin Charles Golumbic · 1975
Earlier work this paper cites.
The maximal number of induced complete bipartite graphs
Béla Bollobás, Chiê Nara, and Shun-ichi Tachibana · 1986
Earlier work this paper cites.
Dense packings of induced subgraphs
Geoffrey Exoo · 1986
Earlier work this paper cites.
The inducibility of complete bipartite graphs
Jason I. Brown and Alexander Sidorenko · 1994
Earlier work this paper cites.

Similar

The maximal number of induced r r -partite subgraphs
Béla Bollobás, Yoshimi Egawa, Andrew Harris, and Guo Ping Jin · 1995
Cited alongside, same era.
Limits of dense graph sequences
László Lovász and Balázs Szegedy · 2006
Cited alongside, same era.
Reflection positivity, rank connectivity, and homomorphism of graphs
Michael Freedman, László Lovász, and Alexander Schrijver · 2007
Cited alongside, same era.
Flag algebras
Alexander A. Razborov · 2007
Cited alongside, same era.

Then

A measure-theoretic approach to the theory of dense hypergraphs
Original
Gábor Elek and Balázs Szegedy · 2008
Later among the works it cites.
Testability and repair of hereditary hypergraph properties
Tim Austin and Terence Tao · 2010
Later among the works it cites.
On the number of pentagons in triangle-free graphs
Original
Hamed Hatami, Jan Hladký, Daniel Král, Serguei Norine, and Alexander Razborov · 2011
Closest in time.
The inducibility of graphs on four vertices
James Hirst · 2011
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…