# Explanation of a proof of an embedding lemma of Bollobas and Thomason

I do not understand the proof of Bollobas and Thomason of an embedding lemma. There is a lot of notation to present first, then the statement of the lemma, then the precise question about the proof.

Let $$U$$ and $$W$$ be non-empty sets of vertices of a graph $$G$$. Let $$e(U,W)$$ be the number of edges with one endpoint in $$U$$ and the other in $$W$$. Let $$d(U,W)=\frac{e(U,W)}{\lvert U\rvert\lvert W\rvert}$$. The pair $$(U,W)$$ is $$\eta$$-uniform if $$\lvert d(U,W)-d(U',W')\rvert<\eta$$ whenever $$\emptyset\ne U'\subseteq U$$ and $$\emptyset\ne W'\subseteq W$$ and $$\lvert U'\rvert>\eta\lvert U\rvert$$ and $$\lvert W'\rvert>\eta\lvert W\rvert$$.

Lemma 3 (from Bollobas and Thomason, "Hereditary and Monotone Properties of Graphs" in The Mathematics of Paul Erdős II). Let $$H$$ be a graph with vertex set $$\{x_1,\dots,x_k\}$$. Let $$0<\lambda,\eta<1$$ satisfy $$k\eta\le\lambda^{k-1}$$. Let $$G$$ be a graph with vertex set $$\bigcup_{i=1}^k V_i$$ where the $$V_i$$ are disjoint sets each of order $$u\ge 1$$. Suppose that each pair $$(V_i,V_j)$$ is $$\eta$$-uniform and that $$d(V_i,V_j)\le 1-\lambda$$ if $$x_i x_j\notin E(H)$$ and that $$d(V_i,V_j)\ge \lambda$$ if $$x_i x_j\in E(H)$$.

Then there exist vertices $$v_i\in V_i$$ such that the map $$x_i\mapsto v_i$$ gives an isomorphism between $$H$$ and the subgraph of $$G$$ spanned by $$\{v_1,\dots,v_k\}$$.

In the proof, they say they may assume $$H$$ is a complete graph. Why?

I have a follow-up question that I will put in a new post.

• By the way, I mention because I didn't know for the longest time: it is not Erdös but Erdős. I have edited accordingly. May 20 '20 at 1:47
• Thanks. (For that matter, his name isn't "Paul.") Alert Springer Verlag, because I literally copied the title from the Springer Verlag site. On the cover of the book they used the "two dots" umlaut as well---a book co-edited by Ron Graham. link.springer.com/book/10.1007/978-3-642-60406-5 media.springernature.com/w306/springer-static/cover-hires/book/… (There is a different cover where they use the other mark.) So here's a question for MLA: if a book misspells a word, and one refers to the title of the book, should one correct the misspelling?
– Tri
May 20 '20 at 5:44

The reduction here is: if $$x_ix_j$$ is not an edge of $$H$$, then swap edges and non-edges between $$V_i$$ and $$V_j$$. Looking for a complete graph in the result, with vertices in specified parts, is the same as looking for a copy of $$H$$ in the original graph, and the uniformity is preserved.