# A binomial random multigraph

Christos Pelekis Aristotle University of Thessaloniki, Department of
Mathematics, 541 24 Thessaloniki, Greece, e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Fix a positive integer $n$, a real number $p\in(0,1]$, and a (perhaps random)
hypergraph $\mathcal{H}$ on $[n]$. We introduce and investigate the following
random multigraph model, which we denote $\mathbb{G}(n,p\,;\,\mathcal{H})$:
begin with an empty graph on $n$ vertices, which are labelled by the set
$[n]$. For every $H\in\mathcal{H}$ choose, independently from previous
choices, a doubleton from $H$, say $D=\\{i,j\\}\subset H$, uniformly at random
and then introduce an edge between the vertices $i$ and $j$ in the graph with
probability $p$, where each edge is introduced independently of all other
edges.

_Keywords_ : random multigraphs; hypergraphs; threshold functions

_MSC (2020)_ : 05C80; 05C65; 60C05; 05C82

##  1 Introduction

###  1.1 Notation and terminology

Let us begin with introducing some notation and terminology, which will remain
fixed throughout the text.

Given a positive integer $n$, we denote by $[n]$ the set $\\{1,\ldots,n\\}$.
The cardinality of a finite set $F$ is denoted $|F|$. A _hypergraph_ ,
$\mathcal{H}$, on $[n]$ is a collection of subsets of $[n]$. Let us emphasise
that we do not assume that each subset of $[n]$ appears at most once in
$\mathcal{H}$, and we allow repetitions. More precisely, $\mathcal{H}$ is a
_multi-hypergraph_ but we slightly abuse terminology and use the term
hypergraph instead. The elements of a hypergraph are referred to as
_hyperedges_ , or just _edges_.

Given a hypergraph $\mathcal{H}$ on $[n]$ and a subset $H\subset[n]$, we
denote by $m(H;\mathcal{H})$ the _multiplicity_ of $H$ in the hypergraph
$\mathcal{H}$, i.e., $m(H;\mathcal{H})$ is the number of times the set $H$
appears in the collection $\mathcal{H}$. The _degree_ of a set $A\subset[n]$
in $\mathcal{H}$, denoted $\deg_{\mathcal{H}}(A)$, is the cardinality of the
hypergraph $\\{H\in\mathcal{H}:A\subset H\\}$. When $A=\\{v\\}$ is a
singleton, we write $\deg_{\mathcal{H}}(v)$ instead of
$\deg_{\mathcal{H}}(\\{v\\})$.

A hypergraph $\mathcal{H}$ is _simple_ when $m(H;\mathcal{H})=1$, for all
$H\in\mathcal{H}$. Given a finite set $F\subset[n]$ and an integer
$k\in\\{0,1,\ldots,|F|\\}$, we denote by $\binom{F}{k}$ the simple hypergraph
consisting of all subsets of $F$ whose cardinality equals $k$. A hypergraph
$\mathcal{H}$ is said to be $k$-_uniform_ if $|H|=k$, for all
$H\in\mathcal{H}$. A $2$-uniform hypergraph is just a (multi)graph. Unless
mentioned otherwise, all hypergraphs $\mathcal{H}$ considered in the text
satisfy $|H|\geq 2$, for all $H\in\mathcal{H}$. Finally, given a simple
hypergraph, say $\mathcal{H}$, and a positive integer $m$, we denote by
$\mathcal{H}^{(\times m)}$ the hypergraph that contains each hyperedge of
$\mathcal{H}$ exactly $m$ times.

Given two sequences $\\{a_{n}\\}_{n},\\{b_{n}\\}_{n}$, we write $a_{n}\ll
b_{n}$, or $b_{n}\gg a_{n}$, when $\frac{a_{n}}{b_{n}}\to 0$, as
$n\to+\infty$. We also write $a_{n}=O(b_{n})$ if there exists a constant
$C>0$, which does not depend on $n$, and a positive integer $n_{0}$ such that
$a_{n}\leq C\cdot b_{n}$, for all $n\geq n_{0}$. Similarly, we write
$a_{n}=\Theta(b_{n})$ if there exist constants $C,c>0$, independent of $n$,
and positive integer $n_{0}$ such that $cb_{n}\leq a_{n}\leq Cb_{n}$, for all
$n\geq n_{0}$. In other words, $a_{n}$ and $b_{n}$ are of the same order.
Finally, we write $a_{n}=\Omega(b_{n})$ if there exists constant $C>0$ such
that $a_{n}\geq Cb_{n}$ for all $n$ large enough.

Given a positive integer $m$ and a real number $q\in[0,1]$, we denote by
$\textit{Bin}(m,q)$ a _binomial random variable_ of parameters $m$ and $q$.
Furthermore, given real numbers $\\{p_{s}\\}_{s\in S}\in[0,1]$, indexed by
some finite set $S$, we denote by $\mathcal{B}(p_{s};s\in S)$ the random
variable that counts the number of successes in $|S|$ independent trials,
where trial $s\in S$ has probability $p_{s}$ of being a success. The random
variable $\mathcal{B}(p_{s};s\in S)$ is referred to in the literature as a
_Poisson-Binomial distribution_. Let also $\textit{Hyp}(N,M,a)$ denote a
_hypergeometric random variable_ counting the number of successes when a
sample of size $a$ is drawn without replacement from a population of size $N$
which contains $M$ successes. Given two random variables $X,Y$, we write
$X\sim Y$ when $X$ and $Y$ have the same distribution.

In this article we shall be concerned with a model to generate random
multigraphs. A _multigraph_ is a graph which is allowed to have multiple edges
between pairs of vertices, and we shall be concerned with a random process
which generates such graphs. Random processes which generate (simple) graphs
are referred to as _random graphs_ , and constitute a classical topic of
probabilistic combinatorics. The study of random graphs is more than sixty
years old and was initiated by Gilbert [9] and Erdős & Rényi [5, 6], who
introduced two quintessential random graph models. The first, and perhaps most
studied, model is the _binomial random graph_ , denoted $\mathbb{G}(n,p)$,
which is obtained by independently introducing an edge between each pair of
vertices in an empty graph on $n$ vertices with probability $p$. The second
model is the _uniform random graph_ , denoted $\mathbb{G}(n,m)$, which is
obtained by choosing a graph uniformly at random from the set consisting of
all graphs on the vertex set $[n]$ having $m$ edges. In other words,
$\mathbb{G}(n,m)$ is a subset of $\binom{\binom{[n]}{2}}{m}$ chosen uniformly
at random. Since their introduction, the two models have been studied
extensively and have been generalized in a plethora of ways, thus generating a
substantial amount of literature. We refer the reader to [2, 4, 8, 12, 15, 18]
for excellent textbooks on the theory of random graphs.

We shall also be concerned with two extension of the above-mentioned random
graph models to hypergraphs. The _binomial random $k$-uniform hypergraph_,
denoted $\mathbb{H}_{n,q;k}$, is a $k$-uniform hypergraph $\mathcal{H}$ whose
hyperedges are obtained by independently including each element
$F\in\binom{[n]}{k}$ in $\mathcal{H}$ with probability $q$. The _uniform
random $k$-uniform hypergraph_, denoted $\mathbb{H}_{n,m;k}$, is a $k$-uniform
hypergraph $\mathcal{H}$ whose hyperedges are the sets obtained by choosing an
element from $\binom{\binom{[n]}{k}}{m}$ uniformly at random (see [8, Chapter
14]).

Random multigraph models have also attracted considerable attention due to the
fact that they are more appropriate for “real world” problems. For instance,
the need for considering models which allow multiple edges between pairs of
vertices arises in the study of social networks, where interactions between
individuals may become apparent in different contexts, or time periods (see,
for example, [17]). There is a significant amount of literature on random
multigraphs, and several models have been proposed in various contexts.
Examples include a _configuration model_ (see [18, Chapter 7]), as well as
several generalisations and variations of the binomial random graph and the
uniform random graph (see, for example, [1, 3, 7, 10, 11, 16], among many
others). In the present article we introduce and investigate the following
random multigraph model.

###  1.2 The model

A _binomial random multigraph_ , denoted $\mathbb{G}(n,p\,;\,\mathcal{H})$, is
generated as follows: Fix a positive integer $n$, a real number $p\in(0,1]$,
and a (perhaps random) hypergraph $\mathcal{H}$ on $[n]$. Begin with an empty
graph on $n$ vertices, which are labelled by the set $[n]$. For every set
$H\in\mathcal{H}$, choose, independently from previous choices, a doubleton
from $H$, say $D=\\{i,j\\}\in\binom{H}{2}$, uniformly at random and then
introduce an edge between the vertices $i$ and $j$ in the graph with
probability $p$, where each edge is introduced independently of all other
edges.

###  1.3 Relation to existing models

When $\mathcal{H}=\binom{[n]}{2}$, then
$\mathbb{G}(n,p\,;\,\binom{[n]}{2})=\mathbb{G}(n,p)$, and therefore the
binomial random graph is a special case of our model. Observe that, when
$\mathcal{H}$ contains hyperedges such that $|H|\geq 3$, the multigraph
$\mathbb{G}(n,1\,;\,\mathcal{H})$ is still random, in contrast to
$\mathbb{G}(n,1)$ which is deterministic.

A straightforward way to generalize $\mathbb{G}(n,p\,;\,\mathcal{H})$ is to
sample $m$ times (with or without replacement) a doubleton from each element
of $\mathcal{H}$, and then introduce an edge between the corresponding pairs
of vertices in the sample with probability $p$. Special cases of the model,
when the sampling is _with replacement_ , have been reported in the
literature. For example, the model
$\mathbb{G}\left(n,p\,;\,\binom{[n]}{2}^{(\times m)}\right)$ has been
investigated in [10, 13], in the setting of hypotheses testing for clustering
and classification, and may be seen as a natural generalisation of the
binomial random graph to multigraphs having at most $m$ edges between each
pair of vertices. When the sampling is _without replacement_ then, for every
$H\in\mathcal{H}$, we sample $m\leq\binom{|H|}{2}$ distinct doubletons from
$H$ uniformly at random, and then we flip a coin for every doubleton in the
sample to decide whether we join the corresponding pairs of vertices in the
graph. This model appears to be new. Observe that the $m$ distinct doubletons
that are chosen uniformly at random from $\binom{H}{2}$ correspond to a random
sub-graph of the complete graph on the vertex set $H$, and the corresponding
model, with $p=1$, may be seen as a “randomized version” of the binomial
random motif graph, which is introduced in [1].

One could also sample a different number of doubletons from each element of
$\mathcal{H}$, and even randomize this number. A bit more precisely, let
$\mathcal{H}$ be a hypergraph, and suppose that
$\\{X_{H}\\}_{H\in\mathcal{H}}$ are mutually independent random variables,
indexed by the edges of $\mathcal{H}$, taking values in the set of non-
negative integers $\\{0,1,2,\ldots\\}$. Let
$\mathbb{H}{\\{X_{H};H\in\mathcal{H}\\}}$ denote the (random) hypergraph that
contains each element $H\in\mathcal{H}$ exactly $X_{H}$ times. That is, we
draw from $X_{H}$, for each $H\in\mathcal{H}$, and then create a hypergraph
that contains each edge $H\in\mathcal{H}$ exactly $X_{H}$ times. The model
$\mathbb{G}\left(n,1\,;\,\mathbb{H}{\\{X_{B};B\in\binom{[n]}{2}\\}}\right)$ is
introduced in [3], as a mutligraph analogue of the binomial random graph
model. The model
$\mathbb{G}\left(n,1\,;\,\mathbb{H}{\\{P_{B}\,;\,B\in\binom{[n]}{2}\\}}\right)$,
where $\\{P_{B}\\}_{B\in\binom{[n]}{2})}$ are independent Poisson random
variables of given mean is introduced in [16], as a model to study biological
networks. All the aforementioned models can be considered in a more general
setting, where $\binom{[n]}{2}$ is replaced by some other hypergraph on $[n]$.
Such models correspond to a model $\mathbb{G}(n,p\,\,;\,\,\mathcal{H})$ for
which the hypergraph $\mathcal{H}$ is random, but one could consider the model
with more “exotic” random hypergraphs. For example, one could consider the
model $\mathbb{G}(n,p\,;\,\mathbb{H}_{n,k,q})$, which appears to be new. The
model $\mathbb{G}(n,p\,;\,\mathbb{H}_{n,m;k})$ reduces to $\mathbb{G}(n,m)$,
for $p=1,k=2$.

In this article we shall mainly be concerned with the model
$\mathbb{G}(n,p\,;\,\binom{[n]}{k})$, but we hope that we will be able to
report on various other models in the future.

###  1.4 Main results

Given a multigraph property, say $\mathcal{P}$, we write $G\in\mathcal{P}$
when the multigraph $G$ posses property $\mathcal{P}$. A “typical” question in
the theory of the binomial random graph model $\mathbb{G}(n,p)$ begins with a
particular graph property, say $\mathcal{P}$, and asks for values
$\\{p_{n}\\}_{n}$ for which $\mathbb{P}(\mathbb{G}(n,p_{n})\in\mathcal{P})$
tends to one, as n tends to infinity. Such questions involve the notion of
_thresholds_ and one remarkable discovery in the theory of random graphs,
which is due to Erdős and Rényi, is the fact that several graph properties
admit a threshold. That is, for several graph properties $\mathcal{P}$, there
exists a sequence $\\{p_{n}^{\ast}\\}_{n}$ such that the probability that a
random graph $G_{n}\in\mathbb{G}(n,p_{n})$ possesses $\mathcal{P}$ tends to
zero, when $p_{n}\ll p_{n}^{\ast}$, and tends to one when $p_{n}\gg
p_{n}^{\ast}$. In other words, there is a “phase transition” in this limiting
probability which transits from the property being very unlikely to the
property becoming almost certain. In this article we shall be concerned with
thresholds in binomial random multigraphs. Before being more precise, let us
first recall some definitions.

A (multi)graph property $\mathcal{P}$ is called _non-trivial_ if the empty
graph does not possess $\mathcal{P}$, while the complete graph does possess
$\mathcal{P}$. A (multi)graph property $\mathcal{P}$ is called _monotone
increasing_ if $G\in\mathcal{P}$ implies that $G+e\in\mathcal{P}$, i.e., the
property $\mathcal{P}$ is not destroyed after adding an edge $e$ to the graph
$G$. Similarly, a (multi)graph property $\mathcal{P}$ is called _monotone
decreasing_ if $G\in\mathcal{P}$ implies that $G-e\in\mathcal{P}$, i.e., the
property $\mathcal{P}$ is not destroyed by removing an edge $e$ from the graph
$G$. Clearly, a property $\mathcal{P}$ is monotone increasing if and only if
its complement is monotone decreasing, and thus any statement about an
increasing property translates to a statement about a decreasing one. Examples
of monotone increasing properties are connectivity, Hamiltonicity, triangle-
containment, among others. An example of a monotone decreasing multigraph
property is the graph being simple. For deterministic hypergraphs, the
corresponding notion of a threshold is analogous to the notion of a threshold
in $\mathbb{G}(n,p)$.

######  Definition 1 (Threshold functions).

Let $\\{\mathcal{H}_{n}\\}_{n\geq 2}$ be a sequence of hypergraphs on $[n]$,
and fix a monotone increasing (multi)graph property $\mathcal{P}$. A
_threshold function_ for $\mathcal{P}$, in the model
$\mathbb{G}(n,p\,;\,\mathcal{H}_{n})$, is a sequence $\\{c_{n}^{\ast}\\}_{n}$
such that

$\lim_{n\to\infty}\mathbb{P}(\mathbb{G}(n,p_{n}\,;\,\mathcal{H}_{n})\in\mathcal{P})=\begin{cases}0,&\text{
if }\,\,p_{n}\ll c_{n}^{\ast}\\\ 1,&\text{ if }\,\,p_{n}\gg
c_{n}^{\ast}.\end{cases}$

However, when the hypergraph is random, the corresponding notion of a
threshold has to take into account the underlying “randomness of the
hypergraph”. For example, thresholds in
$\mathbb{G}(n,p\,;\,\mathbb{H}_{n,q;k})$ are defined as follows.

######  Definition 2 (Threshold functions in
$\mathbb{G}(n,p\,;\,\mathbb{H}_{n,q;k})$).

Let $k\geq 3$ be fixed, and let $\mathcal{P}$ be a monotone increasing
(multi)graph property. A _threshold function_ for $\mathcal{P}$, in the model
$\mathbb{G}(n,p\,;\,\mathbb{H}_{n,q;k})$, is a sequence
$\\{c_{n}^{\ast}\\}_{n}$ such that

$\lim_{n\to\infty}\mathbb{P}(\mathbb{G}(n,p_{n}\,;\,\mathbb{H}_{n,q_{n};k})\in\mathcal{P})=\begin{cases}0,&\text{
if }\,\,p_{n}\cdot q_{n}\ll c_{n}^{\ast}\\\ 1,&\text{ if }\,\,p_{n}\cdot
q_{n}\gg c_{n}^{\ast}.\end{cases}$

A central line of research in the theory of random graphs is concerned with
the investigation of thresholds for various graph properties. A well-known
result, due to Bollobás and Thomason (see [8, Theorem 1.7]), asserts that
every monotone increasing graph property admits a threshold in
$\mathbb{G}(n,p)$. We believe that the Bollobás–Thomason theorem holds true
for several “well-behaved” binomial random multigraphs. For example, we
believe that the following holds true.

######  Conjecture 1.

Let $k\geq 3$ be fixed, and let $\mathcal{P}$ be a non-trivial monotone
increasing (multi)graph property. Then $\mathcal{P}$ has a threshold in
$\mathbb{G}(n,p\,;\,\binom{[n]}{k})$.

We are unable to prove Conjecture 1, though we will provide some evidence for
its validity. Our first result implies that several increasing properties
admit a “gapped threshold” in $\mathbb{G}(n,p\,;\,\binom{[n]}{k})$.

######  Theorem 1.1.

Let $k\geq 3$ be fixed, and let $\mathcal{P}$ be a non-trivial monotone
increasing (multi)graph property which admits a threshold in
$\mathbb{G}(n,p)$. Then there exist sequences $\\{b_{n}^{\ast}\\}_{n}$ and
$\\{c_{n}^{\ast}\\}_{n}$ such that

$\lim_{n\to\infty}\mathbb{P}\left(\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{k})\in\mathcal{P}\right)=\begin{cases}0,&\text{
if }\,\,p_{n}\ll b_{n}^{\ast}\\\ 1,&\text{ if }\,\,p_{n}\gg
c_{n}^{\ast}.\end{cases}$

Observe that Theorem 1.1 does not provide a “gapped threshold” for all
increasing properties $\mathcal{P}$, but only for properties that admit
thresholds in $\mathbb{G}(n,p)$. For example, it provides no information for
the property $\mathcal{P}=\,$“the graph is simple”.

The reader familiar with $\mathbb{G}(n,p)$ will have already noticed several
analogies between the binomial random graph and the binomial random multigraph
models, and we will illustrate this analogy further. Our next two results show
that the probability that the latter model possesses an increasing property
is, similarly to the former model, an increasing function of $p$, as well as
an increasing function of $\mathcal{H}$.

######  Theorem 1.2.

Fix a positive integer $n$, two real numbers $p_{1},p_{2}\in[0,1]$, and a
hypergraph $\mathcal{H}$ on $[n]$. If $p_{1}\leq p_{2}$ then, for every
monotone increasing property $\mathcal{P}$, it holds

$\mathbb{P}(\mathbb{G}(n,p_{1}\,;\,\mathcal{H})\in\mathcal{P})\leq\mathbb{P}(\mathbb{G}(n,p_{2}\,;\,\mathcal{H})\in\mathcal{P})\,.$

######  Theorem 1.3.

Fix a positive integer $n$, a real number $p\in[0,1]$, and two hypergraphs
$\mathcal{H}_{1},\mathcal{H}_{2}$ on $[n]$. If
$\mathcal{H}_{1}\subset\mathcal{H}_{2}$ then, for every monotone increasing
property $\mathcal{P}$, it holds

$\mathbb{P}(\mathbb{G}(n,p\,;\,\mathcal{H}_{1})\in\mathcal{P})\leq\mathbb{P}(\mathbb{G}(n,p\,;\,\mathcal{H}_{2})\in\mathcal{P})\,.$

We also provide some additional evidence for the validity of Conjecture 1, by
determining the limiting probability,
$\mathbb{P}(\mathbb{G}(n,p,\mathcal{H})\in\mathcal{P})$, for some graph
properties $\mathcal{P}$ in various random multigraph models. We begin with a
result which is related to the “simplicity threshold”.

######  Theorem 1.4.

Let $\mathcal{P}$ denote the property “the graph is simple”, and let $k\geq 3$
be fixed. The following hold true.

  1. 1.

If $p_{n}\ll\frac{1}{n^{k}}$, then

$\lim_{n\to\infty}\mathbb{P}\left(\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{k})\in\mathcal{P}\right)=1\,.$

  2. 2.

If $p_{n}\gg\frac{1}{n^{k-1}}$, then

$\lim_{n\to\infty}\mathbb{P}\left(\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{k})\in\mathcal{P}\right)=0\,.$

In other words, Theorem 1.4 provides estimates on the threshold function for
the property “the graph is simple”. We are unable to determine an exact
threshold for this property. It is easy to see that a threshold for the
property “the graph contains at least one edge” is $\frac{1}{n^{k}}$ (see
Lemma 5.1 below) and, since it is not unreasonable to expect that
$\mathbb{G}(n,p,\binom{[n]}{k})$ contains multiple edges as long as it has
some edges, perhaps a simplicity threshold equals $\frac{1}{n^{k}}$ as well.

Theorem 1.4 has no analogue in $\mathbb{G}(n,p)$ but, for graph properties
that make sense in both models, there seems to be an analogy between
thresholds in $\mathbb{G}(n,p)$ and $\mathbb{G}(n,p\,;\,\binom{[n]}{k})$.
However, in the latter case the calculations involving expectations and
variances of various random variables are significantly more complex. A reason
for this “complexity” is that the model $\mathbb{G}(n,p\,;\,\binom{[n]}{k})$,
for $k\geq 3$, exhibits certain “dependencies” which are not present in
$\mathbb{G}(n,p)$. Let us illustrate this a bit further.

For $B\in\binom{[n]}{2}$, let $E_{B}$ be the number of edges between the two
vertices in $B$. Then, in the model $\mathbb{G}(n,p\,;\,\binom{[n]}{k}),k\geq
3$, the random variables $\\{E_{B}\\}_{B\in\binom{[n]}{2}}$ are correlated; a
fact that complicates the calculation of moments and probabilities. For
example, in order to compute the probability that a particular triangle, say
$T$, is present in $\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{k})$, we have to
compute the probability that the two vertices of every $B\in\binom{T}{2}$ are
joined by at least one edge. The latter probability depends, among other
things, on the probability that the coin-flips corresponding to the elements
in $\mathcal{H}_{T}=\\{H\in\binom{[n]}{k}:T\subset H\\}$ resulted in $\ell$
edges between the vertices of $T$, where
$\ell\in\\{0,1,\ldots,|\mathcal{H}_{T}|\\}$, and we are unable to find a neat
way to calculate such probabilities for $k>3$. When $k=3$, then
$\mathcal{H}_{T}$ consists of a single element, a fact that simplifies the
calculations, as we show in the proof of Theorem 1.6 below. The proofs of the
following results illustrate further the aforementioned dependencies.

######  Theorem 1.5.

The property “the graph is connected” has threshold function
$\frac{\log(n)}{n^{2}}$ in $\mathbb{G}(n,p\,;\,\binom{[n]}{3})$.

Given Theorem 1.5 and bearing in mind the corresponding result in
$\mathbb{G}(n,p)$, it may be reasonable to expect that a connectivity
threshold in $\mathbb{G}(n,p\,;\,\binom{[n]}{k}),k\geq 4,$ is
$\frac{\log(n)}{n^{k-1}}$.

Having determined the connectivity threshold in
$\mathbb{G}(n,p\,;\,\binom{[n]}{3})$, a next step may be to determine the
“triangle containment” threshold in this model. A _triangle_ in a multigraph
$G$, with vertex set $[n]$, is a triplet of vertices $T\in\binom{[n]}{3}$ such
that all pairs of vertices from $T$ are joined with at least one edge. A
threshold for “triangle containment” in $\mathbb{G}(n,p\,;\,\binom{[n]}{3})$
should be $\frac{1}{n^{2}}$, but we are unable to prove it. We can determine
the order of the expected number of triangles in
$\mathbb{G}(n,p\,;\,\binom{[n]}{3})$, but are unable to determine the order of
its variance, due to the aforementioned “dependencies”. The next result,
combined with standard first moment arguments, implies that the expected
number of triangles in $\mathbb{G}(n,p\,;\,\mathbb{H}_{n,q;3})$ goes to zero,
when $p_{n}\cdot q_{n}\ll\frac{1}{n^{2}}$.

######  Theorem 1.6.

The expected number of triangles in $\mathbb{G}(n,p\,;\,\mathbb{H}_{n,q;3})$
is equal to

$\binom{n}{3}\cdot\left\\{(1-p\cdot
q)\cdot\left(\mathbb{P}\left(\textit{Bin}\left(n-3,\frac{pq}{3}\right)\geq
1\right)\right)^{3}+p\cdot
q\cdot\left(\mathbb{P}\left(\textit{Bin}\left(n-3,\frac{pq}{3}\right)\geq
1\right)\right)^{2}\right\\}\,.$

Note that the expected number of triangles in
$\mathbb{G}(n,p\,;\,\binom{[n]}{3})$ are obtained from Theorem 1.6 for $q=1$.
The expected number of triangles in $\mathbb{G}(n,p\,;\,\mathbb{H}_{n,m;3})$
is of similar form and illustrates the, rather intuitive, idea that
$\mathbb{G}(n,p\,;\,\mathbb{H}_{n,q;3})$ and
$\mathbb{G}(n,p\,;\,\mathbb{H}_{n,m;3})$ should be “close” to each other when
$q=\frac{m}{\binom{n}{3}}$.

######  Theorem 1.7.

The expected number of triangles in $\mathbb{G}(n,p\,;\,\mathbb{H}_{n,m;3})$
is equal to

$\binom{n}{3}\cdot\left\\{\left(1-p\cdot\frac{m}{\binom{n}{3}}\right)\cdot\left(\mathbb{P}\left(\textit{Bin}(W,p)\geq
1\right)\right)^{3}+p\cdot\frac{m}{\binom{n}{3}}\cdot\left(\mathbb{P}\left(\textit{Bin}(W,p)\geq
1\right)\right)^{2}\right\\}\,,$

where $W\sim\textit{Hyp}(\binom{n}{3},n-3,m)$.

The purpose of our final result is to illustrate a bit further the above-
mentioned “complexities of calculations” for values of $k$ that are larger
than three.

######  Theorem 1.8.

The expected number of triangles in $\mathbb{G}(n,p\,;\,\binom{[n]}{4})$ is
equal to

$\binom{n}{3}\cdot\left\\{\left(1-\sum_{i=0}^{2}p_{0i}^{(n-3)}\right)+\sum_{i=0}^{2}p_{0i}^{(n-3)}\cdot\left(\mathbb{P}\left(\textit{Bin}\left(\binom{n-3}{2},\frac{p}{6}\right)\geq
1\right)\right)^{3-i}\right\\}\,,$

where $p_{0i}^{(n-3)},i=0,1,2,$ is the $(0,i)$-th element of the $(n-3)$-th
power of the following transition matrix of a homogeneous Markov chain with
state space $\\{0,1,2,3\\}$:

$P=\blockarray{ccccc}&0123\\\ \block{c[cccc]}01-p/2p/200\\\ 101-p/3p/30\\\
2001-p/6p/6\\\ 30001\\\ \,\,.$

###  1.5 Organisation

The remaining part of our article is organised as follows. In Section 2 we
show that a $\mathbb{G}(n,p\,;\,\mathcal{H})$ model is a mixture of models of
the form $\mathbb{G}(n,p\,;\,\mathcal{D})$, where each $\mathcal{D}$ is a
particular $2$-uniform hypergraph on $[n]$. In Section 3 we collect some
observations related to the degree distribution of vertices in various
binomial random multigraph models. In Section 4 we prove Theorems 1.2 and 1.3.
The proof of Theorem 1.1 is given in Section 5, and Theorems 1.4 and 1.5 are
proven in Section 6. Finally, the proofs of Theorems 1.6, 1.7 and 1.8 are
given in Section 7.

##  2 The model as a mixture of random multigraphs

In this section we show that the model $\mathbb{G}(n,p\,;\,\mathcal{H})$ is a
mixture of models of the form $\mathbb{G}(n,p\,;\,\mathcal{D})$, for a
particular class of $2$-uniform hypergraphs $\mathcal{D}$. This requires some
extra piece of notation.

######  Definition 3 (Shadow).

Let $\mathcal{H}=\\{H_{1},\ldots,H_{m}\\}$ be a hypergraph on $[n]$. Let
$\mathscr{S}(\mathcal{H})$ denote the class consisting of all $2$-uniform
hypergraphs $\mathcal{D}=\\{D_{1},\ldots,D_{m}\\}$, having $m$ edges, which
satisfy $D_{i}\in\binom{H_{i}}{2}$, for all $i=1,\ldots,m$. Clearly, if
$\mathcal{H}$ is $2$-uniform, then
$\mathscr{S}(\mathcal{H})=\\{\mathcal{H}\\}$. We refer to the class
$\mathscr{S}(\mathcal{H})$ as the _shadow_ of the hypergraph $\mathcal{H}$.

Observe that each $\mathcal{D}\in\mathscr{S}(\mathcal{H})$ is a $2$-uniform
hypergraph consisting of $|\mathcal{H}|$ doubletons.

######  Theorem 2.1.

Fix a positive integer $n$, a real number $p\in[0,1]$ and a hypergraph
$\mathcal{H}$ on $[n]$. Let $\mathcal{P}$ be a graph property. Then

$\mathbb{P}(\mathbb{G}(n,p\,;\,\mathcal{H})\in\mathcal{P})=\prod_{H\in\mathcal{H}}\frac{1}{\binom{|H|}{2}}\cdot\sum_{\mathcal{D}\in\mathscr{S}(\mathcal{H})}\mathbb{P}\left(\mathbb{G}(n,p\,;\,\mathcal{D})\in\mathcal{P}\right)\,,$

where $\mathscr{S}(\mathcal{H})$ is the shadow of $\mathcal{H}$.

###### Proof.

The multigraph $\mathbb{G}(n,p\,;\,\mathcal{H})$ can be equivalently generated
as follows: We first choose, independently from previous choices, a doubleton
$D\in\binom{H}{2}$ uniformly at random, for each $H\in\mathcal{H}$. This
results in a collection consisting of $|\mathcal{H}|$ doubletons, say
$D_{1},\ldots,D_{|\mathcal{H}|}$, which form a $2$-uniform hypergraph, say
$\mathcal{D}\in\mathscr{S}(\mathcal{H})$. Then, given
$\mathcal{D}\in\mathscr{S}(\mathcal{H})$, we flip a coin for every
$D\in\mathcal{D}$ to decide whether we put an edge between the vertices of
$D$, with each coin-flip being independent from all others. Hence, given
$\mathcal{D}\in\mathscr{S}(\mathcal{H})$, the probability that
$\mathbb{G}(n,p\,;\,\mathcal{H})\in\mathcal{P}$ is equal to the probability
that $\mathbb{G}(n,p\,;\,\mathcal{D})\in\mathcal{P}$. Notice that the
probability of choosing a particular $\mathcal{D}\in\mathscr{S}(\mathcal{H})$
is equal to $\prod_{H\in\mathcal{H}}\,\frac{1}{\binom{|H|}{2}}$. The result
follows from the law of total probability, upon conditioning on
$\mathcal{D}\in\mathscr{S}(\mathcal{H})$. ∎

##  3 Degree distribution

In this section we collect some observations regarding the degree distribution
of a vertex, and the number of edges between a pair of vertices in binomial
random multigraphs.

######  Proposition 3.1.

Let $G\in\mathbb{G}(n,p\,;\,\mathcal{H})$ and fix a vertex $v\in[n]$. Let
$\mathcal{H}_{v}=\\{H\in\mathcal{H}:v\in H\\}$ and, for each
$H\in\mathcal{H}_{v}$, set $p_{H}=\frac{2p}{|H|}$. Then
$\deg_{G}(v)\sim\mathcal{B}(p_{H};H\in\mathcal{H}_{v})$.

###### Proof.

Observe that vertex $v$ has a potential edge for every $H\in\mathcal{H}_{v}$.
Now, given $H\in\mathcal{H}_{v}$, the probability of choosing a doubleton
$D\in\binom{H}{2}$ such that $i\in D$ is equal to
$\frac{|H|-1}{\binom{|H|}{2}}$. Hence the probability that vertex $v$ is
adjacent to some vertex $w\in H$, is equal to
$\frac{|H|-1}{\binom{|H|}{2}}\cdot p$. In other words, the number of edges
adjacent to vertex $v$ equals the number of successes in $|\mathcal{H}_{v}|$
independent trials, where trial $H\in\mathcal{H}_{v}$ has probability
$\frac{|H|-1}{\binom{|H|}{2}}\cdot p=\frac{2p}{|H|}$ of being a success. The
result follows. ∎

######  Corollary 3.1.

Fix a positive integers $n\geq k\geq 2$, a real number $p\in[0,1]$, and let
$\mathcal{H}$ be a $k$-uniform hypergraph on $[n]$. Let
$G\in\mathbb{G}(n,p\,;\,\mathcal{H})$ and fix a vertex $v\in[n]$. Let
$\mathcal{H}_{v}=\\{H\in\mathcal{H}:v\in H\\}$. Then
$\deg_{G}(v)\sim\textit{Bin}(|\mathcal{H}_{v}|,\frac{2p}{k})$.

###### Proof.

Immediate from Proposition 3.1. ∎

In other words, the number of edges that are incident to each vertex is a
binomial random variable whose number of successes depend on the number of
$k$-sets that contain the vertex. Similar results holds true for the number of
edges between a fixed pair of vertices.

######  Proposition 3.2.

Let $G\in\mathbb{G}(n,p\,;\,\mathcal{H})$ and fix two distinct vertices
$u,v\in[n]$. Let $\mathcal{H}_{u,v}=\\{H\in\mathcal{H}:\\{u,v\\}\subset H\\}$.
Then the number of edges between vertices $u$ and $v$ is a
$\mathcal{B}(p_{H};H\in\mathcal{H}_{u,v})$ random variable, where
$p_{H}=\frac{p}{\binom{|H|}{2}}$.

###### Proof.

For every $H\in\mathcal{H}_{u,v}$, the probability of choosing the doubleton
$\\{u,v\\}$ is equal to $\frac{1}{\binom{|H|}{2}}$. Therefore, the probability
that vertex $u$ is adjacent to vertex $v$ in trial $H\in\mathcal{H}_{u,v}$ is
equal to $\frac{1}{\binom{|H|}{2}}\cdot p$. The result follows. ∎

######  Corollary 3.2.

Fix a positive integers $n\geq k\geq 2$, a real number $p\in[0,1]$, and let
$\mathcal{H}$ be a $k$-uniform hypergraph on $[n]$. Let
$G\in\mathbb{G}(n,p\,;\,\mathcal{H})$ and fix two distinct vertices
$i,j\in[n]$. Let $\mathcal{H}_{i,j}=\\{H\in\mathcal{H}:\\{i,j\\}\subset H\\}$.
Then the number of edges between the vertices $i$ and $j$ is a
$\textit{Bin}\left(|\mathcal{H}_{i,j}|\,,\,\frac{p}{\binom{k}{2}}\right)$
random variable.

###### Proof.

Immediate from Proposition 3.2. ∎

######  Proposition 3.3.

Fix positive integers $n\geq k\geq 2$ and real numbers $p,q\in[0,1]$. Let $v$
be a vertex in $G\in\mathbb{G}(n,p\,;\;\mathbb{H}_{n,q;k})$. Then
$\deg_{G}(v)\sim\textit{Bin}\left(\binom{n-1}{k-1},\frac{2p}{k}q\right)$.

###### Proof.

Let $X$ be the number of edges in $\mathbb{H}_{n,q;k}$ that contain vertex
$v$. Then $X\sim\textit{Bin}\left(\binom{n-1}{k-1},q\right)$. Now, given $X$,
it follows from Corollary 3.1 that
$\deg_{G}(v)\sim\textit{Bin}(X,\frac{2p}{k})$, and the result follows. ∎

In the case of $\mathbb{G}(n,p\,;\,\mathbb{H}_{n,m;k})$, the degree of a
vertex is a mixture of binomial random variables. Recall that
$\textit{Hyp}(N,M,a)$ denotes a hypergeometric random variable.

######  Proposition 3.4.

Fix positive integers $n\geq k\geq 2$, a real number $p\in[0,1]$ and a
positive integer $m\leq\binom{n}{k}$. Let $v$ be a vertex in
$G\in\mathbb{G}(n,p,\mathbb{H}_{n,m;k})$. Then
$\deg_{G}(v)\sim\textit{Bin}\left(W,p\right)$, where
$W\sim\textit{Hyp}\left(\binom{n}{k},\binom{n-1}{k-1},m\right)$.

###### Proof.

Let $W$ be the number of edges in $\mathbb{H}_{n,m;k}$ that contain vertex
$v$. Note that is holds
$W\sim\textit{Hyp}\left(\binom{n}{k},\binom{n-1}{k-1},m\right)$. Now, given
$W$, it follows from Corollary 3.1 that
$\deg_{G}(v)\sim\textit{Bin}(W,\frac{2p}{k})$. In other words, we have

$\displaystyle\mathbb{P}(\deg_{G}(v)=\ell)$ $\displaystyle=$
$\displaystyle\sum_{j\geq\ell}\mathbb{P}(\deg_{G}(v)=\ell\,|\,W=j)\cdot\mathbb{P}(W=j)$
$\displaystyle=$
$\displaystyle\sum_{j\geq\ell}\mathbb{P}\left(\textit{Bin}(\ell,\frac{2p}{k})=j\right)\cdot\mathbb{P}(W=j)$

and the result follows. ∎

##  4 Monotonicity

In this section we prove Theorems 1.2 and 1.3.

###### Proof of Theorem 1.2.

We may assume that $p_{1}<p_{2}$; say, $p_{2}=p_{1}+(1-p_{1})\cdot p$, for
some $p\in(0,1)$. Begin with generating a graph
$G\in\mathbb{G}(n,p_{1}\,;\,\mathcal{H})$. That is, choose, independently from
previous choices, a doubleton $D\in\binom{H}{2}$ uniformly at random from
every $H\in\mathcal{H}$. This results in $|\mathcal{H}|$ doubletons, say
$D_{1},\ldots,D_{|\mathcal{H}|}$, and for every such doubleton we,
independently, flip a coin to decide whether we introduce an edge between the
corresponding vertices in the graph; where the outcome of each coin is a
success with probability $p_{1}$. A doubleton
$D\in\\{D_{1},\ldots,D_{|\mathcal{H}|}\\}$ is said to be _bad_ if the outcome
of the corresponding coin-flip was a failure; this happens with probability
$1-p_{1}$. Now, for every bad doubleton from
$\\{D_{1},\ldots,D_{|\mathcal{H}|}\\}$, we independently introduce an edge
between the corresponding vertices in the graph $G$ with probability $p$. Let
$G^{\prime}$ be the resulting graph. Clearly, it holds $G\subset G^{\prime}$
and $G^{\prime}\in\mathbb{G}(n,p_{2}\,;\,\mathcal{H})$. If $G\in\mathcal{P}$,
then it also holds $G^{\prime}\in\mathcal{P}$, and the result follows. ∎

###### Proof of Theorem 1.3.

The proof is similar to the proof of Theorem 1.2; so we briefly sketch it.
Begin with generating a graph $G\in\mathbb{G}(n,p\,;\,\mathcal{H}_{1})$. Let
$\mathcal{H}=\mathcal{H}_{2}\setminus\mathcal{H}_{1}$. For every
$H\in\mathcal{H}$ choose a doubleton, say $D=\\{i,j\\}\in\binom{H}{2}$
uniformly at random, and then introduce an edge between the vertices $i$ and
$j$ in $G$ with probability $p$. Let $G^{\prime}$ denote the resulting graph.
Clearly, it holds $G\subset G^{\prime}$ and
$G^{\prime}\in\mathbb{G}(n,p\,;\,\mathcal{H}_{2})$. ∎

##  5 Proof of Theorem 1.1

In this section we prove Theorem 1.1. Let us begin with determining the
threshold of the simplest possible increasing graph property.

######  Lemma 5.1.

The property “the graph contains at least one edge” has threshold
$\frac{1}{|\mathcal{H}_{n}|}$ in $\mathbb{G}(n,p\,;\,\mathcal{H}_{n})$.

###### Proof.

Let $G_{n}\in\mathbb{G}(n,p_{n}\,;\,\mathcal{H}_{n})$, and observe that
$G_{n}$ is empty if and only if all $|\mathcal{H}_{n}|$ coin-tosses
corresponding to doubletons chosen from elements of $\mathcal{H}$ were
failures. In other words, it holds

$\mathbb{P}(G_{n}\text{ is
empty})=\mathbb{P}(\textit{Bin}(|\mathcal{H}_{n}|,p_{n})=0)=(1-p_{n})^{|\mathcal{H}_{n}|}\,.$

Suppose first that $p_{n}\ll\frac{1}{|\mathcal{H}_{n}|}$. Then, using the
inequality $1-x\geq e^{-2x}$, for $x\in[0,1/2]$, we obtain

$\mathbb{P}(G_{n}\text{ is empty})=(1-p_{n})^{|\mathcal{H}_{n}|}\geq
e^{-2p_{n}|\mathcal{H}_{n}|}\to 1\,,\text{ as }n\to\infty\,.$

Assume now that $p_{n}\gg\frac{1}{|\mathcal{H}_{n}|}$. Then, using the
inequality $1-x\leq e^{-x}$, for $x\in\mathbb{R}$, we obtain

$\mathbb{P}(G_{n}\text{ is empty})=(1-p_{n})^{|\mathcal{H}_{n}|}\leq
e^{-p_{n}|\mathcal{H}_{n}|}\to 0\,,\text{ as }n\to\infty\,.$

Hence $\frac{1}{|\mathcal{H}_{n}|}$ is the desired threshold. ∎

We will also need the following lemma.

######  Lemma 5.2.

Let $k\geq 3$ be fixed, and let $\\{\mathcal{H}_{n}\\}_{n}$ be a sequence of
$k$-uniform hypergraphs on $[n]$ such that
$\deg_{\mathcal{H}_{n}}(B)=\Theta(n^{k-2})$, for all $n$ and all
$B\in\binom{[n]}{2}$. Let $\mathcal{P}$ denote the monotone increasing
property “all pairs of vertices are joined by at least one edge”. Then

$\lim_{n\to+\infty}\,\mathbb{P}(\mathbb{G}(n,1\,;\,\mathcal{H}_{n})\in\mathcal{P})=1\,.$

###### Proof.

For every $B=\\{i,j\\}\in\binom{[n]}{2}$, let $Y_{B}$ denote the indicator of
the event “vertices $i$ and $j$ are joined by at least one edge”, and set
$Y=\sum_{B\in\binom{[n]}{2}}Y_{B}$. Then $Y$ counts the number of pairs of
vertices from $[n]$ that are joined by at least one edge. Note note that
$Y<\binom{n}{2}$ implies that there exists $B\in\binom{[n]}{2}$ such that
$Y_{B}=0$. Hence the union bound combined with Corollary 3.2 imply that there
exists constant $C$, which does not depend on $n$, such that

$\displaystyle\mathbb{P}\left(Y<\binom{n}{2}\right)$ $\displaystyle\leq$
$\displaystyle\sum_{B\in\binom{[n]}{2}}\mathbb{P}(Y_{B}=0)\,\leq\,\binom{n}{2}\cdot\left(1-\frac{1}{\binom{k}{2}}\right)^{C\cdot
n^{k-2}}$ $\displaystyle\leq$ $\displaystyle\binom{n}{2}\cdot e^{-\frac{C\cdot
n^{k-2}}{\binom{k}{2}}}\,=\,e^{\log(\binom{n}{2})-\frac{C\cdot
n^{k-2}}{\binom{k}{2}}}\to 0\,,$

as desired. ∎

######  Corollary 5.1.

Let $\mathcal{D}\in\mathscr{S}(\binom{[n]}{k})$ be chosen uniformly at random.
Then $\mathbb{P}(\mathcal{D}\,\text{is complete})\to 1$, as $n\to\infty$.

###### Proof.

Set $\mathcal{H}_{n}=\binom{[n]}{k}$ and note that
$\deg_{\mathcal{H}_{n}}(B)=\binom{n-2}{k-2}$ for all $B\in\binom{[n]}{2}$. Let
$\mathcal{P}$ denote the monotone increasing property “all pairs of vertices
are joined by at least one edge”. Lemma 5.2 and Theorem 2.1 imply that

$1=\lim_{n\to\infty}\,\mathbb{P}(\mathbb{G}(n,1\,;\,\mathcal{H}_{n})\in\mathcal{P})=\lim_{n\to\infty}\frac{1}{\binom{k}{2}^{|\mathcal{H}_{n}|}}\sum_{\mathcal{D}\in\mathscr{S}(\binom{[n]}{k})}\mathbb{P}(\mathbb{G}(n,1\,;\,\mathcal{D})\in\mathcal{P})\,.$

Now observe that $\mathbb{P}(\mathbb{G}(n,1\,;\,\mathcal{D})\in\mathcal{P})$
is equal to either $1$ or $0$, depending on whether $\mathcal{D}$ is complete
or not. Hence, if $\mathbf{1}_{\mathcal{D}}$ is the indicator of the event
”$\mathcal{D}$ is complete”, it holds

$\lim_{n\to\infty}\frac{1}{\binom{k}{2}^{|\mathcal{H}_{n}|}}\sum_{\mathcal{D}\in\mathscr{S}(\binom{[n]}{k})}\mathbf{1}_{\mathcal{D}}\,=\,1\,,$

as desired. ∎

We may now proceed with the proof of Theorem 1.1.

###### Proof of Theorem 1.1.

To simplify notation, let us set $\mathcal{H}_{n,k}=\binom{[n]}{k}$. Let
$\mathcal{P}$ be an increasing multigraph property which admits a threshold in
$\mathbb{G}(n,p)$. Let $\\{c_{n}^{\ast}\\}_{n}$ be a threshold for
$\mathcal{P}$ in $\mathbb{G}(n,p\,;\,\binom{[n]}{2})$, and let
$G_{n}\in\mathbb{G}(n,p_{n}\,;\,\mathcal{H}_{n})$.

Set $b_{n}^{\ast}=\frac{1}{n^{k}}$, and suppose that $p_{n}\ll b_{n}^{\ast}$.
Since $\mathbb{P}(G_{n}\text{ is
empty})\leq\mathbb{P}(G_{n}\notin\mathcal{P})$, Lemma 5.1 implies
$\mathbb{P}(G_{n}\notin\mathcal{P})\to 1$, as $n\to\infty$, and the first
statement follows.

To prove the second statement, suppose that $p_{n}\gg c_{n}^{\ast}$. Theorem
2.1 then yields

$\displaystyle\mathbb{P}(G_{n}\in\mathcal{P})$ $\displaystyle=$
$\displaystyle\binom{k}{2}^{-|\mathcal{H}_{n}|}\sum_{\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n})}\mathbb{P}(\mathbb{G}(n,p_{n}\,;\,\mathcal{D})\in\mathcal{P})$
$\displaystyle\geq$
$\displaystyle\binom{k}{2}^{-|\mathcal{H}_{n}|}\sum_{\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n}):\mathcal{D}\text{
complete}}\mathbb{P}(\mathbb{G}(n,p_{n}\,;\,\mathcal{D})\in\mathcal{P})\,.$

For every complete $\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n})$ it holds
$\mathbb{P}(\mathbb{G}(n,p_{n}\,;\,\mathcal{D})\in\mathcal{P})\geq\mathbb{P}(\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{2})\in\mathcal{P})$,
by Theorem 1.3, and hence

$\mathbb{P}(G_{n}\in\mathcal{P})\geq\binom{k}{2}^{-|\mathcal{H}_{n}|}\sum_{\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n}):\mathcal{D}\text{
complete}}\mathbb{P}(\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{2})\in\mathcal{P})=\pi_{n}\cdot\mathbb{P}(\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{2})\in\mathcal{P})\,$

where $\pi_{n}$ is the probability that a randomly selected
$\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n})$ is complete. The second statement
follows from Corollary 5.1 and the fact that
$\mathbb{P}(\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{2})\in\mathcal{P})\to 1$, as
$n\to\infty$. ∎

##  6 Thresholds

###  6.1 Proof of Theorem 1.4

Let us begin with the following observation, whose proof is included for the
sake of completeness.

######  Lemma 6.1.

Let $n\geq k\geq 3$ be positive integers, and let $\varepsilon\in(0,1]$.
Suppose that $X\sim\textit{Bin}(c\cdot
n^{k-2},\frac{1}{n^{k-1-\varepsilon}})$, for some constant $c$ which does not
depend on $n$. Then, for large enough $n$, it holds that

$\mathbb{P}(X\geq 2)\,\geq\,\frac{1}{n^{2-\varepsilon}}\,.$

###### Proof.

Assume first that $\varepsilon<1$. Since $\varepsilon\in(0,1)$, it follows
that $c\cdot n^{k-2}\leq n^{k-1-\varepsilon}$, for large enough $n$, and
therefore for such $n$ it holds

$\displaystyle\mathbb{P}(X\geq 2)\geq\mathbb{P}(X=2)$ $\displaystyle=$
$\displaystyle\binom{c\cdot
n^{k-2}}{2}\cdot\left(\frac{1}{n^{k-1-\varepsilon}}\right)^{2}\cdot\left(1-\frac{1}{n^{k-1-\varepsilon}}\right)^{c\cdot
n^{k-2}-2}$ $\displaystyle\geq$ $\displaystyle\left(\frac{c\cdot
n^{k-2}}{2}\right)^{2}\cdot\left(\frac{1}{n^{k-1-\varepsilon}}\right)^{2}\cdot\left(1-\frac{1}{n^{k-1-\varepsilon}}\right)^{n^{k-1-\varepsilon}}$
$\displaystyle\geq$ $\displaystyle\left(\frac{c\cdot
n^{k-2}}{2n^{k-1-\varepsilon}}\right)^{2}\cdot\frac{1}{4}$ $\displaystyle=$
$\displaystyle\left(\frac{c}{4}\right)^{2}\cdot\frac{1}{n^{2-2\varepsilon}}$

where in the second estimate we have used the inequality
$\left(1-\frac{1}{x}\right)^{x}\geq\frac{1}{4}$, for $x\geq 2$. Now, for $n$
large enough, it holds
$\left(\frac{c}{4}\right)^{2}\cdot\frac{1}{n^{2-2\varepsilon}}\geq\frac{1}{n^{2-\varepsilon}}$,
and the result follows.

Suppose now that $\varepsilon=1$. If $c\geq 1$, then $\mathbb{P}(X\geq
2)\geq\mathbb{P}(\textit{Bin}(n^{k-2},\frac{1}{n^{k-2}})\geq 2)\geq 1/2$,
since the median of a $\textit{Bin}(n^{k-2},\frac{1}{n^{k-2}})$ random
variable is equal to its mean (see [14]). If $c<1$ then, in the same way as
above, we have

$\displaystyle\mathbb{P}(X\geq 2)$ $\displaystyle\geq$
$\displaystyle\left(\frac{c\cdot
n^{k-2}}{2}\right)^{2}\cdot\left(\frac{1}{n^{k-2}}\right)^{2}\cdot\left(1-\frac{1}{n^{k-2}}\right)^{n^{k-2}}$
$\displaystyle\geq$ $\displaystyle\left(\frac{c}{4}\right)^{2}\,,$

and the latter is larger than $\frac{1}{n}$, for large enough $n$. ∎

We now proceed with the proof of Theorem 1.4. Recall, from Section 2, the
definition of the shadow of a hypergraph $\mathcal{H}$ on $[n]$, which is
denoted $\mathscr{S}(\mathcal{H})$, and recall that, given $A\subset[n]$ and a
(multi)hypergraph $\mathcal{H}$ on $[n]$, we denote by $m(A;\mathcal{H})$ the
multiplicity of $A$ in $\mathcal{H}$.

Recall also that in order to generate a multigraph
$G_{n}\in\mathbb{G}(n,p\,;\,\mathcal{H})$ we randomly select
$\mathcal{D}\in\mathscr{S}(\mathcal{H})$ and then we flip a coin for each
doubleton $D\in\mathcal{D}$ to decide whether we introduce an edge between the
two vertices of $D$. We refer to this coin-flipping procedure as the _coin-
flips corresponding to $\mathcal{D}$_.

Given $\mathcal{D}\in\mathscr{S}(\binom{[n]}{k})$, for $k\geq 3$, let

$\mathcal{F}_{\mathcal{D}}=\left\\{B\in\binom{[n]}{2}:m(B;\mathcal{D})\geq
2\right\\}$

and observe that, since $|\mathcal{D}|=\binom{n}{k}=O(n^{k})$ and $k\geq 3$,
it holds $\mathcal{F}_{\mathcal{D}}\neq\emptyset$, for $n$ large enough.
Furthermore, for $n$ large enough, it holds
$|\mathcal{F}_{\mathcal{D}}|=\Omega(n^{2})$ for all
$\mathcal{D}\in\mathscr{S}(\binom{[n]}{k})$. Indeed, if this is not the case
then there exists $\mathcal{D}\in\mathscr{S}(\binom{[n]}{k})$ such that
$|\mathcal{F}_{\mathcal{D}}|=O(n^{2-\varepsilon})$, for some $\varepsilon>0$,
and therefore the fact that $m(B;\mathcal{D})\leq\binom{n-2}{k-2}$, for all
$B\in\mathcal{F}_{\mathcal{D}}$, yields

$|\mathcal{D}|\leq O(n^{2-\varepsilon})\cdot\binom{n-2}{k-2}+n^{2}\ll
O(n^{k})\,,$

contrariwise to the fact that $|\mathcal{D}|=\binom{n}{k}=\Omega(n^{k})$.
Similarly, letting

$\mathcal{F}_{\mathcal{D}}^{(k)}=\left\\{B\in\binom{[n]}{2}:m(B;\mathcal{D})=\Omega(n^{k-2})\right\\}\,,$

it holds $|\mathcal{F}_{\mathcal{D}}^{(k)}|=\Omega(n^{2})$.

###### Proof of Theorem 1.4.

To simplify notation, set $\mathcal{H}_{n}=\binom{[n]}{k}$, for $n\geq 4$, and
let $G_{n}\in\mathbb{G}(n,p_{n}\,;\,\mathcal{H}_{n})$.

  1. 1.

The result follows from Lemma 5.1 upon observing that $\mathbb{P}(G_{n}\text{
is empty})\leq\mathbb{P}(G_{n}\text{ is simple})$.

  2. 2.

Assume now that $p_{n}\gg\frac{1}{n^{k-1}}$. For each
$\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n})$, and each $B\in\binom{[n]}{2}$,
let $I_{B}(\mathcal{D})$ denote the indicator of the event “the coin-flips
corresponding to $\mathcal{D}$ resulted in at least two edges between the
vertices of $B$”.

For each $\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n})$, define the random
variable
$Y_{\mathcal{D}}=\sum_{B\in\mathcal{F}_{\mathcal{D}}}I_{B}(\mathcal{D})$. Then
$Y_{\mathcal{D}}$ counts the number of pairs of vertices from $[n]$ for which
the coin-flips corresponding to $\mathcal{D}$ resulted in at least two edges
between them. Hence

$\mathbb{P}(G_{n}\,\text{is
simple})=\binom{k}{2}^{-|\mathcal{H}_{n}|}\sum_{\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n})}\mathbb{P}(Y_{\mathcal{D}}=0)\,.$

We aim to show that $\mathbb{E}(Y_{\mathcal{D}})\to\infty$, for all
$\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n})$. For every
$\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n})$ and each
$B\in\mathcal{F}_{\mathcal{D}}$ it holds

$\mathbb{E}(I_{B}(\mathcal{D}))=\mathbb{P}(I_{B}(\mathcal{D})=1)=\mathbb{P}(\textit{Bin}(m(B;\mathcal{D}),p_{n})\geq
2)\,,$

thus

$\mathbb{E}(Y_{\mathcal{D}})=\sum_{B\in\mathcal{F}_{\mathcal{D}}}\mathbb{P}(\textit{Bin}(m(B;\mathcal{D}),p_{n})\geq
2)\geq\sum_{B\in\mathcal{F}_{\mathcal{D}}^{(k)}}\mathbb{P}(\textit{Bin}(m(B;\mathcal{D}),p_{n})\geq
2)\,.$ (1)

We distinguish two cases. Assume first that $p_{n}\geq\frac{1}{n^{k-2}}$. Then
the case $\varepsilon=1$ in Lemma 6.1 implies that, for large enough $n$ and
$B\in\mathcal{F}_{\mathcal{D}}^{(k)}$, it holds

$\mathbb{P}(\textit{Bin}(m(B;\mathcal{D}),p_{n})\geq
2)\geq\mathbb{P}\left(\textit{Bin}\left(m(B;\mathcal{D}),\frac{1}{n^{k-2}}\right)\geq
2\right)\geq\frac{1}{n}\,.$

Hence (1) yields

$\mathbb{E}(Y_{\mathcal{D}})\geq\sum_{B\in\mathcal{F}_{\mathcal{D}}^{(k)}}\frac{1}{n}=\Omega(n)\to\infty\,.$

Suppose now that $p_{n}\gg\frac{1}{n^{k-1}}$ but $p_{n}<\frac{1}{n^{k-2}}$.
Then there exists $\varepsilon\in(0,1)$ such that
$p_{n}\geq\frac{1}{n^{k-1-\varepsilon}}$, for $n$ large enough. For such $n$
and $B\in\mathcal{F}_{\mathcal{D}}^{(k)}$, Lemma 6.1 implies that

$\mathbb{P}(\textit{Bin}(m(B;\mathcal{D}),p_{n})\geq
2)\geq\mathbb{P}\left(\textit{Bin}\left(m(B;\mathcal{D}),\frac{1}{n^{k-1-\varepsilon}}\right)\geq
2\right)\geq\frac{1}{n^{2-\varepsilon}}\,,$

and (1) now yields

$\mathbb{E}(Y_{\mathcal{D}})\geq\sum_{B\in\mathcal{F}_{\mathcal{D}}^{(k)}}\frac{1}{n^{2-\varepsilon}}=\Omega(n^{\varepsilon})\to\infty\,.$

Summarising the above, we have shown that $\mathbb{E}(Y_{\mathcal{D}})$ tends
to infinity when $p_{n}\gg\frac{1}{n^{k-1}}$. We now look at the variance of
$Y_{\mathcal{D}}$. Observe that, for each
$\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n})$, the indicators
$\\{I_{B}(\mathcal{D})\\}_{B\in\mathcal{F}_{\mathcal{D}}}$ are mutually
independent; thus

$\displaystyle\text{Var}(Y_{\mathcal{D}})$ $\displaystyle=$
$\displaystyle\sum_{B\in\mathcal{F}_{\mathcal{D}}}\text{Var}(I_{B}(\mathcal{D}))$
$\displaystyle=$
$\displaystyle\sum_{B\in\mathcal{F}_{\mathcal{D}}}\left(\mathbb{E}(I_{B}(\mathcal{D}))-(\mathbb{E}(I_{B}(\mathcal{D})))^{2}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{B\in\mathcal{F}_{\mathcal{D}}}\mathbb{E}(I_{B}(\mathcal{D}))$
$\displaystyle=$ $\displaystyle\mathbb{E}(Y_{\mathcal{D}}).$

The second moment method now yields

$\mathbb{P}(Y_{\mathcal{D}}=0)\leq\frac{\text{Var}(Y_{\mathcal{D}})}{(\mathbb{E}(Y_{\mathcal{D}}))^{2}}\leq\frac{1}{\mathbb{E}(Y_{\mathcal{D}})}\to
0,\,\text{ as }n\to\infty\,.$

Summarizing the above, we have shown that
$\mathbb{P}(\mathbb{G}(n,p_{n}\,;\,\mathcal{D})\,\text{is simple})\to 0$, for
all $\mathcal{D}\in\mathscr{S}(\mathcal{H}_{n})$, and so
$\mathbb{P}(G_{n}\,\text{is simple})\to 0$. The result follows.

∎

###  6.2 Proof of Theorem 1.5

The proof is analogous to the proof of the connectivity threshold in
$\mathbb{G}(n,p)$. We begin with determining a threshold for not having
isolated vertices.

######  Theorem 6.1.

The property “Not having an isolated vertex” has threshold
$\frac{\log(n)}{n^{2}}$ in $\mathbb{G}(n,p\,;\,\binom{[n]}{3})$.

###### Proof.

For each $n\geq 1$, let $G_{n}\in\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{3})$. For
$i\in[n]$, let $I_{i}$ denote the indicator of the event “vertex $i$ is
isolated”. Then $X_{n}=\sum_{i\in[n]}I_{i}$ is the number of isolated vertices
in $G_{n}$. From Corollary 3.1 it follows that

$\mu_{n}:=\mathbb{E}(X_{n})=n\cdot\left(1-\frac{2p_{n}}{3}\right)^{\binom{n-1}{2}}\,.$

Therefore, using the inequality $1-x\leq e^{-x}$, for $x\in\mathbb{R}$, we
conclude that

$\displaystyle\mathbb{E}(X_{n})$ $\displaystyle\leq$ $\displaystyle
e^{\log(n)-\frac{2p_{n}}{3}\cdot\binom{n-1}{2}}\to 0,\,\,\text{ when
}\,p_{n}\gg\frac{\log(n)}{n^{2}}\,.$

Markov’s inequality now gives $\mathbb{P}(X_{n}\geq 1)\leq\mathbb{E}(X_{n})\to
0$, and therefore $\mathbb{P}(X_{n}=0)\to 1$.

Now assume that $p_{n}\ll\frac{\log(n)}{n^{2}}$. For $i\in[n]$, let $A_{i}$ be
the event that “vertex $i$ is isolated”. Then, using the inequality $1-x\geq
e^{-2x}$, for $x\in[0,1/2]$, we conclude, for large enough values of $n$, that

$\mu_{n}=\sum_{i\in[n]}\mathbb{P}(A_{i})=n\cdot\left(1-\frac{2p_{n}}{3}\right)^{\binom{n-1}{2}}\geq
e^{\log(n)-\frac{4p_{n}}{3}\cdot\binom{n-1}{2}}\to+\infty\,.$

Now, for any two distinct vertices $i,j\in[n]$, let
$\mathcal{H}_{i}=\\{H\in\binom{[n]}{3}:i\in H\,,\,j\notin H\\}$,
$\mathcal{H}_{j}=\\{H\in\binom{[n]}{3}:j\in H\,,\,i\notin H\\}$ and
$\mathcal{H}_{ij}=\\{H\in\binom{[n]}{3}:\\{i,j\\}\subset H\\}$. Then it holds
$|\mathcal{H}_{i}|=|\mathcal{H}_{j}|=\binom{n-2}{2}$ and
$|\mathcal{H}_{ij}|=n-2$, and so

$\mathbb{P}(A_{i}\cap
A_{j})=\left(1-\frac{2p_{n}}{3}\right)^{2\binom{n-2}{2}}\cdot(1-p_{n})^{n-2}\leq\left(1-\frac{2p_{n}}{3}\right)^{2\binom{n-2}{2}+(n-2)}.$

We conclude that

$\gamma_{n}:=\sum_{i\neq j}\mathbb{P}(A_{i}\cap A_{j})\leq
n(n-1)\left(1-\frac{2p_{n}}{3}\right)^{2\binom{n-2}{2}+(n-2)}\,,$

which yields

$\displaystyle\frac{\mathbb{E}(X_{n}^{2})}{(\mathbb{E}(X_{n}))^{2}}$
$\displaystyle=$ $\displaystyle\frac{\mu_{n}+\gamma_{n}}{\mu_{n}^{2}}$
$\displaystyle=$
$\displaystyle\frac{1}{\mu_{n}}+\frac{\gamma_{n}}{\mu_{n}^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\mu_{n}}+\frac{n(n-1)\left(1-\frac{2p_{n}}{3}\right)^{2\binom{n-2}{2}+(n-2)}}{n^{2}\cdot\left(1-\frac{2p_{n}}{3}\right)^{2\binom{n-1}{2}}}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\mu_{n}}+\frac{1}{\left(1-\frac{2p_{n}}{3}\right)^{n-2}}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\mu_{n}}+\frac{1}{\left(1-p_{n}\right)^{n}}\,.$

Now notice that the assumption $p_{n}\ll\frac{\log(n)}{n^{2}}$ implies

$\left(1-p_{n}\right)^{n}\geq e^{-2np_{n}}\to 1\,.$

Since $\mu_{n}\to+\infty$, the second moment method yields

$\mathbb{P}(X_{n}\geq
1)\geq\frac{(\mathbb{E}(X_{n}))^{2}}{\mathbb{E}(X_{n}^{2})}\to 1\,.$

This implies that $\mathbb{P}(X_{n}=0)\to 0$, and the result follows. ∎

We may now proceed with the proof of Theorem 1.5.

###### Proof of Theorem 1.5.

Suppose first that $p_{n}\ll\frac{\log(n)}{n^{2}}$. Then, Theorem 6.1 implies
that the probability that $G_{n}\in\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{3})$ has
isolated vertices tends to one, as $n$ tends to infinity; hence the same holds
true for the probability that $G_{n}\in\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{3})$
is disconnected.

Suppose now that $p_{n}\gg\frac{\log(n)}{n^{2}}$. Let $P_{n}$ be the
probability of the event that “a graph
$G_{n}\in\mathbb{G}(n,p_{n}\,;\,\binom{[n]}{3})$ is disconnected”. We aim to
show that $P_{n}$ tends to zero. For each $m\leq n/2$, let $X_{m}$ be the
number of subsets of $m$ vertices that are disconnected from all remaining
vertices of the graph $G_{n}$. Then

$P_{n}\leq\mathbb{P}\left(\sum_{m=1}^{n/2}X_{m}>0\right)\leq\sum_{m=1}^{n/2}\mathbb{E}(X_{m})\,,$

and it is therefore enough to bound $\mathbb{E}(X_{m})$. Now observe that

$\mathbb{E}(X_{m})=\binom{n}{m}\cdot\left(1-\frac{2p_{n}}{3}\right)^{(n-m)\cdot\binom{m}{2}}\cdot\left(1-\frac{2p_{n}}{3}\right)^{m\cdot\binom{n-m}{2}}\,,$

since, for each subset of $[n]$ consisting of $m$ vertices, say $M$, there are
$(n-m)\binom{m}{2}$ sets $H\in\binom{[n]}{3}$ having exactly two vertices in
$M$, and $m\cdot\binom{n-m}{2}$ sets $H\in\binom{[n]}{3}$ having exactly two
vertices in $[n]\setminus M$, and for each of the aforementioned
$H\in\binom{[n]}{3}$ the probability that no edge is introduced between a
vertex in $M$ and a vertex in $[n]\setminus M$ is equal to
$1-\frac{2p_{n}}{3}$. Hence, using the estimates $m\leq n/2$ and
$m!\geq\left(\frac{m}{e}\right)^{m}$, we conclude that

$\displaystyle\mathbb{E}(X_{m})$ $\displaystyle=$
$\displaystyle\binom{n}{m}\cdot\left(1-\frac{2p_{n}}{3}\right)^{(n-m)\cdot\binom{m}{2}+m\cdot\binom{n-m}{2}}=\binom{n}{m}\cdot\left(1-\frac{2p_{n}}{3}\right)^{\frac{m(n-m)(n-2)}{2}}$
$\displaystyle\leq$
$\displaystyle\frac{n^{m}}{m!}\cdot\left(1-\frac{2p_{n}}{3}\right)^{\frac{mn(n-2)}{4}}\leq
e^{m}\cdot n^{m}\cdot\left(1-\frac{2p_{n}}{3}\right)^{\frac{mn(n-2)}{4}}$
$\displaystyle=$ $\displaystyle\left(e\cdot
n\cdot\left(1-\frac{2p_{n}}{3}\right)^{\frac{n(n-2)}{4}}\right)^{m}\,.$

We therefore have

$\sum_{m=1}^{n/2}\mathbb{E}(X_{m})\leq\sum_{m\geq 1}\left(e\cdot
n\cdot\left(1-\frac{2p_{n}}{3}\right)^{\frac{n(n-2)}{4}}\right)^{m}\,.$

Now observe that, for $p_{n}\gg\frac{\log(n)}{n^{2}}$, it holds

$A_{n}:=e\cdot n\cdot\left(1-\frac{2p_{n}}{3}\right)^{\frac{n(n-2)}{4}}\leq
e\cdot n\cdot e^{-\frac{2p_{n}}{3}\cdot\frac{n(n-2)}{4}}=e\cdot
e^{\log(n)-\frac{2p_{n}}{3}\cdot\frac{n(n-2)}{4}}\to 0\,,$

and hence, for $n$ large enough, we have

$\sum_{m=1}^{n/2}\mathbb{E}(X_{m})\leq\frac{A_{n}}{1-A_{n}}\to 0\,.$

The result follows. ∎

##  7 Triangles

###  7.1 Proof of Theorem 1.6

Let $G_{n}\in\mathbb{G}(n,p\,;\,\mathbb{H}_{n,q;3})$. Let also $X$ count the
number of triangles in $G_{n}$, and for each potential triangle
$T\in\binom{[n]}{3}$, let $I_{T}$ be the indicator of the event “the triangle
$T$ is present in $G_{n}$”. Then
$\mathbb{E}(X)=\sum_{T\in\binom{[n]}{3}}\mathbb{P}(I_{T}=1)$, and the
linearity of expectation implies that it is enough to compute
$\mathbb{P}(I_{T}=1)$ for a particular $T\in\binom{[n]}{3}$.

Let $T\in\binom{[n]}{3}$ be fixed. Recall that for every
$H\in\mathbb{H}_{n,q;3}$ we choose a doubleton $D\in\binom{H}{3}$ uniformly at
random, and then flip a coin to decide whether we join the two vertices
vertices in $D$ with an edge. In particular, we may flip such a coin for
$H=T$; this happens with probability $q$. So assume first that
$T\in\mathbb{H}_{n,q;3}$ and let $\binom{T}{2}=\\{D_{1},D_{2},D_{3}\\}$. For
every $i=1,2,3$, let $X_{i}$ be the number of hyperedges
$H\in\mathbb{H}_{n,q;3}\setminus\\{T\\}$ such that $D_{i}\subset H$, and
observe that $X_{i}\sim\textit{Bin}(n-3,q)$, because there are $n-3$ elements
in $\binom{[n]}{3}$ that contain $D$ and each such element is included in
$\mathbb{H}_{n,q;3}$ with probability $q$. Note that the random variables
$X_{i},i=1,2,3,$ are independent and identically distributed. Let $D$ be the
doubleton which is chosen from $T$ uniformly at random. Then, given that
$T\in\mathbb{H}_{n,q;3}$, we have

$\mathbb{P}(I_{T}=1)=\sum_{i=1}^{3}\mathbb{P}(I_{T}=1\,|\,D=D_{i})\cdot\mathbb{P}(D=D_{i})=\frac{1}{3}\sum_{i=1}^{3}\mathbb{P}(I_{T}=1\,|\,D=D_{i})\,.$
(2)

Now observe that it holds

$\mathbb{E}(I_{T}\,|\,D=D_{1},X_{1},X_{2},X_{3})=(1-p)\cdot\prod_{i=1}^{3}\mathbb{P}(\textit{Bin}(X_{i},\frac{p}{3})\geq
1)+p\cdot\prod_{j\neq 1}\mathbb{P}(\textit{Bin}(X_{j},\frac{p}{3})\geq 1)\,,$

because, given $X_{1},X_{2},X_{3}$, if the outcome of the coin-flip
corresponding to $D_{1}$ is a failure, then we introduce no edge between the
two vertices of $D_{1}$ and therefore the probability that the two vertices of
every $D\in\binom{T}{3}$ are joined by at least one edge is equal
$\prod_{i=1}^{3}\mathbb{P}(\textit{Bin}(X_{i},\frac{p}{3})\geq 1)$. If the
outcome of the coin-flip corresponding to $D_{1}$ is a success, then one edge
is introduced between the two vertices of $D_{1}$ and the probability that the
two vertices of every $D\in\binom{T}{3}\setminus\\{D_{1}\\}$ are joined by at
least one edge is then equal to
$\mathbb{P}(\textit{Bin}(X_{2},\frac{p}{3})\geq
1)\cdot\mathbb{P}(\textit{Bin}(X_{3},\frac{p}{3})\geq 1)$. Now note that,
since $X_{i}\sim\textit{Bin}(n-3,q)$, for every $i=1,2,3$, it holds
$\textit{Bin}(X_{i},\frac{p}{3})\sim\textit{Bin}(n-3,\frac{pq}{3})$ and
therefore it holds
$\mathbb{E}\left(\mathbb{P}(\textit{Bin}(X_{i},\frac{p}{3})\geq
1)\right)=\mathbb{P}(\textit{Bin}(n-3,\frac{pq}{3})\geq 1)$; this together
with the independence of the random variables $X_{1},X_{2},X_{3}$ imply that

$\displaystyle\mathbb{P}(I_{T}=1\,|\,D=D_{1})$ $\displaystyle=$
$\displaystyle\mathbb{E}\left(\mathbb{E}(I_{T}\,|\,D=D_{1},X_{1},X_{2},X_{3})\right)$
$\displaystyle=$
$\displaystyle(1-p)\cdot\left(\mathbb{P}(\textit{Bin}(n-3,\frac{pq}{3})\geq
1)\right)^{3}+p\cdot\left(\mathbb{P}(\textit{Bin}(n-3,\frac{pq}{3})\geq
1)\right)^{2}\,.$

By symmetry, it holds

$\mathbb{P}(I_{T}=1\,|\,D=D_{1})=\mathbb{P}(I_{T}=1\,|\,D=D_{2})=\mathbb{P}(I_{T}=1\,|\,D=D_{3})\,,$

and we conclude from (2) that

$\mathbb{P}(I_{T}=1\,|\,T\in\mathbb{H}_{n,q;3})=(1-p)\cdot\left(\mathbb{P}(\textit{Bin}(n-3,\frac{pq}{3})\geq
1)\right)^{3}+p\cdot\left(\mathbb{P}(\textit{Bin}(n-3,\frac{pq}{3})\geq
1)\right)^{2}\,.$ (3)

Suppose now that $T\notin\mathbb{H}_{n,q;3}$. Then, using an analogous
argument as before, we have

$\mathbb{P}(I_{T}=1\,|\,T\notin\mathbb{H}_{n,q;3})=\left(\mathbb{P}(\textit{Bin}(n-3,\frac{pq}{3})\geq
1)\right)^{3}\,.$ (4)

Hence (3) and (4) imply that

$\displaystyle\mathbb{P}(I_{T}=1)$ $\displaystyle=$ $\displaystyle
q\cdot\mathbb{P}(I_{T}=1\,|\,T\in\mathbb{H}_{n,q;3})+(1-q)\cdot\mathbb{P}(I_{T}=1\,|\,T\notin\mathbb{H}_{n,q;3})$
$\displaystyle=$
$\displaystyle(1-pq)\cdot\left(\mathbb{P}(\textit{Bin}(n-3,\frac{pq}{3})\geq
1)\right)^{3}+pq\cdot\left(\mathbb{P}(\textit{Bin}(n-3,\frac{pq}{3})\geq
1)\right)^{2}\,,$

and Theorem 1.6 follows.

###  7.2 Proof of Theorem 1.7

The proof is similar to the proof of Theorem 1.6, so we sketch it.

Let $G_{n}\in\mathbb{G}(n,p\,;\,\mathbb{H}_{n,m;3})$, let $T\in\binom{[n]}{3}$
be fixed, and let $I_{T}$ be the indicator of the event “the triangle $T$ is
present in $G_{n}$”. We consider two cases. Either $T\in\mathbb{H}_{n,m;3}$ or
$T\notin\mathbb{H}_{n,m;3}$.

Suppose first that $T\in\mathbb{H}_{n,m;3}$; this happens with probability
$\frac{m}{\binom{n}{3}}$. Suppose that $\binom{T}{2}=\\{D_{1},D_{2},D_{3}\\}$
and, for $i=1,2,3$, let $W_{i}$ be the number of hyperedges in
$\mathbb{H}_{n,m;3}\setminus\\{T\\}$ that contain $D_{i}$. Observe that
$W_{i}\sim\textit{Hyp}(\binom{n-3}{3},n-3,m)$, for each $i=1,2,3$, and that
the random variables $W_{1},W_{2},W_{3}$ are independent and identically
distributed.

Upon conditioning on the outcome of the coin-flip corresponding to $T$ and on
$W_{1},W_{2},W_{3}$, we deduce that

$\mathbb{P}(I_{T}=1\,|\,T\in\mathbb{H}_{n,m;3})=(1-p)\cdot\left(\mathbb{P}(\textit{Bin}(W,p)\geq
1)\right)^{3}+p\cdot\left(\mathbb{P}(\textit{Bin}(W,p)\geq 1)\right)^{2}\,,$

where $W\sim\textit{Hyp}(\binom{n-3}{3},n-3,m)$.

Similarly, we find

$\mathbb{P}(I_{T}=1\,|\,T\notin\mathbb{H}_{n,m;3})=\left(\mathbb{P}(\textit{Bin}(W,p)\geq
1)\right)^{3}\,,$

where $W\sim\textit{Hyp}(\binom{n-3}{3},n-3,m)$, and Theorem 1.7 follows.

###  7.3 Proof of Theorem 1.8

Let $\mathcal{H}_{n}=\binom{[n]}{4}$, and let
$G_{n}\in\mathbb{G}(n,p\,;\,\mathcal{H}_{n})$. We begin with finding the
probability, say $\alpha$, that all pairs of vertices of a particular triplet
$T\in\binom{[n]}{3}$ are joined by at least one edge. Let
$\mathcal{H}_{T}=\\{H\in\mathcal{H}_{n}:T\subset H\\}$, and note that
$|\mathcal{H}_{T}|=n-3$. Also note that any element
$H\in\mathcal{H}_{n}\setminus\mathcal{H}_{T}$ satisfies $|H\cap T|\leq 2$. We
compute the desired probability via conditioning on the number of pairs of
vertices of $T$ which have been joined by at least one edge after “flipping
the coins corresponding to $\mathcal{H}_{T}$”.

We begin with choosing a doubleton uniformly at random from every element of
$\mathcal{H}_{T}$, and then flip a coin for every such doubleton in order to
decide whether we put an edge between the corresponding edges. Let $Y$ count
the number of doubletons $D\in\binom{T}{2}$ whose elements have been joined
with at least one edge in the graph. Observe that $Y\in\\{0,1,2,3\\}$, and let
$\pi_{i}=\mathbb{P}(Y=i)$, for $i=0,1,2,3$.

Now, given that $Y=0$, the probability that $T$ is a triangle in $G_{n}$
equals

$\alpha_{0}=\left\\{\mathbb{P}\left(\textit{Bin}\left(\binom{n-3}{2},\frac{p}{6}\right)\geq
1\right)\right\\}^{3}\,,$

since for every $D\in\binom{T}{2}$ there are $\binom{n-3}{2}$ elements
$H\in\mathcal{H}\setminus\mathcal{H}_{T}$ that contain $D$, and the
probability that the coin-flip corresponding to a particular
$H\in\mathcal{H}\setminus\mathcal{H}_{T}$ which contains $D$ results in an
edge between the elements of $D$ is equal to $\frac{p}{6}$. Similarly, given
that $Y=i$, for $i=1,2$, the probability that $T$ is a triangle in $G_{n}$
equals

$\alpha_{i}=\left\\{\mathbb{P}\left(\textit{Bin}\left(\binom{n-3}{2},\frac{p}{6}\right)\geq
1\right)\right\\}^{3-i}\,.$

Hence the desired probability is equal to

$\alpha=\sum_{i=0}^{3}\alpha_{i}\cdot\mathbb{P}(Y=i)\,,$

and it remains to determine the probability distribution of $Y$. Consider the
absorbing homogeneous Markov chain on the state space $S=\\{0,1,2,3\\}$ having
transition matrix given by

$P=\blockarray{ccccc}&0123\\\ \block{c[cccc]}01-p/2p/200\\\ 101-p/3p/30\\\
2001-p/6p/6\\\ 30001\\\ $

We claim that for $i=0,1,2$, $\mathbb{P}(Y=i)$ is equal to the $(0,i)$-element
of $P^{n-3}$, denoted $p_{0i}^{(n-3)}$. In other words, we claim that
$\mathbb{P}(Y=i)$ is equal to the probability that, beginning from state $0$,
a Markov chain with transition matrix $P$ will be in state $i$ after $n-3$
steps. Given the claim, we then also obtain
$\mathbb{P}(Y=3)=1-\sum_{i=0}^{2}p_{0i}^{(n-3)}$.

To prove the claim, recall that a sample from $Y$ is obtained after “flipping
the coins corresponding to $\mathcal{H}_{T}$”. We now flip the coins
corresponding to $\mathcal{H}_{T}$ one by one in a series of steps. Let
$H_{1},\ldots,H_{n-3}$ be an enumeration of the elements of $\mathcal{H}_{T}$.
For each step $t=1,\ldots,n-3$, we choose a doubleton
$D_{t}\in\binom{H_{i}}{2}$ uniformly at random and then flip a coin in order
to decide whether we join the elements of $D_{i}$ with an edge in the graph.
For each step $t=1,\ldots,n-3$, let $Y^{(t)}$ be the number of elements in
$\binom{T}{2}$ which have been joined with at least one edge at step $t$, and
set $Y^{(0)}=0$. Note that $Y^{(n-3)}=Y$ and that if $Y^{(t-1)}=j$, for some
$j=0,1,2$, then $Y^{(t)}\in\\{j,j+1\\}$. Now observe that for any $t\geq 1$
and any $j=0,1,2$ we have

$\mathbb{P}(Y^{(t)}=j+1\,|\,Y^{(t-1)}=j)=\frac{3-j}{6}\cdot p\,,$

because, given that $Y^{(t-1)}=j$, exactly $3-j$ out of the six doubletons in
$\binom{H_{t}}{2}$ are favourable (in the sense that they may potentially
introduce an edge between two previously unjoined vertices of $T$) and, given
that a favourable doubleton is selected, there is a probability $p$ that an
edge will be introduced between the two corresponding vertices of $T$. In
other words, $\\{Y^{(t)}\\}_{t\geq 0}$ is a homogeneous absorbing Markov
chain, which begins at state $0$, having transition matrix given by $P$.
Theorem 1.8 follows upon recalling that $Y=Y^{(n-3)}$.

## References

  * [1] M. Anastos, P. Michaeli, S. Petti, Thresholds in random motif graphs, In Proc.: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Vol. 145, Pages 66:1–66:19 (2019).
  * [2] B. Bollobás, Random graphs, No 73, Cambridge university press, 2001.
  * [3] A.L. Chen, F.J. Zhang, H. Li, The degree distribution of the random multigraphs, Acta Math. Sin. (Engl. Ser.) 28(5) (2012) 941–956.
  * [4] R. Durrett, Random graph dynamics, Vol. 200. No. 7. Cambridge: Cambridge university press, 2007.
  * [5] P. Erdős, A. Rényi, On random graphs I, Publ. Math. Debrecen 6 (1959) 290–297.
  * [6] P. Erdős, A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutato Int. Közl. 5 (1960) 17–61.
  * [7] L. Federico, Connectivity of Poissonian inhomogeneous random multigraphs, Electronic Journal of Graph Theory and Applications 11(1) (2023) 97–109.
  * [8] A. Frieze, M. Karoński, Introduction to random graphs, Cambridge University Press, 2016.
  * [9] E.N. Gilbert, Random graphs, Ann. Math. Stat. 30 (1959) 1141–1144.
  * [10] E. Godehardt, Probability models for random multigraphs with applications in cluster analysis, Annals of Discrete Mathematics 55 (1993) 93–108.
  * [11] C. Goldschmidt, E. Kreačić, The spread of fire on a random multigraph, Adv. in Appl. Probab. 51(1) (2019) 1–40.
  * [12] S. Janson, T. Luczak, A. Rucinski, Random graphs, Vol. 45. John Wiley & Sons, 2011.
  * [13] B. Harris, C. Godehardt, A. Horsch, Random multigraphs, classification and clustering, New trends in probability and statistics, Vol. 3 (Tartu/Pühajärve, 1994), 279–286, VSP, Utrecht, 1995.
  * [14] R. Kaas, J. M. Buhrman, Mean, Median, Mode in Binomial Distributions, Statistica Neerlandica 34(1) (1980) 13–18.
  * [15] E.M. Palmer, Graphical Evolution: an introduction to the theory of random graphs, John Wiley & Sons, Inc., 1985.
  * [16] J.M. Ranola, S. Ahn, M. Sehl, D.J. Smith, K. Lange, A Poisson model for random multigraphs, Bioinformatics 26(16) (2010) 2004–2011.
  * [17] T. Shafie, A Multigraph Approach to Social Network Analysis, Journal of Social Structure 16 (2015) 1–22.
  * [18] R. Van Der Hofstad, Random graphs and complex networks, Vol. 43, Cambridge university press, 2017.