Expected number of triangles in tripartite graph

Question

Suppose that $G$ is a tripartite graph with vertex parts $X,Y,$ and $Z$. Assume that $e_G(X,Y)$ is the number of edges between $X$ and $Y$ and in the same way we can define $e_G(X,Z)$ and $e_G(Y,Z)$. Assume that $d_G(X,Y):=\frac{e_G(X,Y)}{|X||Y|}$ is an edge density between $X$ and $Y$.

We have this setting and I have the following three questions:

1. Is it possible to compute the number of triangles in this graph?

2. What does "expected number of triangles" mean in this context? By triangle, I mean $(x,y,z)\in X\times Y\times Z$ such that $xy,yz,xz$ are edges.

3. Is it true that expected number of triangles is $d_G(X,Y)d_G(Y,Z)d_G(X,Z)|X||Y||Z|$? If yes, then can anyone explain how to derive this answer?

I'm very confused with the notion of actual number and expected number of triangles in graph so I'd be very thankful for your help and I'll highly appreciate it!

Answer 1

Is it possible to compute the number of triangles in a tripartite graph?

Of course. For example, we can count three triangles in the following tripartite graph, $\triangle aqs, \triangle ars, \triangle bqx$.

What does "expected number of triangles" mean in this context?

Fix vertex sets $X, Y,Z$.

The keywords are "expected" and "context". Whenever we talk about "expected" value of some variable in the study of probability, we have to specify a probability distribution of that variable. For example, when we say the expected number of heads of a coin toss is $1/2$, we must have assumed that the coin is a fair coin, i.e., the probability that it shows head is the same as the probability that it shows tail. Given a coin with a different distribution of head and tail, the expected number of heads of one toss could be different, such as $0$ or $1/3$ or $(\sqrt5-1)/2$.

There are many cases of probability distributions. Our concern here is the discrete probability distribution of the tripartite graphs that we are interested in. You can imagine that we have a magical coin. Whenever it lands, it produces a tripartite graph. For each tripartite graph you are interested in, it produces that graph with some fixed probability. Each tripartite graph produced will have some number of triangles. Now you can compute the expected number of triangles produced by one toss of that magical coin.

$$\text{expected number of triangles}=\sum_{\text{a tripartite graph } G}P(G)T(G)$$ where $P(G)$ is the probability that $G$ shows up and $T(G)$ is the number of triangles in $G$.

Without specifying a probability distribution of tripartite graphs, it is simply meaningless to talk about the expected value of triangles.

An probability space $(\Omega, \Bbb P)$

Let us describe a "uniform" distribution for $G$ as a random variable. Suppose we are given vertex sets $X,Y,Z$ and $d_{XY}, d_{XZ}, d_{YZ}$ are some given constants $[0,1]$.

Let the set of all possible edges $\mathcal E:=\{\{x,y\}: x\in X, y\in Y\}\cup\{\{x,z\}: x\in X, z\in Z\}\cup\{\{y,z\}: y\in Y, z\in Z\}$. Each element of $\mathscr P(\mathcal E)$, the powerset of $\mathcal E$ defines a tripartite graph with vertex sets $X, Y, Z$ and with that element as the set of edges.

Let $\Omega := \{G\in\mathscr P(\mathcal E) : d_G(X,Y)=d_{XY}, d_G(X,Z)=d_{XZ}, d_G(Y,Z)=d_{YZ}$}.
If $d_{XY}|X|\,|Y|$ is not an integer, then $\Omega$ is empty. Henceforth, we assume $d_{XY}|X|\,|Y|,\ d_{XZ}|X|\,|Z|,\ d_{YZ}|Y|\,|Z| $ are integers.

$$|\Omega|={|X|\,|Y|\choose d_{XY}|X|\,|Y|}{|X|\,|Y|\choose d_{XZ}|X|\,|Z|}{|Y|\,|Z|\choose d_{YZ}|Y|\,|Z|}$$

The probability distribution $\Bbb P:\Omega\to\Bbb R$ is $\Bbb P(G)=\frac1{|\Omega|}$ for all $G\in\Omega$.
$(\Omega,\mathcal P)$ is the probability space that is realized by the magic coin aforementioned.

Consider random variable $\xi:\Omega\to\Bbb R$, $\xi(G):=$ number of triangles in $G$. What we want to compute, the expected number of triangles is $E[\xi]=\sum_{G\in\Omega}\xi(ω)\Bbb P(G)$.

How do we compute the expected number of triangles?

• By definition. $$\begin{aligned}&\quad E[\xi]\\ &=\sum_{G\in\Omega}(\text{number of triangles in }G)\Bbb P(G)\\ &=\frac1{|\Omega|}\sum_{G\in\Omega}\sum_{a\in X,\,p\in Y,\,s\in Z}[\triangle aps\text{ in }G] \quad\quad (\,[\triangle aps\text{ in }G] \text{ is an Iverson bracket})\\ &=\frac1{|\Omega|}\sum_{a\in X,\,p\in Y,\,s\in Z}\sum_{G\in\Omega}[\triangle aps\text{ in }G]\\ &=\frac1{|\Omega|}\sum_{a\in X,\,p\in Y,\,s\in Z}{|X|\,|Y|-1\choose d_{XY}|X|\,|Y|-1}{|X|\,|Y|-1\choose d_{XZ}|X|\,|Z|-1}{|Y|\,|Z|-1\choose d_{YZ}|Y|\,|Z|-1}\\ &=\frac1{|\Omega|}\sum_{a\in X,\,p\in Y,\,s\in Z}\frac{d_{XY}|X|\,|Y|}{|X|\,|Y|}{|X|\,|Y|\choose d_{XY}|X|\,|Y|}\cdot(\text{ factors for }(X,Z)\text{ and }(Y,Z))\\ &=\sum_{a\in X,\,p\in Y,\,s\in Z}d_{XY}\cdot(\text{ factors for }(X,Z)\text{ and }(Y,Z))\\ &=|X|\,|Y|\,|Z|d_{XY}d_{XZ}d_{YZ}\\ \end{aligned}$$

• We can see that for any $a\in X$, $p\in Y$, $s\in Z$, the probability that $\triangle aps$ is included in the tripartite graph $G$ defined by $(\Omega,\Bbb P)$, $$P(\triangle aps\text{ in } G)=P(\text{edge } ap)P(\text{edge } as)P(\text{edge } ps)=d_{XY}d_{XZ}d_{YZ}.$$ $$E[\xi]=\sum_{a\in X, p\in Y, s\in Z}P(\triangle aps)=d_{XY}d_{XZ}d_{YZ}|X|\,|Y|\,|Z|.$$ Although missing a statement or two about independent events that may need separate proof, the computation above should be pretty good for understanding.

A variation

We could define $(\Omega, \Bbb P)$ as the tripartite graph $G$ with vertex set $X, Y,Z$ where

• each edge between a point of $X$ and a point of $Y$ appears with probability $d_{XY}$ and
• similarly for $(X,Z)$ and $(Y,Z)$ and
• each edge appears or not independent of any other edge.

Then $d_G(X,Y)$ will also be a random variable, whose expectation will be $d_{XY}$. The expected number of variables in $G$ will be $d_{XY}d_{XZ}d_{YZ}|X|\,|Y|\,|Z$ still.