"Fix $n \geq 3$ and let $K_n$ be the complete graph on $n$ vertices Let $\mathbb{K}_n$ be the class of all finite simple graphs that do NOT have $K_n$ as a subgraph.

Let $\Gamma_n$ be the Fraisse limit of $\mathbb{K}_n$. Show that $\Gamma_n$ is the unique graph such that:

  1. Every finite subgraph of $\Gamma_n$ is in $\mathbb{K}_n$, and
  2. If $X$ and $Y$ are disjoint finite sets of vertices of $\Gamma_n$, and $K_{n-1}$ is not embeddable in the restriction of $\Gamma_n$ to $X$, then there is a vertex in $\Gamma_n$ which is joined to every vertex in $X$ and to no vertex in $Y$."

I think I've solved Question 1, it seems quite straightforward. By definition, all (finite) induced subgraphs of $\Gamma_n$ will be in $\mathbb{K}_n$, and this can easily be extended to all subgraphs.

I'm not too sure how to approach Question 2, the condition "$K_{n-1}$ is not embeddable" is throwing me off. I'm thinking we have to use the fact that $\Gamma_n$ is homogeneous. I've proved that $\Gamma_n$ is regular, if that is of any help.

If needed, here's a definition of the Fraisse limit from Model Theory: "Let $L$ be a countable signature, and let $\mathbb{K}$ be a nonempty finite or countable set of finitely generated $L$-structure which has the Hereditary Property, Joint Embedding Property and the Amalgamation Property (see here for definitions). Then there exists an $L$-structure $\mathcal{D}$ (called the Fraisse limit of $\mathbb{K}$), unique up to isomorphism, such that

  • $\mathcal{D}$ is at most countable.
  • $\mathbb{K} = \text{age}(\mathcal{D})$; that is, $\mathbb{K}$ is the set of all finitely generated substructures of $\mathcal{D}$. Again, see here for a definition.
  • $\mathcal{D}$ is homogeneous; that is, any isomorphism between finitely generated substructures of $\mathcal{D}$ extends to an automorphism of $\mathcal{D}$."

In the language of graphs, an $L$-structure is a graph, and a finitely generated substructure is an induced subgraph.

Thank you!


I'll explain why $\Gamma_n$ satisfies property 2.

Suppose $X$ and $Y$ are disjoint subsets of $\Gamma_n$ and $K_{n-1}$ is not embeddable in the induced subgraph on $X$. Let $G$ be the induced subgraph on $X\cup Y$, and let $H$ be the graph obtained from $G$ by adding a single new vertex $v$ and new edges connecting $v$ to every element of $X$ (but no element of $Y$). Then you can check that $K_n$ is not embeddable in $H$.

So $H\in \mathbb{K}_n$, and hence there is an embedding $f\colon H\to \Gamma_n$. Let $g\colon G\to \Gamma_n$ be the restriction of $f$ to $G$. Then $g\colon G\to f(G)$ is an isomorphism, so it extends to an automorphism $\sigma\colon \Gamma_n\cong \Gamma_n$. Let $w = \sigma^{-1}(v)$. Then we have $wEx$ for all $x\in X$ and $\lnot wEy$ for all $y\in Y$.

So now you know that $\Gamma_n$ satisfies properties 1 and 2. Of course, you're not done with the problem - you still need to show that $\Gamma_n$ is the unique (countable!) graph satisfying properties 1 and 2. Hint: use a back-and-forth argument.


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.