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.

  • $\begingroup$ 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. $\endgroup$
    – LSpice
    May 20, 2020 at 1:47
  • 1
    $\begingroup$ 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? $\endgroup$
    – Tri
    May 20, 2020 at 5:44

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.