
The Tur\'an function $ex(n,F)$ denotes the maximal number of edges in an
$F$free graph on $n$ vertices. We consider the function $h_F(n,q)$, the
minimal number of copies of $F$ in a graph on $n$ vertices with $ex(n,F)+q$
edges. The value of $h_F(n,q)$ has been extensively studied when $F$ is
bipartite or colourcritical. In this paper we investigate the simplest
remaining graph $F$, namely, two triangles sharing a vertex, and establish the
asymptotic value of $h_F(n,q)$ for $q=o(n^2)$.

We present a unified general method for the asymptotic study of graphs from
the socalled "subcritical"$ $ graph classes, which include the classes of
cacti graphs, outerplanar graphs, and seriesparallel graphs. This general
method works both in the labelled and unlabelled framework. The main results
concern the asymptotic enumeration and the limit laws of properties of random
graphs chosen from subcritical classes. We show that the number $g_n/n!$ (resp.
$g_n$) of labelled (resp. unlabelled) graphs on $n$ vertices from a subcritical
graph class ${G}=\cup_n {G_n}$ satisfies asymptotically the universal behaviour
$$ g_n = c n^{5/2} \gamma^n (1+o(1)) $$ for computable constants $c,\gamma$,
e.g. $\gamma\approx 9.38527$ for unlabelled seriesparallel graphs, and that
the number of vertices of degree $k$ ($k$ fixed) in a graph chosen uniformly at
random from $G_n$, converges (after rescaling) to a normal law as $n\to\infty$.

We consider connected components in $k$uniform hypergraphs for the following
notion of connectedness: given integers $k\ge 2$ and $1\le j \le k1$, two
$j$sets (of vertices) lie in the same $j$component if there is a sequence of
edges from one to the other such that consecutive edges intersect in at least
$j$ vertices.
We prove that certain collections of $j$sets constructed during a
breadthfirst search process on $j$components in a random $k$uniform
hypergraph are reasonably regularly distributed with high probability. We use
this property to provide a short proof of the asymptotic size of the giant
$j$component shortly after it appears.

For integers $g,m \geq 0$ and $n>0$, let $S_{g}(n,m)$ denote the graph taken
uniformly at random from the set of all graphs on $\{1,2, \ldots, n\}$ with
exactly $m=m(n)$ edges and with genus at most $g$. We use counting arguments to
investigate the components, subgraphs, maximum degree, and largest face size of
$S_{g}(n,m)$, finding that there is often different asymptotic behaviour
depending on the ratio $\frac{m}{n}$.
In our main results, we show that the probability that $S_{g}(n,m)$ contains
any given nonplanar component converges to $0$ as $n \to \infty$ for all
$m(n)$; the probability that $S_{g}(n,m)$ contains a copy of any given planar
graph converges to $1$ as $n \to \infty$ if $\liminf \frac{m}{n} > 1$; the
maximum degree of $S_{g}(n,m)$ is $\Theta (\ln n)$ with high probability if
$\liminf \frac{m}{n} > 1$; and the largest face size of $S_{g}(n,m)$ has a
threshold around $\frac{m}{n}=1$ where it changes from $\Theta (n)$ to $\Theta
(\ln n)$ with high probability.

We establish a multivariate local limit theorem for the order and size as
well as several other parameters of the kcore of the ErdosRenyi graph. The
proof is based on a novel approach to the kcore problem that replaces the
meticulous analysis of the peeling process by a generative model of graphs with
a core of a given order and size. The generative model, which is inspired by
the Warning Propagation message passing algorithm, facilitates the direct study
of properties of the core and its connections with the mantle and should
therefore be of interest in its own right.

Let $\mathbb{S}_g$ be the orientable surface of genus $g$. We prove that the
component structure of a graph chosen uniformly at random from the class
$\mathcal{S}_g(n,m)$ of all graphs on vertex set $[n]=\{1,\dotsc,n\}$ with $m$
edges embeddable on $\mathbb{S}_g$ features two phase transitions. The first
phase transition mirrors the classical phase transition in the
Erd\H{o}sR\'enyi random graph $G(n,m)$ chosen uniformly at random from all
graphs with vertex set $[n]$ and $m$ edges. It takes place at
$m=\frac{n}{2}+O(n^{2/3})$, when a unique largest component, the socalled
\emph{giant component}, emerges. The second phase transition occurs at $m =
n+O(n^{3/5})$, when the giant component covers almost all vertices of the
graph. This kind of phenomenon is strikingly different from $G(n,m)$ and has
only been observed for graphs on surfaces. Moreover, we derive an asymptotic
estimation of the number of graphs in $\mathcal{S}_g(n,m)$ throughout the
regimes of these two phase transitions.

The jigsaw percolation process on graphs was introduced by Brummitt,
Chatterjee, Dey, and Sivakoff as a model of collaborative solutions of puzzles
in social networks. Percolation in this process may be viewed as the joint
connectedness of two graphs on a common vertex set. Our aim is to extend a
result of Bollob\'as, Riordan, Slivken, and Smith concerning this process to
hypergraphs for a variety of possible definitions of connectedness. In
particular, we determine the asymptotic order of the critical threshold
probability for percolation when both hypergraphs are chosen binomially at
random.

We investigate bootstrap percolation with infection threshold $r> 1$ on the
binomial $k$uniform random hypergraph $H_k(n,p)$ in the regime $n^{1}\ll
n^{k2}p \ll n^{1/r}$, when the initial set of infected vertices is chosen
uniformly at random from all sets of given size. We establish a threshold such
that if there are less vertices in the initial set of infected vertices, then
whp only a few additional vertices become infected, while if the initial set of
infected vertices exceeds the threshold then whp almost every vertex becomes
infected. In addition, for $k=2$, we show that the probability of failure
decreases exponentially.

We consider highorder connectivity in $k$uniform hypergraphs defined as
follows: Two $j$sets are $j$connected if there is a walk of edges between
them such that two consecutive edges intersect in at least $j$ vertices. We
describe the evolution of $j$connected components in the $k$uniform binomial
random hypergraph $\mathcal{H}^k(n,p)$. In particular, we determine the
asymptotic size of the giant component shortly after its emergence and
establish the threshold at which the $\mathcal{H}^k(n,p)$ becomes $j$connected
with high probability. We also obtain a hitting time result for the related
random hypergraph process $\{\mathcal{H}^k(n,M)\}_M$  the hypergraph becomes
$j$connected exactly at the moment when the last isolated $j$set disappears.
This generalises wellknown results for graphs and vertexconnectivity in
hypergraphs.

Diluted meanfield models are spin systems whose geometry of interactions is
induced by a sparse random graph or hypergraph. Such models play an eminent
role in the statistical mechanics of disordered systems as well as in
combinatorics and computer science. In a pathbreaking paper based on the
nonrigorous `cavity method', physicists predicted not only the existence of a
replica symmetry breaking phase transition in such models but also sketched a
detailed picture of the evolution of the Gibbs measure within the replica
symmetric phase and its impact on important problems in combinatorics, computer
science and physics [Krzakala et al.: PNAS 2007]. In this paper we rigorise
this picture completely for a broad class of models, encompassing the Potts
antiferromagnet on the random graph, the $k$XORSAT model and the diluted
$k$spin model for even $k$. We also prove a conjecture about the detection
problem in the stochastic block model that has received considerable attention
[Decelle et al.: Phys. Rev. E 2011].

A bootstrap percolation process on a graph with infection threshold $r\ge 1$
is a dissemination process that evolves in time steps. The process begins with
a subset of infected vertices and in each subsequent step every uninfected
vertex that has at least $r$ infected neighbours becomes infected and remains
so forever.
Critical phenomena in bootstrap percolation processes were originally
observed by Aizenman and Lebowitz in the late 1980s as finitevolume phase
transitions in $\mathbb{Z}^d$ that are caused by the accumulation of small
local islands of infected vertices. They were also observed in the case of
dense (homogeneous) random graphs by Janson, \L uczak, Turova and Valier
(2012). In this paper, we consider the class of inhomogeneous random graphs
known as the ChungLu model: each vertex is equipped with a positive weight and
each pair of vertices appears as an edge with probability proportional to the
product of the weights. In particular, we focus on the sparse regime, where the
number of edges is proportional to the number of vertices.
The main results of this paper determine those weight sequences for which a
critical phenomenon occurs: there is a critical density of vertices that are
infected at the beginning of the process, above which a small (sublinear) set
of infected vertices creates an avalanche of infections that in turn leads to
an outbreak. We show that this occurs essentially only when the tail of the
weight distribution dominates a power law with exponent 3 and we determine the
critical density in this case.

We consider bootstrap percolation on the binomial random graph $G(n,p)$ with
infection threshold $r\in \mathbb{N}$, an infection process which starts from a
set of initially infected vertices and in each step every vertex with at least
$r$ infected neighbours becomes infected. We improve the results of Janson, \L
uczak, Turova, and Valier (2012) by strengthening the probability bounds on the
number of infected vertices at the end of the process, using simple arguments
based on martingales and giant components.

Bootstrap percolation on a graph with infection threshold $r\in \mathbb{N}$
is an infection process, which starts from a set of initially infected vertices
and in each step every vertex with at least $r$ infected neighbours becomes
infected. We consider bootstrap percolation on the binomial random graph
$G(n,p)$, which was investigated among others by Janson, \L uczak, Turova and
Valier (2012). We improve their results by strengthening the probability bounds
for the number of infected vertices at the end of the process.

Let $\mathbb{S}_g$ be the orientable surface of genus $g$. We show that the
number of vertexlabelled cubic multigraphs embeddable on $\mathbb{S}_g$ with
$2n$ vertices is asymptotically $c_g n^{5(g1)/21}\gamma^{2n}(2n)!$, where
$\gamma$ is an algebraic constant and $c_g$ is a constant depending only on the
genus $g$. We also derive an analogous result for simple cubic graphs and
weighted cubic multigraphs. Additionally we prove that a typical cubic
multigraph embeddable on $\mathbb{S}_g$, $g\ge 1$, has exactly one nonplanar
component.

We consider simplicial complexes that are generated from the binomial random
3uniform hypergraph by taking the downwardclosure. We determine when this
simplicial complex is homologically connected, meaning that its zeroth and
first homology groups with coefficients in $\mathbb{F}_2$ vanish. Although this
is not intrinsically a monotone property, we show that it nevertheless has a
single sharp threshold, and indeed prove a hitting time result relating the
connectedness to the disappearance of the last minimal obstruction.

In the classical Erd\"osR\'enyi random graph G(n,p) there are n vertices and
each of the possible edges is independently present with probability p. The
random graph G(n,p) is homogeneous in the sense that all vertices have the same
characteristics. On the other hand, numerous realworld networks are
inhomogeneous in this respect. Such an inhomogeneity of vertices may influence
the connection probability between pairs of vertices.
The purpose of this paper is to propose a new inhomogeneous random graph
model which is obtained in a constructive way from the Erd\"osR\'enyi random
graph G(n,p). Given a configuration of n vertices arranged in N subsets of
vertices (we call each subset a supervertex), we define a random graph with N
supervertices by letting two supervertices be connected if and only if there
is at least one edge between them in G(n,p). Our main result concerns the
threshold for connectedness. We also analyze the phase transition for the
emergence of the giant component and the degree distribution.
Even though our model begins with G(n,p), it assumes the existence of some
community structure encoded in the configuration. Furthermore, under certain
conditions it exhibits a power law degree distribution. Both properties are
important for real applications.

We give a full characterisation of the symmetries of unlabelled
triangulations and derive a constructive decomposition of unlabelled
triangulations depending on their symmetries. As an application of these
results we can deduce a complete enumerative description of unlabelled cubic
planar graphs.

We determine the asymptotic size of the largest component in the $2$type
binomial random graph $G(\mathbf{n},P)$ near criticality using a refined
branching process approach. In $G(\mathbf{n},P)$ every vertex has one of two
types, the vector $\mathbf{n}$ describes the number of vertices of each type,
and any edge $\{u,v\}$ is present independently with a probability that is
given by an entry of the probability matrix $P$ according to the types of $u$
and $v.$ We prove that in the weakly supercritical regime, i.e. if the distance
to the critical point of the phase transition is given by an
$\varepsilon=\varepsilon(\mathbf{n})\to0,$ with probability $1o(1),$ the
largest component in $G(\mathbf{n},P)$ contains asymptotically $2\varepsilon
\\mathbf{n}\_1$ vertices and all other components are of size $o(\varepsilon
\\mathbf{n}\_1).$

In the planted bisection model a random graph $G(n,p_+,p_ )$ with $n$
vertices is created by partitioning the vertices randomly into two classes of
equal size (up to $\pm1$). Any two vertices that belong to the same class are
linked by an edge with probability $p_+$ and any two that belong to different
classes with probability $p_ <p_+$ independently. The planted bisection model
has been used extensively to benchmark graph partitioning algorithms. If
$p_{\pm} =2d_{\pm} /n$ for numbers $0\leq d_ <d_+ $ that remain fixed as
$n\to\infty$, then w.h.p. the ``planted'' bisection (the one used to construct
the graph) will not be a minimum bisection. In this paper we derive an
asymptotic formula for the minimum bisection width under the assumption that
$d_+ d_ >c\sqrt{d_+ \ln d_+ }$ for a certain constant $c>0$.

The $k$core, defined as the largest subgraph of minimum degree $k$, of the
random graph $G(n,p)$ has been studied extensively. In a landmark paper Pittel,
Wormald and Spencer [JCTB 67 (1996) 111151] determined the threshold $d_k$
for the appearance of an extensive $k$core. Here we derive a multitype
GaltonWatson branching process that describes precisely how the $k$core is
embedded into the random graph for any $k\geq3$ and any fixed average degree
$d=np>d_k$. This generalises prior results on, e.g., the internal structure of
the $k$core.

We consider the following definition of connectivity in $k$uniform
hypergraphs: Two $j$sets are $j$connected if there is a walk of edges between
them such that two consecutive edges intersect in at least $j$ vertices. We
determine the threshold at which the random $k$uniform hypergraph with edge
probability $p$ becomes $j$connected with high probability. We also deduce a
hitting time result for the random hypergraph process  the hypergraph becomes
$j$connected at exactly the moment when the last isolated $j$set disappears.
This generalises wellknown results for graphs.

The stochastic Kronecker graph model introduced by Leskovec et al. is a
random graph with vertex set $\mathbb Z_2^n$, where two vertices $u$ and $v$
are connected with probability
$\alpha^{{u}\cdot{v}}\gamma^{(1{u})\cdot(1{v})}\beta^{n{u}\cdot{v}(1{u})\cdot(1{v})}$
independently of the presence or absence of any other edge, for fixed
parameters $0<\alpha,\beta,\gamma<1$. They have shown empirically that the
degree sequence resembles a power law degree distribution. In this paper we
show that the stochastic Kronecker graph a.a.s. does not feature a power law
degree distribution for any parameters $0<\alpha,\beta,\gamma<1$. In addition,
we analyze the number of subgraphs present in the stochastic Kronecker graph
and study the typical neighborhood of any given vertex.

The phase transition in the size of the giant component in random graphs is
one of the most wellstudied phenomena in random graph theory. For hypergraphs,
there are many possible generalisations of the notion of a component, and for
all but the simplest example, the phase transition phenomenon was first proved
by Cooley, Kang and Person. In this paper we build on this and determine the
asymptotic size of the unique giant component.

In this paper we consider $j$tupleconnected components in random
$k$uniform hypergraphs (the $j$tupleconnectedness relation can be defined by
letting two $j$sets be connected if they lie in a common edge and consider the
transitive closure; the case $j=1$ corresponds to the common notion of
vertexconnectedness). We determine that the existence of a $j$tupleconnected
component containing $\Theta (n^j)$ $j$sets in random $k$uniform hypergraphs
undergoes a phase transition and show that the threshold occurs at edge
probability $\tfrac{(kj)!}{\binom{k}{j}1}n^{jk}$. Our proof extends the
recent short proof for the graph case by Krivelevich and Sudakov which makes
use of a depthfirst search to reveal the edges of a random graph.
Our main original contribution is a "bounded degree lemma" which controls the
structure of the component grown in the search process.

Let $H_d(n,p)$ signify a random $d$uniform hypergraph with $n$ vertices in
which each of the ${n}\choose{d}$ possible edges is present with probability
$p=p(n)$ independently, and let $H_d(n,m)$ denote a uniformly distributed with
$n$ vertices and $m$ edges. We derive local limit theorems for the joint
distribution of the number of vertices and the number of edges in the largest
component of $H_d(n,p)$ and $H_d(n,m)$ for the regime ${{n1}\choose{d1}}
p,dm/n >(d1)^{1}+\epsilon$. As an application, we obtain an asymptotic
formula for the probability that $H_d(n,p)$ or $H_d(n,m)$ is connected. In
addition, we infer a local limit theorem for the conditional distribution of
the number of edges in $H_d(n,p)$ given connectivity. While most prior work on
this subject relies on techniques from enumerative combinatorics, we present a
new, purely probabilistic approach.