A blow-up replaces each vertex of a graph by an independent set, and each original edge by all edges between the corresponding two sets. Replacing every vertex of by vertices gives the balanced complete multipartite blow-up .
A family of positively many -cliques forces a logarithmic balanced graph blow-up, which can also contain a matching of that many members of the family. To induct on , prune faces with few extensions, apply induction to the remaining -faces, and use a matching of those faces as one side of a bipartite incidence graph. The common neighbourhood from bipartite density estimate selects logarithmically many disjoint faces with polynomially many common extension vertices.
Cloning a vertex replaces it by several nonadjacent vertices with identical neighbourhoods. In homomorphism density, conditioning on the images of all other vertices reduces cloning to the inequality from the Jensen inequality. Iterated cloning shows that positive clique homomorphism density forces any fixed complete multipartite blow-up.
Articles by others on the same topic
There are currently no matching articles.