Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

Thanks for your time.

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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