# Amalgamation of graphs

I am trying to understand the definition of amalgamation of a $n+1$-partite graph as explained here(first few lines of page 4). We have a $n+1$-partite graph $G$ with partite sets $V_0,V_1,\cdots,V_n$ and we define amalgamation of $G$ on $V_i$ as follows: Let $W_i$ be a fixed set with $|W_i|=n|V_i|$. For each set, $A\subset W_i$ with $|A|=|V_i|$, we let $G_A$ be a "copy of G" with $i$th vertex class $V_i(G_A)=A$, all other classes disjoint. What does this mean? Classes will be disjoint for they are from different partite sets anyway.

I am trying to construct a small example as follows: Let $G$ be $K_{2,3,2}$. Suppose $V_0=\{v_1,v_2\}$, $V_1=\{w_1,w_2,w_3\}$ and $V_2=\{x_1,x_2\}$. Let $W_0=\{a_1,a_2,a_3,a_4\}$ and $A=\{a_1,a_2\}$. Now is $G_A$ the complete 3-partite graph with classes $\{a_1,a_2\},\{w_1,w_2,w_3\},\{x_1,x_2\}$?

The definition of amalgamation is as the union of all such graphs $G_A$. Does it mean the collection of all such $3$-partite graphs (visually speaking the graph obtained by drawing all such $3$-partite graphs side by side)?

-

Leader’s description of $A_i(G)$ isn’t the clearest thing that I’ve ever read, but I think that I have it sorted.

Start with your $(n+1)$-partite graph $G$ with vertex classes $V_0,V_1,\dots,V_n$, and let $k$ be any positive integer. Fix an index $i$ with $0\le i\le n$; we’ll form the $k$-amalgamation of $G$ on $V_i$.

Let $W_i$ be a set of $k|V_i|$ new vertices. For each $A\subseteq W_i$ with $|A|=|V_i|$ form a graph $G_A$ as follows. Let $J=\{0,1,\dots,n\}\setminus\{i\}$. For each $j\in J$ let $V_j^A$ be a set of $|V_j|$ new vertices; the vertex set of $G_A$ is

$$A\cup\bigcup_{j\in J}V_j^A\;.$$

We fill in edges to make $G_A$ an isomorphic copy of $G$: the vertex classes of $G_A$ are $A$ and the sets $V_j^A$ for $j\in J$, and the isomorphism from $G_A$ to $G$ takes $A$ to $V_i$ and $V_j^A$ to $V_j$ for $j\in J$.

Now $W_i$ has $$\binom{k|V_i|}{|V_i}$$ subsets $A$ of cardinality $|V_i|$; call this number $m$. At this point we have $m$ copies of $G$, one for each $A\subseteq W_i$ of cardinality $|V_i|$. The $mn$ vertex classes in the family $$\left\{V_j^A:A\subseteq W_i\text{ and }|A|=|V_i|\text{ and }j\in J\right\}$$ are pairwise disjoint and are also disjoint from $W_i$.

Finally, $A_i(G)$ is the union of the $m$ graphs $G_A$: its vertex set is $$W_i\cup\bigcup\left\{V_j^A:A\subseteq W_i\text{ and }|A|=|V_i|\text{ and }j\in J\right\}\;,$$ so it has $$k|V_i|+m\sum_{j\in J}|V_j|$$ vertices. If $G$ has $e$ edges, each $G_A$ also has $e$ edges, and $A_i(G)$ therefore has $em$ edges.

If you start with $G=K_{2,3,2}$ and form the $2$-amalgamation on $V_0=\{v_1,v_2\}$, $W_0$ will be a $4$-element set, so you’ll have $m=\binom42=6$ copies $G_A$ of $G$, and $A_0(G)$, the amalgamation of these copies, will have $2|V_0|+mn=4+6\cdot(3+2)=34$ vertices.

-
Thanks, much obliged. Are you sure that the original link did not have a typo and $n$ and $k$ are two distinct numbers? – Shahab Dec 5 '12 at 13:14
@Shahab: The construction makes sense whether $k=n$ or not, so I suspect that using both was intentional, though it does appear from a brief glance that the two are equal in the immediate applications of the construction. – Brian M. Scott Dec 5 '12 at 21:18