On the Termination of Some Biclique Operators on Multipartite Graphs 111This
work was partially supported by the PICS program of CNRS (France), by the
project “Models on graphs: enumerative combinatorics and algebraic structures”
of the Vietnam National Foundation for Science and Technology Development
(NAFOSTED) and by the Vietnam Institute for Advanced Study in Mathematics
(VIASM). This article is a complete and improved version of the extended
abstract that appeared in [19].

Christophe Crespelle 222Corresponding author<EMAIL_ADDRESS>Matthieu Latapy Thi Ha Duong Phan

Abstract.

We define a new graph operator, called the _weak-factor graph_ , which comes
from the context of complex network modelling. The weak-factor operator is
close to the well-known clique-graph operator but it rather operates in terms
of bicliques in a multipartite graph. We address the problem of the
termination of the series of graphs obtained by iteratively applying the weak-
factor operator starting from a given input graph. As for the clique-graph
operator, it turns out that some graphs give rise to series that do not
terminate. Therefore, we design a slight variation of the weak-factor
operator, called _clean-factor_ , and prove that its associated series
terminates for all input graphs. In addition, we show that the multipartite
graph on which the series terminates has a very nice combinatorial structure:
we exhibit a bijection between its vertices and the chains of the inclusion
order on the intersections of the maximal cliques of the input graph.

Keywords. Clean-factor Graph, Multipartite Graphs, Graph Series, Complex
Network Modelling

##  1 Introduction

The _clique-graph_ operator [24] is a well-known graph operator which, given a
graph $G$, consists of building the graph $G^{\prime}$ whose vertices are
maximal cliques of $G$ and such that there is an edge between two distinct
vertices of $G^{\prime}$ iff the corresponding cliques of $G$ share at least
one common vertex. The clique-graph series, obtained by iteratively applying
the clique-graph operator starting from $G$, has been widely studied (see e.g.
[23, 6]). This series is said to be convergent (in the sense of [6]) if one of
the graphs of the series is the graph with one single vertex333Note that [23]
uses a different definition of convergence which includes the one of [6] as a
particular case, and also includes periodic behaviours. The notion of
termination we use throughout the article is somehow equivalent to the one of
[6].. Then, all the graphs obtained in the following iterations are the same
(i.e. reduced to a single vertex).

Here we consider a new operator, called _weak-factor graph_ , which comes from
the context of complex network modelling and which operates in terms of
bicliques in multipartite graphs rather than cliques in graphs. One of the
interest of this operator is that it keeps an explicit and complete track of
the original graph at all step of the series: given an arbitrary graph of the
series it generates, one can univocally retrieve the original graph which gave
rise to the series. Given a $k$-partite graph $G=(V_{0},\ldots,V_{k-1},E)$
(see Section 1.2 for a definition), where $k\geq 2$, the _weak-factor graph_
$G^{\prime}$ of $G$ is defined as follows (see Definition 5 for a more formal
definition): $G^{\prime}$ is the graph $G$ augmented with a new level $V_{k}$
of vertices, each of which corresponds to one _non-simple_ maximal biclique of
the bipartite graph which is formed by the edges between the upper level of
$G$, i.e. $V_{k-1}$, and the rest of the vertices of $G$, i.e. $\bigcup_{0\leq
i\leq k-2}V_{i}$. Note that we do not add a new vertex at level $V_{k}$ for
all maximal bicliques but only for the _non-simple_ ones, i.e. those maximal
bicliques that have at least two vertices in $V_{k-1}$ and two vertices in
$\bigcup_{0\leq i\leq k-2}V_{i}$. For each new vertex $x$ at level $V_{k}$
corresponding to a non-simple maximal biclique $B$, we define its
neighbourhood in $G^{\prime}$ as being the vertices of $B$. The weak-factor
series of a graph $G$ is defined as the series obtained by iteratively
applying the weak-factor operator starting from the vertex-clique-incidence
bipartite graph of $G$ (see Figure 1), where the vertices of $G$ are at level
$V_{0}$ and the maximal cliques of $G$ are at level $V_{1}$. This series is
said to terminate iff, at some point, no new vertices are created. Then, the
series is finite and the following graphs are undefined. For example, the
series depicted on Figure 1 terminates since no new vertices are created when
applying the weak-factor operator on graph $G_{3}$ of the series.

As we will show in Section 2, the weak-factor series does not always
terminate. Then, the interest of the multipartite structure of the weak-factor
graph is that it will allow us to restrict the definition of the non-simple
bicliques we use in the weak-factor operator, taking into account the
different levels of the multipartite graphs. In this way, we will be able to
devise a refined version of the weak-factor graph, which we call the _clean-
factor graph_ , whose associated series terminates for all graphs.

$G_{0}=G$$G_{1}=B(G)$$G_{2}$$G_{3}$

Figure 1: Example of the weak-factor series of some graph $G$. From left to
right: the original graph $G=G_{0}$, its vertex-clique-incidence bipartite
graph $B(G)=G_{1}$, the tripartite graph $G_{2}$ of the series, and the
quadripartite graph $G_{3}$ on which the series terminates. The dashed edges
are those belonging to some non-simple maximal biclique used in the
factorisation steps. Note that even if those edges were removed, the
multipartite graph obtained at termination of the series would still
constitute an unambiguous encoding of the original graph, as these edges are
encoded by the presence of some vertices in the levels above them.

#### Our contribution

In this paper, we study a new graph operator called the weak-factor operator
which naturally arises in complex network modelling (see Section 1.1). We show
that there are graphs for which the weak-factor series, obtained by
iteratively applying the weak-factor operator, does not terminate. Therefore,
our main contribution is to define a refinement of the operator, called the
_clean-factor graph_ , whose series terminates for all graphs, thereby
defining an object suitable for modelling purposes. The difference between our
approach and the one followed by previous works is that we do not try to
determine on which graphs the weak-factor series terminates, but we rather
look for minimal constraints to impose to the operator in order to obtain
termination for all graphs. The solution we present here obtains termination
by imposing constraints to only a bounded number of levels (namely 3) of the
multipartite graph on which the operator is applied.

In addition to our termination result, we show that the multipartite graph on
which the clean-factor series terminates has a remarkable combinatorial
structure. Namely, its vertices are in bijection with the chains of the
inclusion order on the non-simple intersections of maximal cliques of the
graph (Theorem 1), denoted ${\cal{L}}$ in the rest of the paper. We believe
that this link between the termination of the series and the structure of the
cliques of the original graph is worth in itself and may be used to study
termination of other similarly defined graph operators.
Finally, we give an upper bound on the size and computation time of the graph
on which the iterated clean-factor series of $G$ terminates, under reasonable
hypotheses on the degree distributions of the vertex-clique-incidence
bipartite graph of $G$ (which hold for most real-world complex networks),
therefore showing that this multipartite graph can be used in practice for
complex network modelling.

Let us mention that this work is an improved and complete version of the
extended abstract that appeared in [19]. In [19], the notion of clean-factor
is slightly different from the one we use here. As a consequence, we could not
prove that imposing constraints only to a bounded number of levels is enough
to guarantee the termination of the series, and we did not have a real
bijection between the multipartite graph obtained at termination and the
vertices of ${\cal{L}}$.

#### Related works

The weak-factor operator we study here operates on multipartite graphs and is
defined using the bicliques between the upper level and the rest of the
multipartite graph. For graphs, closely related operators have been defined
using the cliques or the bicliques of the graph, and many works addressed the
question of convergence of the series obtained by iteratively applying these
operators to an input graph. There exists several definitions of convergence
in the literature. The notion of termination we use here for the multipartite
graph series is somehow equivalent to the convergence notion used in [6] in
the context of graph series, and is a particular case of convergence of the
definition used in [23].

For the well-known clique graph operator (see [24] for a survey) the question
of convergence has received a lot of attention [23, 6]. Most of the efforts
focussed on obtaining convergence results, or divergence results, for some
particular graphs or graph classes [17, 16, 18, 20]. Similar questions have
been addressed recently for the biclique graph operator [12, 13], which also
operates on graphs444Note that the bicliques we use in the definition of the
weak-factor operator are bicliques in a bipartite graph and not in a general
graph as in the definition of the biclique graph operator. but using bicliques
instead of cliques. It is worth noticing that the clique graph and the
biclique graph are defined as intersection graphs while this is not the case
of the operators we study in this paper. Let us mention, that another closely
related graph operator called edge-clique-graph operator has been studied (see
e.g. [8, 7]) but, to the best of our knowledge, the question of the
convergence of its iterated series has not been investigated.

It must be clear that none of these three operators, clique graphs, biclique
graphs and edge-clique graphs, which are defined on graphs, is equivalent to
one of the multipartite-graph operators we consider here. And the convergence
or divergence results obtained previously for these graph operators do not
imply the termination and non-termination results we present here.

Moreover, it is worth noticing that the question we address in this paper is
orthogonal, and complementary, to the one addressed in all the previously
cited works. Indeed, we do not intend to characterise the graphs for which the
iteration of the weak-factor operator terminates or does not terminate.
Instead, we aim at determining minimal constraints that can be imposed to this
operator in order to obtain termination for all graphs.

Finally, we note that recently [10] showed the interest of clique graphs to
study communities in complex networks. However, their approach and results are
not equivalent to ours. In particular, they do not consider the series
obtained by iterating the operator, which is our main concern here in the case
of the weak-factor operator.

#### Outline of the paper

In Section 1.1, we detail further the context where the practical motivation
of our work comes from. Then, Section 1.2 gives a few notations and basic
definitions, useful in the whole paper, including the definition of a
fundamental notion, the factorisation, which plays a key role in the
following. In Section 2, we formally define the weak-factor operator and a
natural variation of this operator, called the factor operator, both of which
giving rise to some infinite series. In Section 3 we propose a deeper
refinement of the operator, called the clean-factor operator, for which we
prove termination for all graphs and give a structural characterisation of the
multipartite graph obtained at termination. Finally, in Section 4, we address
the question of efficiently computing and storing the representation provided
by the clean-factor series.

###  1.1 Motivation

It is worth to mention that we did not come to the study of the termination of
the weak-factor series only for theoretic motivations: this question is of key
interest in complex network modelling. Complex networks are those graphs
encountered in practice in various domains such as computer science, biology,
social sciences and others. In the last decade, they were shown to share some
nontrivial common properties [30, 1], independently from the context they come
from. A lot of efforts have been done to design models able to capture these
properties while staying general enough. One of the difficulty of the domain
is to encompass in a same model the two major properties of these networks,
namely their heterogeneous degree distribution and their high local density
(clustering coefficient, see [4] for a formal definition).

Among the most promising approaches, [14, 15] propose to model complex
networks based on the properties of their vertex-clique-incidence bipartite
graph. Their idea is to use prescribed-degree-graph generation, which is a
powerful and well understood technique since the works of [5, 21], for the
vertex-clique-incidence bipartite graph instead of the graph itself. In other
words, they advocate for the generation of complex networks by their cliques
rather than by their edges. They show that, in this way, one obtains graphs
having a high local density (thanks to the clique structure) and a
heterogeneous degree distribution that is controlled by the degrees of the
vertices in the vertex-clique-incidence bipartite graph. However, the
bipartite model suffers from a severe limitation: when generating the edges of
the bipartite graph at random, the obtained neighbourhoods of the upper
vertices intersect only on one (or zero) vertex with a very high probability
(see [14, 15]). This is not the case in real world networks, where most of the
maximal cliques have non-simple overlaps with some others (i.e. overlaps of
cardinality at least two). Thus, even though it gives the desired properties
concerning degree distribution and local density, the bipartite model results
in graphs having a caricaturistic structure.

The weak-factor graph (see Section 2) was introduced in [19] in order to
correct this drawback. The idea is to define an object that encodes the non-
simple intersections of maximal cliques of a graph $G$ by the neighbourhoods
of vertices in some other suitably defined graph, so that such objects can be
randomly generated using the prescribed-degree generation technique of [5,
21]. In order to define such an encoding of a graph $G$, we can proceed as
follows. We start from the vertex-clique-incidence bipartite graph
$B(G)=(V_{0},V_{1},E)$ of $G$ and we create a new level $V_{2}$ where each
vertex $x$ corresponds to a non-simple maximal biclique $B$ of $B(G)$. Then,
we can delete the edges of $B$ as they are now encoded by the presence of $x$.
Doing so simultaneously for all non-simple maximal bicliques of $B(G)$ gives a
tripartite graph in which the neighbourhoods on $V_{0}$ of vertices at level
$V_{1}$ have no non-simple intersections anymore. Then, we can iteratively
repeat the operation by considering, at each stage of the process, the maximal
bicliques between the vertices on the uppermost level and the rest of the
vertices of the multipartite graph, until the process hopefully terminates. In
this case, we obtain a multipartite graph555Note that this multipartite graph
is an encoding of the original graph, as the factorising operation is
reversible. without any non-simple intersection of neighbourhoods. We can
therefore generate similar structures at random using the prescribed-degree
generation method without bumping into the problem raised by [14, 15]. Of
course, in order to obtain a multipartite graph that has no non-simple
neighbourhood intersections, it is mandatory that the iterative factorising
process terminates. This is the reason why we came to study the termination of
the weak-factor series.

Note that, opposite to the process described above, in the definition of the
weak-factor operator we do not delete edges of the bicliques involved in one
factorisation step. This has no impact on the set of nodes created in the rest
of the process, as those edges are not involved in further factorisation
steps. On the other hand, keeping those edges helps to describe the structure
of the graphs of the weak-factor series (Definition 2 below) and this is the
reason why we keep them in the rest of the paper.

###  1.2 Notations and preliminary definitions

All graphs considered here are finite, undirected and simple (no loops and no
multiple edges). A graph $G$ having vertex set $V$ and edge set $E$ will be
denoted by $G=(V,E)$. We also denote by $V(G)$ the vertex set of $G$. The edge
between vertices $x$ and $y$ will be indifferently denoted by $xy$ or $yx$.
${\cal{K}}(G)$ denotes the set of maximal cliques of a graph $G$, and $N(x)$
the neighbourhood of a vertex $x$ in $G$.

An ordered $k$-partition ${\cal{P}}$ of a set $V$ is a partition of $V$ into
$k$ parts (non empty and pairwise disjoint, from the classical definition of
partition) which are numbered from $0$ to $k-1$. It is denoted as a $k$-tuple:
${\cal{P}}=(V_{0},\ldots,V_{k-1})$. In this paper, a $k$-partite graph is
always given together with a partition of its vertices as in the following
definition.

######  Definition 1 ($k$-partite graph)

A _$k$ -partite graph_ is a couple $(G,{\cal{P}})$ where $G=(V,E)$ is a graph
and ${\cal{P}}=(V_{0},\ldots,V_{k-1})$ is an ordered $k$-partition of its
vertex set $V$ such that all edges of $G$ are between vertices in different
parts of ${\cal{P}}$. It is denoted by $G=(V_{0},\ldots,V_{k-1},E)$.

A _multipartite_ graph is a $k$-partite graph with $k\geq 2$. For a
$k$-partite graph $G=(V_{0},\ldots,V_{k-1},E)$, the vertices of $V_{i}$, for
any $i$, are called the $i$-th level of $G$, and the vertices of $V_{k-1}$ are
called its _upper vertices_. We denote by $N_{i}(x)$, where $0\leq i\leq k-1$,
the set of neighbours of $x$ at level $i$: $N_{i}(x)=N(x)\cap V_{i}$. A
_biclique_ of a graph is a set of vertices of the graph inducing a complete
bipartite graph. We denote by $B(G)$ the vertex-clique-incidence bipartite
graph of $G=(V,E)$: $B(G)=(V,{\cal{K}}(G),E^{\prime})$ where
$E^{\prime}=\\{vc\ |\ c\in{\cal{K}}(G),\ v\in c\\}$. A _non-simple biclique_
of a bipartite graph is a biclique having at least two vertices in the upper
level and at least two vertices in the bottom level. Two sets have a _non-
simple intersection_ if they share at least two elements. In the whole paper,
we denote ${\cal{L}}$ the inclusion order of the non-simple intersections of
maximal cliques of a graph $G$ (there will be no confusion on the graph $G$
referred to when we use this notation).

For two non-negative integers $a,b\in\mathbb{N}$, we use the notation
$\llbracket a,b\rrbracket$ for the set $\\{p\in\mathbb{N}\ |\ a\leq p\leq
b\\}$, with the convention $\llbracket a,b\rrbracket=\varnothing$ if $a>b$.

In the sequel, an operation will play a key role, we name it _factorisation_
and define it generically as follows.

######  Definition 2 (factorisation with respect to $V^{\prime}_{k}(G)$)

Given a $k$-partite graph $G=(V_{0},\ldots,V_{k-1},E)$ with $k\geq 2$ and a
set $V^{\prime}_{k}(G)$ of subsets of $V(G)$, we define the factorisation of
$G$ with respect to $V^{\prime}_{k}(G)$ as the $(k+1)$-partite graph
$G^{\prime}=(V_{0},\ldots,V_{k},E\cup E_{+})$ where:

  * •

$V_{k}$ is the set of maximal (with respect to inclusion) elements of
$V^{\prime}_{k}(G)$,

  * •

$E_{+}=\\{Xy\ |\ X\in V_{k}\text{ and }y\in X\\}$.

When $V_{k}\not=\emptyset$, the factorisation is said to be _effective_.

Provided that the set $V^{\prime}_{k}(G)$ is properly defined for all
multipartite graphs $G$, such a factorisation operation defines a multipartite
graph operator, the iteration of which gives rise to a series of multipartite
graphs as defined below.

######  Definition 3 (series associated to a factorisation operation)

Given a factorisation operation that associates any $k$-partite graph
$G=(V_{0},\ldots,V_{k-1},E)$ with $k\geq 2$ to a (unique) $k+1$-partite graph
$G^{\prime}$, we define the series of multipartite graphs $(G_{i})_{i\geq 1}$,
associated to this factorisation operation and generated by a graph
$G_{0}=(V_{0},E_{0})$, by: $G_{1}=B(G_{0})$ is the vertex-clique-incidence
bipartite graph of $G_{0}$ (in which the cliques are on the upper level of
$B(G_{0})$) and, for all $i\geq 1$, $G_{i+1}=G^{\prime}_{i}$ when the
factorisation of $G_{i}$ is effective, and $G_{i+1}$ is undefined otherwise.

######  Definition 4 (termination of the series)

We say that the series $(G_{i})_{1\leq i\leq n}$ associated to some
factorisation operation _terminates_ iff for some $i\geq 1$ the factorisation
is not effective, then all subsequent graphs of the series are undefined and
the series reduces to a finite sequence.

In the rest of the paper, we will refine the notion of factorisation by using
different sets $V^{\prime}_{k}(G)$ on which is based the factorisation
operation. And we will study termination of the graph series resulting from
each of these refinements. As, in the following, the graph $G$ referred to is
always clear from the context, we denote $V^{\prime}_{k}$ instead of
$V^{\prime}_{k}(G)$. But all the sets $V^{\prime}_{k}$ we define still depend
on the graph considered.

##  2 Weak-factor series and factor series

###  2.1 Weak-factor series

Thanks to the generic notion of factorisation, we will now formally define the
weak-factor operation we introduced above.

######  Definition 5 ($V^{+}_{k}$ and weak-factor graph)

Given a $k$-partite graph $G=(V_{0},\ldots,V_{k-1},E)$ with $k\geq 2$, we
define the set $V^{+}_{k}$ as:

$V^{+}_{k}=\\{\\{x_{1},\ldots,x_{l}\\}\cup\bigcap_{1\leq i\leq l}N(x_{i})\ |\
l\geq 2,\ \forall i\in\llbracket 1,l\rrbracket,x_{i}\in V_{k-1}\text{ and
}|\bigcap_{1\leq i\leq l}N(x_{i})|\geq 2\\}.$

The _weak-factor graph_ $G^{+}$ of $G$ is the factorisation of $G$ with
respect to $V^{+}_{k}$.

Figure 2: An example graph for which the weak-factor series is infinite. From
left to right: the input graph $G$, its vertex-clique-incidence bipartite
graph $B(G)$, and the tripartite graph $B(G)^{+}$ of its weak-factor series
(note that for sake of readability of the drawing, the edges between levels
$V_{1}$ and $V_{0}$ have been removed in $B(G)^{+}$). The shaded edges are the
ones involving vertex $e$, which plays a special role: all the vertices of the
upper level of the multipartite graph are linked to $e$. The structure of
edges between vertices of $V_{2}$ and vertices of $V_{1}\cup\\{e\\}$ in
$B(G)^{+}$ is identical to the one between levels $V_{1}$ and $V_{0}$ in
$B(G)$, revealing that the series will not terminate.

Figure 1 gives an illustration for this definition. In this case, the weak-
factor series is finite. However, it is not difficult to find examples of
graphs which lead to infinite weak-factor series. Figure 2 provides such an
example for which the structure of the upper level is infinitely reproduced on
the further levels. Intuitively, this is due to the fact that a vertex may be
the base for an infinite number of factorisation steps (vertex $e$ in the
example of Figure 2). The aim of the next sections is to avoid this case by
using a more restrictive definition of factorisation.

###  2.2 Factor series

In this section, we examine a first restriction of the operator, called
_factor graph_ , that forbids the repeated use of the same vertex to produce
infinitely many factorisations, which is the phenomenon responsible for the
non termination of the series for the example of Figure 2.

######  Definition 6 ($V^{\circ}_{k}$ and factor graph)

Given a $k$-partite graph $G=(V_{0},\ldots,V_{k-1},E)$ with $k\geq 2$, we
define the set $V^{\circ}_{k}$ as:

$V^{\circ}_{k}\ =\ \\{X\in V^{+}_{k}\text{ such that }|\bigcap_{y\in X\cap
V_{k-1}}N_{k-2}(y)|\geq 2\\}.$

The _factor graph_ $G^{\circ}$ of $G$ is the factorisation of $G$ with respect
to $V^{\circ}_{k}$.

This new definition results from the restriction of the weak-factor definition
by considering only sets $X\in V^{+}_{k}$ such that the vertices of $X\cap
V_{k-1}$ have at least two common neighbours at level $k-2$. The reason is
that, in this way, a vertex cannot contribute to more than two factorising
steps: once when it is on the upper level of the multipartite graph, once when
it is on the level just below. Indeed, even if the vertices of levels lower
than the two upper levels (i.e. $V_{k}$ and $V_{k-1}$) may be involved in a
factorisation step, they are not responsible for the creation of a new vertex.
Such a creation depends only on the edges between the two upper levels of the
multipartite graph.

Finding examples of input graphs that generate infinite factor series is not
straightforward. In particular, one natural candidate that one could have in
mind, namely the graph whose vertex-clique-incidence bipartite graph is the
_anti-matching_ on $2n$ vertices, which generates an infinite series for the
clique-graph operator [22], actually gives rise to a finite series for the
factor operator. The anti-matching is the bipartite complement of a perfect
matching between the $n$ upper vertices and the $n$ bottom vertices (also
known as the _octahedron_ in clique-graph theory and as the _crown_ in poset
theory). The anti-matching is known for being the bipartite graph on $2n$
vertices that has the maximum number of bicliques. Regarding the factor
series, it implies that there is a combinatorial explosion of the number of
vertices on the first next levels. Despite of this, one can check that the
series of the anti-matching on $2n$ vertices terminates.

Nevertheless, [9] recently provided an example of a graph that gives rise to
an infinite factor series. This is the reason why in the next section, we
constraint further the factor operation: we do not only require that the
neighbourhoods of vertices at level $V_{k-1}$ involved in the creation of a
new vertex at level $V_{k}$ share at least two vertices on level $V_{k-2}$ but
we also require that those vertices have the same neighbourhood at level
$V_{k-3}$ (see Definition 7 of the clean-factor graph). This supplementary
condition is not only a technical condition used to guarantee termination: we
will show that the graph on which terminates the clean-factor series is a
fundamental combinatorial object.

##  3 Clean-factor series

In the previous section, we studied two series of multipartite graphs based on
two different factorisation operations, both of them giving rise to some
infinite series. In this section, we introduce a more constrained refinement
of these two factorisation operations, which we call the _clean-factor_
operator, for which we prove that the associated series always terminates. One
interesting point of our solution is that the constraints introduced in order
to guarantee termination are light: they apply on only 3 levels of the
multipartite graph. In addition, the multipartite graph obtained at
termination has a very deep combinatorial meaning: its vertices are the chains
of the inclusion order ${\cal{L}}$ of the non-simple intersections of maximal
cliques of the input graph $G$.

We now give the formal definition of the clean-factor graph of a multipartite
graph: the general factorisation step is the case where $k\geq 5$, the
construction of levels $V_{2},V_{3}$ and $V_{4}$ are subject to particular
conditions. It should be clear that these particular conditions may be
simplified while preserving termination. But on the other hand, those exact
conditions are necessary in order to obtain the bijection with the chains of
order ${\cal{L}}$.

######  Definition 7 ($V^{*}_{k}$ and clean-factor graph)

Given a $k$-partite graph $G=(V_{0},\ldots,V_{k-1},E)$ with $k\geq 2$, we
define the set $V^{*}_{k}$ as:

  * •

If $k\geq 5$, $V^{*}_{k}\ =\ \\{X\in V^{+}_{k}\ |\ |\bigcap_{x\in X\cap
V_{k-1}}N_{k-2}(x)|\geq 2\text{ and }\forall x,y\in X\cap
V_{k-1},N_{k-3}(x)=N_{k-3}(y)\text{ and }|\bigcap_{x\in X\cap
V_{k-1}}N_{1}(x)|\geq 2\\}$.

  * •

If $k=4$, $V^{*}_{4}\ =\ \\{X\in V^{+}_{4}\ |\ |\bigcap_{x\in X\cap
V_{3}}N_{2}(x)|\geq 2\text{ and }|\bigcap_{x\in X\cap V_{3}}N_{1}(x)|\geq
2\text{ and }\forall x,y\in X\cap V_{3},N_{0}(x)=N_{0}(y)\\}$.

  * •

If $k=3$, $V^{*}_{3}=\ \\{X\in V^{+}_{3}\ |\ |\bigcap_{x\in X\cap
V_{2}}N_{1}(x)|\geq 2\text{ and }|\bigcap_{x\in X\cap V_{2}}N_{0}(x)|\geq
2\\}$.

  * •

If $k=2$, $V^{*}_{2}=V^{+}_{2}$.

The _clean-factor graph_ $G^{*}$ of $G$ is the factorisation of $G$ with
respect to $V^{*}_{k}$.

The rest of this section is devoted to proving the termination of the clean-
factor series $(G_{i})_{i\geq 1}$ generated by any graph $G$ (Theorem 2) and
the bijection between vertices of level $V_{i}$ of the series, with $i\geq 2$,
and the chains of length $i-2$ of ${\cal{L}}$ (Theorem 1). We start by proving
Theorem 1 since Theorem 2 will be obtained as a direct corollary from it.

Theorem 1 gives a characterisation of $V_{i},i\geq 2$ by associating to each
of its nodes a chain of length $i-2$ in order ${\cal{L}}$. Formally, we
associate to a node $x$ of $V_{i}$ a sequence $S(x)$ of subsets of $V(G)$
which are precisely the elements of ${\cal{L}}$ defining the chain associated
to $x$. Before formally defining $S(x)$ (Definition 10) and stating Theorem 1,
we need to establish some basic definitions, notations and properties of the
non-simple intersections of the maximal cliques of a graph.

###### Definition 8

We denote by ${\cal{O}}^{\prime}$ the set of intersections of maximal cliques
of $G$ (possibly only one clique or none), that is
${\cal{O}}^{\prime}=\\{O\subseteq V(G)\ |\ \exists
P_{c}\subseteq{\cal{K}}(G),O=\bigcap_{C\in P_{c}}C\\}$, using the convention
that $\bigcap_{C\in\varnothing}C=V(G)$. And we denote by ${\cal{O}}$ the
subset of ${\cal{O}}^{\prime}$ formed by the elements that contain at least
two vertices of $G$ and that are obtained as the intersection of at least two
distinct maximal cliques of $G$, that is ${\cal{O}}=\\{O\in{\cal{O}}^{\prime}\
|\ |O|\geq 2\text{ and }\exists k\geq 2,\exists
C_{1},\ldots,C_{k}\in{\cal{K}}(G),(\forall j,l\in\llbracket
1,k\rrbracket,j\neq l\Rightarrow C_{j}\neq C_{l})\text{ and }O=\bigcap_{1\leq
i\leq k}C_{i}\\}$.

###### Definition 9

For any subset $A\subseteq V(G)$ of vertices of $G$, we denote by $K(A)$ the
set of maximal cliques of $G$ containing $A$, that is
$K(A)=\\{C\in{\cal{K}}(G)\ |\ A\subseteq C\\}$. And we denote by ${\cal{C}}$
the family of subsets of ${\cal{K}}(G)$ defined by ${\cal{C}}=\\{K(O)\ |\
O\in{\cal{O}}^{\prime}\\}$.

Note that the set $A$ defining $K(A)$ is not unique: there may exist
$A^{\prime}\neq A$ such that $K(A^{\prime})=K(A)$. This is the reason why we
now need to state some basic properties of sets $K(A)$ that we will use in the
following.

###### Remark 1

For any subsets $A,B\subseteq V(G)$, if $A\subseteq B$ then $K(B)\subseteq
K(A)$. And for any subsets $A\subseteq V(G)$ and $O\in{\cal{O}}^{\prime}$, if
$K(O)\subseteq K(A)$ then $A\subseteq O$.

Proof: The first part of the remark is self-evident. For the second part, note
that, by definition of ${\cal{O}}^{\prime}$, $O=\bigcap_{C\in K(O)}C$. And on
the other hand, we have $A\subseteq\bigcap_{C\in K(A)}C\subseteq\bigcap_{C\in
K(O)}C=O$. $\blacksquare$

###### Remark 2

For any $A,B\subseteq V(G)$, $K(A)\cap K(B)=K(A\cup B)$. Conversely, if
$A_{1},\ldots,A_{n}\subseteq V(G)$, with $n\geq 2$, and if
$O\in{\cal{O}}^{\prime}$ and if $\bigcap_{1\leq i\leq n}K(A_{i})=K(O)$, then
$\bigcup_{1\leq i\leq n}A_{i}\subseteq O$.

Proof: Let $A,B\in V(G)$. The cliques in $K(A)\cap K(B)$ are exactly the
cliques that contain both $A$ and $B$, i.e. the cliques that contain $A\cup
B$. Therefore $K(A)\cap K(B)=K(A\cup B)$.

Let $A_{1},\ldots,A_{n}\subseteq V(G)$, with $n\geq 2$, and let
$O\in{\cal{O}}^{\prime}$ such that $\bigcap_{1\leq i\leq n}K(A_{i})=K(O)$.
From what precedes, $\bigcap_{1\leq i\leq n}K(A_{i})=K(\bigcup_{1\leq i\leq
n}A_{i})$. Consequently, we have $K(O)\subseteq K(\bigcup_{1\leq i\leq
n}A_{i})$. And since $O\in{\cal{O}}^{\prime}$, from Remark 1, we have
$\bigcup_{1\leq i\leq n}A_{i}\subseteq O$. $\blacksquare$

###### Lemma 1

${\cal{O}}^{\prime}$ and ${\cal{C}}$ are closed under intersection.

Proof: The fact that ${\cal{O}}^{\prime}$ is closed under intersection is
clear from the definition. Let us show that ${\cal{C}}$ is closed under
intersection. Let $k\geq 2$ and let $O_{1},\ldots,O_{k}\in{\cal{O}}^{\prime}$.
We prove that $\bigcap_{1\leq i\leq k}K(O_{i})\in{\cal{C}}$. For that purpose,
consider a set $O\in{\cal{O}}^{\prime}$ such that $O\supseteq\bigcup_{1\leq
i\leq k}O_{i}$ and which is minimal under inclusion. We will show that
$\bigcap_{1\leq i\leq k}K(O_{i})=K(O)$. Since $O\supseteq\bigcup_{1\leq i\leq
k}O_{i}$, we have $K(O)\subseteq K(\bigcup_{1\leq i\leq
k}O_{i})=\bigcap_{1\leq i\leq k}K(O_{i})$, from Remark 2. For the converse
inclusion, consider $C\in K(\bigcup_{1\leq i\leq k}O_{i})$. By definition,
$C\in{\cal{O}}^{\prime}$ and $\bigcup_{1\leq i\leq k}O_{i}\subseteq C$. Since
$\bigcup_{1\leq i\leq k}O_{i}\subseteq O$, we also have $\bigcup_{1\leq i\leq
k}O_{i}\subseteq O\cap C$. And since $O\cap C\in{\cal{O}}^{\prime}$ (as
${\cal{O}}^{\prime}$ is closed under intersection), the minimality of $O$
implies that $O\cap C=O$, that is $O\subseteq C$. Thus, $C\in K(O)$ and it
follows that $K(\bigcup_{1\leq i\leq k}O_{i})\subseteq K(O)$, which completes
the proof. $\blacksquare$

The following lemma is the first step toward the bijection theorem (Theorem
1). It establishes the bijection between vertices of $V_{2}$ and the chains of
length $0$ of ${\cal{L}}$. We will use it in the initialising step of the
recursion of the proof of Theorem 1.

###### Lemma 2

In the clean-factor series, $V_{0}=V(G),V_{1}={\cal{K}}(G)$ and
$V_{2}={\cal{O}}$ in the sense that the map $\phi$ defined by $x\mapsto
N_{0}(x)$ is a bijection from $V_{2}$ to ${\cal{O}}$. Moreover, $\forall x\in
V_{2},N_{1}(x)=K(N_{0}(x))$.

Proof: Let us start with the second part of the lemma. Let $x\in V_{2}$. By
definition of $V^{+}_{2}$, all the elements $y$ in $N_{1}(x)$ are such that
$N_{0}(x)\subseteq N_{0}(y)$. Then, $y\in K(N_{0}(x))$, by identifying $V_{1}$
and ${\cal{K}}(G)$. On the other hand, the maximality of $x$ in $V^{+}_{2}$
implies that all $y\in K(N_{0}(x))$ belong to $N_{1}(x)$. Thus,
$N_{1}(x)=K(N_{0}(x))$

Let us prove that the map $\phi$ is a bijection from $V_{2}$ to ${\cal{O}}$.
First, if $x\in V_{2}$ then by definition, $|N_{0}(x)|\geq 2$, $|N_{1}(x)|\geq
2$, and $N_{0}(x)=\bigcap_{y\in N_{1}(x)}N_{0}(y)$, hence $N_{0}(x)$ belongs
to ${\cal{O}}$, and the map $\phi$ is well defined.

Second, $\phi(x)=\phi(x^{\prime})$ means $N_{0}(x)=N_{0}(x^{\prime})$. But
$N_{1}(x)$ is the set of all maximal cliques containing $N_{0}(x)$, and
$N_{1}(x^{\prime})$ is the same. Then, if $\phi(x)=\phi(x^{\prime})$, we have
$x=x^{\prime}$: $\phi$ is injective.

We now prove that $\phi$ is surjective. Let $O$ be an element of ${\cal{O}}$,
we show that the element $x=K(O)\cup\bigcap_{y\in K(O)}N_{0}(y)$ is an element
of $V_{2}$ and $\phi(x)=O$. It is clear that $x\cap V_{0}=O$, so $|x\cap
V_{0}|\geq 2$. Since $O\in{\cal{O}}$, $|K(O)|\geq 2$, and we have $|x\cap
V_{1}|\geq 2$. Then $x\in V^{+}_{2}$. Moreover, by definition, $K(O)$ is
exactly the set of all maximal cliques containing $O$, then $x$ is maximal in
$V^{+}_{2}$. It follows that $x$ is an element of $V_{2}$, and $\phi(x)=O$.
$\blacksquare$

We are now ready to give the definition of the sequence $S(x)$ that we
associate to a vertex $x\in V_{i}$ with $i\geq 2$.

######  Definition 10 (Characterising sequence $S(x)$)

Let $G$ be a graph and let $(G_{i})_{i\geq 1}$ be its clean-factor series. The
_characterising sequence_ $S(x)=(O_{1}(x),\ldots,O_{k-1}(x))$ of a vertex
$x\in V_{k}$, with $k\geq 2$, is defined by:

  * •

$O_{1}(x)=N_{0}(x)$, and

  * •

for $k\geq 3$, $\forall j\in\llbracket 2,k-1\rrbracket,O_{j}(x)$ is the unique
element of ${\cal{O^{\prime}}}$ such that $K(O_{j}(x))=\bigcap_{y\in
N_{j}(x)}N_{1}(y)$.

Note that $O_{j}$ is properly defined. Indeed, from Lemma 2, $\forall y\in
V_{2},V_{1}(y)\in{\cal{C}}$. And since ${\cal{C}}$ is closed under
intersection, a simple recursion shows that for all $i\geq 3$ and for all
$y\in V_{i}$, $N_{1}(y)=\bigcap_{z\in V_{i-1}}N_{1}(z)\in{\cal{C}}$. Then, for
any $j\geq 2$, $\bigcap_{y\in N_{j}(x)}N_{1}(y)$ is in ${\cal{C}}$ and there
exists some $O_{j}$ in ${\cal{O^{\prime}}}$ satisfying the condition. The fact
that such an $O_{j}\in{\cal{O}}^{\prime}$ is unique comes from the fact that
for any set $O\in{\cal{O}}^{\prime}$, we have $O=\bigcap_{C\in K(O)}C$. Then,
if there exists some $O$ such that $K(O)=K(O_{j})$, necessarily $O=O_{j}$.
Consequently, $O_{j}$ is unique and properly defined.

We will often use the following remark in the proof of Theorem 1.

###### Remark 3

For any $x\in V_{k}$, with $k\geq 2$, $K(O_{k-1}(x))=N_{1}(x)$.

Proof: For $k=2$, the remark rewrites $K(O_{1}(x))=N_{1}(x)$. Since
$O_{1}(x)=N_{0}(x)$ and since, from Lemma 2, $K(N_{0}(x))=N_{1}(x)$, then the
result follows. For $k>2$, the remark simply follows from the fact that
$\bigcap_{y\in N_{k-1}(x)}N_{1}(y)=N_{1}(x)$. $\blacksquare$

graph $G$

max. cliques of $G$

order ${\cal{L}}$

Figure 3: Top left: a graph G. Top center: its maximal cliques. Top right: the
inclusion order ${\cal{L}}$ of the non-simple intersections of maximal cliques
of $G$. Bottom: the multipartite graph $M$ obtained at termination of the
clean-factor series of $G$. $M$ has $5$ levels. Level $V_{0}$ is for the
vertices of $G$ and level $V_{1}$ for the maximal cliques of $G$. The
bijection between the vertices of $M$ and the chains of order ${\cal{L}}$
appears in the rest of the levels: each vertex $x$ of $M$ in levels $V_{2}$ to
$V_{4}$ has been labelled with the corresponding chain of ${\cal{L}}$, i.e.
its characterising sequence $S(x)$ (see Definition 10). Level $V_{2}$ is for
the non-simple intersections of maximal cliques of $G$ (i.e. the chains of
${\cal{L}}$ of length $0$), level $V_{3}$ is for the chains of ${\cal{L}}$ of
length $1$, and level $V_{4}$ is for the chains of ${\cal{L}}$ of length $3$,
which is precisely the height of ${\cal{L}}$. For sake of clarity, only a few
links of $M$ have been drawn on the figure, namely all the links between two
consecutive levels higher than level $V_{2}$. The black bold lines are for the
link between a vertex $x$ at level $V_{i}$, for $i\geq 3$, and the unique
vertex of $V_{i-1}$ whose characterising sequence is a prefix of the sequence
of $x$ (of length $length(S(x))-1$, necessarily). In this way, we obtain a
clearer representation of the bijection with the chains of ${\cal{L}}$, as one
can clearly see the four prefix trees of the chains starting at a given
element of ${\cal{L}}$: these prefix trees are rooted at level $V_{2}$ and two
of them are reduced to one single node, labelled $(abcd)$ and $(abce)$.

We will now state the bijection theorem (Theorem 1) which is our main
combinatorial tool for proving the termination of the clean-factor series
(Theorem 2). Its proof is rather intricate, but it gives much more information
than the termination of the series. By associating a sequence of sets to each
vertex in levels greater than $V_{2}$ in the multipartite graph, we show that
each such vertex corresponds to a chain of the inclusion order ${\cal{L}}$ of
the non-simple intersections of maximal cliques of $G$.

######  Theorem 1 (Bijection theorem)

Let $G$ be a graph and $(G_{i})_{i\geq 2}$ its clean-factor series. For any
$k\geq 2$, the map $\phi$ defined by $x\mapsto S(x)$ is a bijection from
$V_{k}$ to $\\{(O_{1},\ldots,O_{k-1})\in{\cal{O}}^{k-1}\ |\
O_{1}\subsetneq\ldots\subsetneq O_{k-1}\\}$ (see Figure 3).

Proof:

The case $k=2$ directly follows from Lemma 2, then, in the following, we only
deal with the cases where $k\geq 3$. We prove Theorem 1 by recursion, using
the five recursion hypotheses below, namely $H_{tar},H_{inj},H_{sur},H_{N}$
and $H_{E}$. Actually, hypotheses $H_{tar},H_{inj}$ and $H_{sur}$ are the
targeted properties: they imply that map $\phi$ is a bijection. Hypotheses
$H_{N}$ and $H_{E}$ contain the fundamental structure of the multipartite
graph series. Hypothesis $H_{N}$ is essential, it gives a complete
characterisation of the neighbourhood of a vertex on the lower levels.
Hypothesis $H_{E}$ shows that the condition of equality of the neighbourhood
at level $k-3$ of the children of $x$ in Definition 7 actually induce a
control of the neighbourhoods of the children of $x$ on all the lower levels.

$H_{tar}(k)$

: If $x\in V_{k}$ then $O_{1}(x)\subsetneq\ldots\subsetneq O_{k-1}(x)$ and
$(O_{1}(x),\ldots,O_{k-1}(x))\in{\cal{O}}^{k-1}$,

$H_{inj}(k)$

: If $x,y\in V_{k}$ then $x\neq y$ implies $S(x)\neq S(y)$,

$H_{sur}(k)$

: For any sequence $(O_{1},\ldots,O_{k-1})\in{\cal{O}}^{k-1}$ with
$O_{1}\subsetneq\ldots\subsetneq O_{k-1}$, there exists $x\in V_{k}$ such that
$S(x)=(O_{1},\ldots,O_{k-1})$.

$H_{N}(k)$

: If $x\in V_{k}$, then for all $j$ such that $2\leq j<k$,
$N_{j}(x)=W_{j}(x)$; where $W_{j}(x)$ is the set $\\{y\in V_{j}\ |\
(O_{1}(y),\ldots,O_{j-2}(y))=(O_{1}(x),\ldots,O_{j-2}(x))\text{ and
}O_{j-1}(x)\subseteq O_{j-1}(y)\subseteq O_{j}(x)\\}$ (using the convention
$(O_{1}(.),\ldots,O_{j-2}(.))=()$ for $j=2$).

$H_{E}(k)$

, for $k\geq 4$: If $y_{1},y_{2}\in V_{k}$ such that
$N_{k-2}(y_{1})=N_{k-2}(y_{2})$ then $\forall p\in\llbracket
0,k-2\rrbracket\setminus\\{1\\},N_{p}(y_{1})=N_{p}(y_{2})$.

At each level $k$ of recursion, we start by showing $H_{N}(k)$, using
$H_{E}(k-1$), then we use it to prove $H_{arr}(k),H_{inj}(k),$ and
$H_{sur}(k)$, and we finish by proving $H_{E}(k)$.

Initialisation step. We will prove that $H_{N}(3)$, $H_{tar}(3)$,
$H_{inj}(3)$, and $H_{sur}(3)$ are true. We do not prove $H_{E}(3)$ since it
is undefined. It is worth to note that we do not need $H_{E}(3)$ in the proof
of $H_{N}(4)$: instead, we use Definition 7 that provide us the initialisation
we need.

Proof of $H_{N}(3)$. Since in $H_{N}(k)$, $j$ varies from $2$ to $k-1$, then
in $H_{N}(3)$, $j$ only takes the value $2$. Then, to prove $H_{N}(3)$, we
just have to prove that for all $x\in V_{3}$, $N_{2}(x)$ is equal to
$W_{2}(x)=\\{y\in V_{2}\ |\ O_{1}(x)\subseteq O_{1}(y)\subseteq O_{2}(x)\\}$.
Let $x\in V_{3}$; we first show that $N_{2}(x)\subseteq W_{2}(x)$. We denote
by $a_{1},\ldots,a_{l}$, with $l\geq 2$, the elements of the set $N_{2}(x)$.
Clearly, for any $i\in\llbracket 1,l\rrbracket$, $\bigcap_{1\leq i\leq
l}N_{0}(a_{i})\subseteq N_{0}(a_{i})\subseteq\bigcup_{1\leq i\leq
l}N_{0}(a_{i})$. From Definition 10, we have $N_{0}(a_{i})=O_{1}(a_{i})$,
$O_{1}(x)=N_{0}(x)=\bigcap_{1\leq i\leq l}N_{0}(a_{i})$, and
$K(O_{2}(x))=\bigcap_{1\leq i\leq l}N_{1}(a_{i})$. Moreover, from Remark 3,
$N_{1}(a_{i})=K(O_{1}(a_{i}))$, so we have $K(O_{2}(x))=\bigcap_{1\leq i\leq
l}K(O_{1}(a_{i}))$. And since, by definition, $O_{2}(x)\in{\cal{O}}^{\prime}$,
then, from Remark 2, $\bigcup_{1\leq i\leq l}O_{1}(a_{i})\subseteq O_{2}(x)$.
Consequently, for any $i\in\llbracket 1,l\rrbracket$, $O_{1}(x)\subseteq
O_{1}(a_{i})\subseteq O_{2}(x)$. That is $N_{2}(x)\subseteq W_{2}(x)$.

Conversely, we show that if $y\in W_{2}(x)$, then $y\in N_{2}(x)$. To that
purpose, we show that $N_{0}(x)\subseteq N_{0}(y)$ and $N_{1}(x)\subseteq
N_{1}(y)$, which implies, by maximality of $x$ in $V^{*}_{3}$ (see Definition
2), that $y\in N_{2}(x)$. First, we have $N_{0}(x)=O_{1}(x)$, and since $y\in
W_{2}(x)$, we also have $O_{1}(x)\subseteq O_{1}(y)=N_{0}(y)$. Then,
$N_{0}(x)\subseteq N_{0}(y)$. Since $O_{1}(y)\subseteq O_{2}(x)$, we have
$K(O_{2}(x))\subseteq K(O_{1}(y))$. And from Remark 3, we have
$K(O_{1}(y))=N_{1}(y)$ and $K(O_{2}(x))=N_{1}(x)$. Thus, $N_{1}(x)\subseteq
N_{1}(y)$ and we conclude that $y\in N_{2}(x)$. Finally, we showed that
$N_{2}(x)=W_{2}(x)$, and so $H_{N}(3)$ is true.

Proof of $H_{tar}(3)$. Since, from $H_{N}(3)$, $N_{2}(x)=W_{2}(x)$ and since
$|N_{2}(x)|\geq 2$, it follows that $O_{1}(x)\subsetneq O_{2}(x)$, otherwise
$W_{2}(x)$ would contain at most one element. By definition of $V^{*}_{3}$,
$|N_{0}(x)|\geq 2$. Since $O_{1}(x)=|N_{0}(x)|$, it follows that $O_{1}(x)$,
and so $O_{2}(x)$, contains at least two elements. Moreover, from Remark 3, we
have $K(O_{2}(x))=N_{1}(x)$. And from Definition 7, $|N_{1}(x)|\geq 2$. It
follows that $K(O_{2}(x))$ contains at least two elements, and so does
$K(O_{1}(x))$ since $K(O_{2}(x))\subseteq K(O_{1}(x))$. Thus $O_{1}(x)$ and
$O_{2}(x)$ both belong to ${\cal{O}}$: $H_{tar}(3)$ is true.

Proof of $H_{inj}(3)$. For any $z\in V_{3}$, $N_{2}(z)=W_{2}(z)$. Thus, for
any $x,y\in V_{3}$, $(O_{1}(x),O_{2}(x))=(O_{1}(y),O_{2}(y))$ implies that
$N_{2}(x)=N_{2}(y)$, which implies that $x=y$. So $H_{inj}(3)$ holds.

Proof of $H_{sur}(3)$. Let $O_{1},O_{2}\in{\cal{O}}$ such that
$O_{1}\subsetneq O_{2}$. We will find an element $x$ of $V_{3}$ such that
$O_{1}(x)=O_{1}$ and $O_{2}(x)=O_{2}$. Let $Y=\\{y\in V_{2}\ |\ O_{1}\subseteq
O_{1}(y)\subseteq O_{2}\\}$. Let $x=Y\cup\bigcap_{y\in Y}N(y)$, we prove that
$x$ is the desired element.

First, to prove that $x\in V_{3}$, we must prove that $x\in V^{*}_{3}$, that
is $|x\cap V_{2}|\geq 2$ and $|x\cap V_{1}|\geq 2$ and $|x\cap V_{0}|\geq 2$.
From Lemma 2 , there exists two distinct elements $y_{1},y_{2}\in V_{2}$ such
that $O_{1}(y_{1})=O_{1}$ and $O_{1}(y_{2})=O_{2}$. Clearly,
$\\{y_{1},y_{2}\\}\subseteq Y$, which gives $|x\cap V_{2}|\geq 2$.
Furthermore, $x\cap V_{1}=\bigcap_{y\in Y}N_{1}(y)=\bigcap_{y\in
Y}K(O_{1}(y))$, from Remark 3. Since, for any $y\in Y$, $O_{1}(y)\subseteq
O_{2}$, we have also $K(O_{2})\subseteq K(O_{1}(y))$. It follows that
$K(O_{2})\subseteq x\cap V_{1}$, and $O_{2}\in{\cal{O}}$ implies that
$|K(O_{2})|\geq 2$, then $|x\cap V_{1}|\geq 2$. We also have $x\cap
V_{0}=\bigcap_{y\in Y}N_{0}(y)=\bigcap_{y\in Y}O_{1}(y)$. And since
$O_{1}\subseteq O_{1}(y)$ for all $y\in Y$, then $O_{1}\subseteq x\cap V_{0}$.
It follows that $|x\cap V_{0}|\geq 2$.

We now show that $x$ is maximal in $V^{*}_{3}$. Let $z\in V_{2}\setminus Y$
i.e. $O_{1}\not\subseteq O_{1}(z)$ or $O_{1}(z)\not\subseteq O_{2}$, we prove
that $x\cap V_{0}\not\subseteq N_{0}(z)$ or $x\cap V_{1}\not\subseteq
N_{1}(z)$, which implies that $\bigcap_{y\in
Y\cup\\{z\\}}N(y)\subsetneq\bigcap_{y\in Y}N(y)$ and that $x$ is maximal,
since this holds for all $z\in V_{2}\setminus Y$. Let us first note that
$x\cap V_{0}=\bigcap_{y\in Y}N_{0}(y)=\bigcap_{y\in Y}O_{1}(y)=O_{1}$, the
last equality coming from the fact that $\forall O\in{\cal{O}},\exists z\in
V_{2},O_{1}(z)=O$ (see Lemma 2). On the other hand $x\cap V_{1}=\bigcap_{y\in
Y}N_{1}(y)=\bigcap_{y\in Y}K(O_{1}(y))=K(\bigcup_{y\in Y}O_{1}(y))=K(O_{2})$,
again using Lemma 2 for the last equality. Now, if $O_{1}(z)\not\subseteq
O_{2}$, since $O_{1}(z)\in{\cal{O}}^{\prime}$, then, from Remark 1,
$K(O_{2})\not\subseteq K(O_{1}(z))$. And since, from what precedes,
$K(O_{2})=x\cap V_{1}$ and, from Remark 3, $K(O_{1}(z))=N_{1}(z)$, we obtain
$x\cap V_{1}\not\subseteq N_{1}(z)$. On the other hand, if $O_{1}\not\subseteq
O_{1}(z)$, since $O_{1}=x\cap V_{0}$ (see above) and $O_{1}(z)=N_{0}(z)$ (by
definition), we obtain $x\cap V_{0}\not\subseteq N_{0}(z)$. Consequently, $x$
is maximal in $V^{*}_{3}$ and then $x\in V_{3}$.

The last condition we have to check for proving $H_{sur}(3)$ is that
$O_{1}(x)=O_{1}$ and $O_{2}(x)=O_{2}$. We already have
$O_{1}=N_{0}(x)=O_{1}(x)$. Moreover by definition, $O_{2}(x)$ is the unique
element of ${\cal{O}}^{\prime}$ such that $K(O_{2}(x))=\bigcap_{y\in
Y}N_{1}(y)$, and we also have from above that $K(O_{2})=\bigcap_{y\in
Y}N_{1}(y)$, then $O_{2}(x)=O_{2}$.

Finally, $H_{sur}(3)$ is true.

Recursion step. Now, let us suppose that $k\geq 4$ and that for all $i$ such
that $3\leq i<k$, $H_{tar}(i)$, $H_{inj}(i)$, $H_{sur}(i)$ and $H_{E}(i)$ are
true. Note that we did not prove $H_{E}(3)$, which is not even defined, but we
don’t need it. Actually, in step $k$ of the recursion, $H_{E}(k-1)$ is used
only in the proof of $H_{N}(k)$. For proving $H_{N}(4)$, the use of $H_{E}(3)$
is replaced by the use of the definition of $V_{3}^{*}$ (Definition 7).

Proof of $H_{N}(k)$. Let $x\in V_{k}$. We denote by $a_{1},\ldots,a_{l}$ the
elements of the set $N_{k-1}(x)$. Let $i_{1},i_{2}\in\llbracket
1,l\rrbracket$. If $k\geq 5$, by hypothesis $H_{E}(k-1)$, we have that
$N_{p}(a_{i_{1}})=N_{p}(a_{i_{2}})=N_{p}(x)$ for all $p\in\llbracket
0,k-3\rrbracket\setminus\\{1\\}$. If $k=4$, by Definition 7, we have that
$N_{0}(a_{i_{1}})=N_{0}(a_{i_{2}})=N_{0}(x)$. Thus, independently of the value
of $k\geq 4$ we have $N_{p}(a_{i_{1}})=N_{p}(a_{i_{2}})=N_{p}(x)$ for all
$p\in\llbracket 0,k-3\rrbracket\setminus\\{1\\}$. Then, using the Definition
10 of the characterising sequence, it follows that, for $p=0$, we obtain
$O_{1}(a_{i})=O_{1}(a_{j})$ and for $p\in\llbracket 2,k-3\rrbracket$, we
obtain $O_{p}(a_{i})=O_{p}(a_{j})=O_{p}(x)$.

Let $j\in\llbracket 2,k-3\rrbracket$ and let $i\in\llbracket 1,l\rrbracket$.
From recursion hypothesis $H_{N}(k-1)$ applied to $a_{i}$, we have
$N_{j}(a_{i})=W_{j}(a_{i})$. Since for all $q\in\llbracket 1,k-3\rrbracket$ we
have $O_{q}(x)=O_{q}(a_{i})$, then, from the definition of $W_{j}$, it follows
that $W_{j}(x)=W_{j}(a_{i})$. Finally, since $N_{j}(x)=N_{j}(a_{i})$, we
obtain $N_{j}(x)=W_{j}(x)$, for all $2\leq j\leq k-3$. Then we just have to
prove that $N_{k-2}(x)=W_{k-2}(x)$ and $N_{k-1}(x)=W_{k-1}(x)$.

We start with $N_{k-1}(x)$. We will first show that for any $i\in\llbracket
1,l\rrbracket$ we have $a_{i}\in W_{k-1}(x)$, that is $N_{k-1}(x)\subseteq
W_{k-1}(x)$. As explained above, we already know that, for all $q\in\llbracket
1,k-3\rrbracket$, $O_{q}(x)=O_{q}(a_{i})$. Then, we only need to show that
$O_{k-2}(x)\subseteq O_{k-2}(a_{i})\subseteq O_{k-1}(x)$.

Let us show the first inclusion: $O_{k-2}(x)\subseteq O_{k-2}(a_{i})$. By
definition, $N_{k-2}(x)=\bigcap_{t\in\llbracket
1,l\rrbracket}N_{k-2}(a_{t})\subseteq N_{k-2}(a_{i})$. Then, we have
$\bigcap_{b\in N_{k-2}(a_{i})}N_{1}(b)\subseteq\bigcap_{b\in
N_{k-2}(x)}N_{1}(b)$. And since, by definition, $\bigcap_{b\in
N_{k-2}(a_{i})}N_{1}(b)=K(O_{k-2}(a_{i})$ and $\bigcap_{b\in
N_{k-2}(x)}N_{1}(b)=K(O_{k-2}(x)$, then we obtain $K(O_{k-2}(a_{i}))\subseteq
K(O_{k-2}(x))$. Thus, from Remark 1, we have $O_{k-2}(x)\subseteq
O_{k-2}(a_{i})$.

Let us now show the second inclusion: $O_{k-2}(a_{i})\subseteq O_{k-1}(x)$.
Since $N_{k-2}(a_{i})\subseteq\bigcup_{t\in\llbracket
1,l\rrbracket}N_{k-2}(a_{t})$ then $\bigcap_{b\in
N_{k-2}(a_{i})}N_{1}(b)\supseteq\bigcap_{b\in\bigcup_{t\in\llbracket
1,l\rrbracket}N_{k-2}(a_{t})}N_{1}(b)$, and by definition $\bigcap_{b\in
N_{k-2}(a_{i})}N_{1}(b)=K(O_{k-2}(a_{i}))$. In order to show the inclusion we
aim at, we will show that $\bigcap_{b\in\bigcup_{t\in\llbracket
1,l\rrbracket}N_{k-2}(a_{t})}N_{1}(b)=\bigcap_{t\in\llbracket
1,l\rrbracket}N_{1}(a_{t})$. Since, by definition again,
$\bigcap_{t\in\llbracket 1,l\rrbracket}N_{1}(a_{t})=K(O_{1}(x))$, this will
give $K(O_{k-2}(a_{i}))\supseteq K(O_{k-2}(x))$, which implies
$O_{k-2}(a_{i}))\subseteq O_{k-2}(x)$, the inclusion we aim at.

Then, let us show the equality $\bigcap_{b\in\bigcup_{t\in\llbracket
1,l\rrbracket}N_{k-2}(a_{t})}N_{1}(b)=\bigcap_{t\in\llbracket
1,l\rrbracket}N_{1}(a_{t})$ by a double inclusion. Let
$z\in\bigcap_{t\in\llbracket 1,l\rrbracket}N_{1}(a_{t})$, then for all
$t\in\llbracket 1,l\rrbracket$, $z\in N_{1}(a_{t})$. It follows that for all
$b\in N_{k-2}(a_{t})$, $z\in N_{1}(b)$. Since this holds for all
$t\in\llbracket 1,l\rrbracket$ and for all $b\in N_{k-2}(a_{t})$, then we
obtain $z\in\bigcap_{b\in\bigcup_{t\in\llbracket
1,l\rrbracket}N_{k-2}(t)}N_{1}(b)$. Conversely, let
$z\in\bigcap_{b\in\bigcup_{t\in\llbracket
1,l\rrbracket}N_{k-2}(a_{t})}N_{1}(b)$, we show that
$z\in\bigcap_{t\in\llbracket 1,l\rrbracket}N_{1}(a_{t})$. For all
$b\in\bigcup_{t\in\llbracket 1,l\rrbracket}N_{k-2}(a_{t})$ we have $z\in
N_{1}(b)$. In particular, for any $t\in\llbracket 1,l\rrbracket$ and for any
$b\in N_{k-2}(a_{t})$, we have $z\in N_{1}(b)$, and so $z\in N_{1}(a_{t})$. As
this holds for any $t\in\llbracket 1,l\rrbracket$, then
$z\in\bigcap_{t\in\llbracket 1,l\rrbracket}N_{1}(a_{t})$, that is
$\bigcap_{b\in\bigcup_{t\in\llbracket
1,l\rrbracket}N_{k-2}(t)}N_{1}(b)\subseteq\bigcap_{t\in\llbracket
1,l\rrbracket}N_{1}(a_{t})$. Finally, as we already showed the converse
inclusion, we obtain $\bigcap_{b\in\bigcup_{t\in\llbracket
1,l\rrbracket}N_{k-2}(t)}N_{1}(b)=\bigcap_{t\in\llbracket
1,l\rrbracket}N_{1}(a_{t})$.

We can now finish the proof of the inclusion $N_{k-1}(x)\subseteq W_{k-1}(x)$.
Remember that $\bigcap_{b\in
N_{k-2}(a_{i})}N_{1}(b)\supseteq\bigcap_{b\in\bigcup_{t\in\llbracket
1,l\rrbracket}N_{k-2}(t)}N_{1}(b)$ and that by definition $\bigcap_{b\in
N_{k-2}(a_{i})}N_{1}(b)=K(O_{k-2}(a_{i})$.
In addition, we just proved that $\bigcap_{b\in\bigcup_{t\in\llbracket
1,l\rrbracket}N_{k-2}(t)}N_{1}(b)=\bigcap_{t\in\llbracket
1,l\rrbracket}N_{1}(a_{t})$, and, by definition again, we have
$\bigcap_{t\in\llbracket 1,l\rrbracket}N_{1}(a_{t})=K(O_{k-1}(x))$. We then
obtain $K(O_{k-2}(a_{i}))$ $\supseteq K(O_{k-1}(x))$, and Remark 1 concludes
that $O_{k-2}(a_{i})\subseteq O_{k-1}(x)$, for all $i\in\llbracket
1,l\rrbracket$. So finally, putting everything together (we proved above that
$O_{k-2}(x)\subseteq O_{k-2}(a_{i})$) we get $O_{k-2}(x)\subseteq
O_{k-2}(a_{i})\subseteq O_{k-1}(x)$, for all $i\in\llbracket 1,l\rrbracket$,
which completes our proof of $a_{i}\in W_{k-1}(x)$, for all $i\in\llbracket
1,l\rrbracket$, that is $N_{k-1}(x)\subseteq W_{k-1}(x)$.

Let us now prove the converse inclusion: $W_{k-1}(x)\subseteq N_{k-1}(x)$. Let
$y\in W_{k-1}(x)$, we have $O_{q}(y)=O_{q}(x)$ for all $q\in\llbracket
1,k-3\rrbracket$. Moreover, as we showed at the beginning of the proof of
$H_{N}(k)$, for all $i\in\llbracket 1,l\rrbracket$, and all $q\in\llbracket
1,k-3\rrbracket$ we have $O_{q}(a_{i})=O_{q}(x)$ and so
$O_{q}(a_{i})=O_{q}(y)$. For $q=1$, from the definition of $O_{1}$, this gives
$N_{0}(a_{i})=N_{0}(y)$. For $q\geq 2$ (which occurs only for $k\geq 5$),
using recursion hypothesis $H_{N}(k-1)$ that characterises, for any $z\in
V_{k-1}$ and any $q\geq 2$, $N_{q}(z)$ as a function of only
$O_{1}(z),\ldots,O_{q}(z)$, we then obtain that since $y$ and $a_{i}$ have the
same sequence $O_{1}(y),\ldots,O_{k-3}(y)=O_{1}(a_{i}),\ldots,O_{k-3}(a_{i})$,
they necessarily have the same neighbourhood $N_{q}(y)=N_{q}(a_{i})$, for all
$q\in\llbracket 2,k-3\rrbracket$. Since we showed that $y$ and $a_{i}$ also
have the same neighbourhood on $V_{0}$, and since we showed at the beginning
of the proof of $H_{N}(k)$ that $N_{p}(a_{i})=N_{p}(x)$ for all
$p\in\llbracket 0,k-3\rrbracket\setminus\\{1\\}$, it follows that for all
$p\in\llbracket 0,k-3\rrbracket\setminus\\{1\\}$, we have $N_{p}(y)=N_{p}(x)$.
Then, in order to show that $y\in N_{k-1}(x)$, we only need to show that
$N_{1}(x)\subseteq N_{1}(y)$ and $N_{k-2}(x)\subseteq N_{k-2}(y)$, which
implies, by maximality of $x$ (see Definition 2), that $y\in N_{k-1}(x)$.
First, let us show that $N_{1}(x)\subseteq N_{1}(y)$. Since $y\in W_{k-1}(x)$,
we have $O_{k-2}(y)\subseteq O_{k-1}(x)$, which implies
$K(O_{k-1}(x))\subseteq K(O_{k-2}(y))$. And since, from remark 3,
$K(O_{k-1}(x))=N_{1}(x)$ and $K(O_{k-2}(y))=N_{1}(y)$, then we get the desired
inclusion: $N_{1}(x)\subseteq N_{1}(y)$.

Let us now show that $N_{k-2}(x)\subseteq N_{k-2}(y)$. Let $z\in N_{k-2}(x)$.
By recursion hypothesis $H_{N}(k-1)$, we know that $N_{k-2}(y)=W_{k-2}(y)$.
Thus, our aim is to show that $z\in W_{k-2}(y)$, that is $O_{q}(z)=O_{q}(y)$
for all $q\in\llbracket 1,k-4\rrbracket$ and $O_{k-3}(y)\subseteq
O_{k-3}(z)\subseteq O_{k-2}(y)$. Let $i\in\llbracket 1,l\rrbracket$, since
$z\in N_{k-2}(x)$ then $z\in N_{k-2}(a_{i})$. It follows by recursion
hypothesis $H_{N}(k-1)$ that for all $q\in\llbracket
1,k-4\rrbracket,O_{q}(z)=O_{q}(a_{i})$. And since we already showed that
$O_{q}(a_{i})=O_{q}(x)$, then we obtain $O_{q}(z)=O_{q}(x)$ for all
$q\in\llbracket 1,k-4\rrbracket$. On the other hand, since $y\in W_{k-1}(x)$,
then $O_{q}(y)=O_{q}(x)$ for all $q\in\llbracket 1,k-4\rrbracket$, which
finally gives that $O_{q}(y)=O_{q}(z)$ for all $q\in\llbracket
1,k-4\rrbracket$.

Let us now show that $O_{k-3}(z)\subseteq O_{k-2}(y)$. Since $y\in
W_{k-1}(x)$, we have $O_{k-2}(x)\subseteq O_{k-2}(y)$. Then, it is sufficient
to show that $O_{k-3}(z)\subseteq O_{k-2}(x)$. We state this fact as a
proposition as we use it further in the proof:
(Prop. A) for any vertex $z\in N_{k-2}(x)$, we have $O_{k-3}(z)\subseteq
O_{k-2}(x)$.
Clearly, since $z\in N_{k-2}(x)$, we have $N_{1}(z)\supseteq\bigcap_{b\in
N_{k-2}(x)}N_{1}(b)$. By definition, $N_{1}(z)=K(O_{k-3}(z)$ and
$\bigcap_{b\in N_{k-2}(x)}N_{1}(b)=K(O_{k-2}(x))$. We then obtain
$K(O_{k-3}(z))$ $\supseteq K(O_{k-2}(x))$, which gives, from Remark 1,
$O_{k-3}(z)\subseteq O_{k-2}(x)$. And since $y\in W_{k-1}(x)$, we have
$O_{k-2}(x)\subseteq O_{k-2}(y)$. Thus, $O_{k-3}(z)\subseteq O_{k-2}(y)$.

We now show that $O_{k-3}(y)\subseteq O_{k-3}(z)$. Since $y\in W_{k-1}(x)$,
then $O_{k-3}(y)=O_{k-3}(x)$. As we already showed, for any $i\in\llbracket
1,l\rrbracket$, we have $O_{k-3}(x)=O_{k-3}(a_{i})$, and so
$O_{k-3}(y)=O_{k-3}(a_{i})$. Moreover, since $z\in N_{k-2}(x)$ then $z\in
N_{k-2}(a_{i})$. And by recursion hypothesis $H_{N}(k-1)$, we have
$W_{k-2}(a_{i})=N_{k-2}(a_{i})$. Thus, $z\in W_{k-2}(a_{i})$ satisfies
$O_{k-3}(a_{i})\subseteq O_{k-3}(z)$. Finally, we obtain $O_{k-3}(y)\subseteq
O_{k-3}(z)$, which achieves the proof of $z\in N_{k-2}(y)$. Thus, we have
$N_{k-2}(x)\subseteq N_{k-2}(y)$.

In summary, we showed that for any $y\in W_{k-1}(x)$, we have
$N_{p}(y)=N_{p}(x)$ for all $p\in\llbracket 0,k-3\rrbracket\setminus\\{1\\}$
and $N_{1}(x)\subseteq N_{1}(y)$ and $N_{k-2}(x)\subseteq N_{k-2}(y)$. Then,
by maximality of $x$ (see Definition 2), $y$ belongs to $N_{k-1}(x)$. That is,
$W_{k-1}(x)\subseteq N_{k-1}(x)$. As we also showed the converse inclusion, we
obtain $N_{k-1}(x)=W_{k-1}(x)$.

In order to achieve the proof of $H_{N}(k)$, we still have to show that
$N_{k-2}(x)=W_{k-2}(x)$. We start with $W_{k-2}(x)\subseteq N_{k-2}(x)$. Let
$z\in W_{k-2}(x)$. Let $i\in\llbracket 1,l\rrbracket$, we show that $z\in
N_{k-2}(a_{i})$. By recursion hypothesis $H_{N}(k-1)$ we know that
$N_{k-2}(a_{i})=W_{k-2}(a_{i})=\\{w\in V_{k-2}\ |\
(O_{1}(w),\ldots,O_{k-4}(w))=(O_{1}(a_{i}),\ldots,O_{k-4}(a_{i}))\text{ and
}O_{k-3}(a_{i})$ $\subseteq O_{k-3}(w)\subseteq O_{k-2}(a_{i})\\}$. As we
already mentioned several times, we have $(O_{1}(a_{i}),\ldots,$
$O_{k-4}(a_{i}))=(O_{1}(x),\ldots,O_{k-4}(x))$. Since $z\in W_{k-2}(x)$, we
also have $(O_{1}(z),\ldots,$ $O_{k-4}(z))=(O_{1}(x),\ldots,O_{k-4}(x))$, and
then $(O_{1}(z),\ldots,O_{k-4}(z))=(O_{1}(a_{i}),\ldots,$ $O_{k-4}(a_{i}))$.
Again, since $z\in W_{k-2}(x)$, we have $O_{k-3}(x)\subseteq
O_{k-3}(z)\subseteq O_{k-2}(x)$. Since we already proved that
$N_{k-1}(x)=W_{k-1}(x)$, we know that $O_{k-3}(a_{i})=O_{k-3}(x)$ and
$O_{k-2}(x)\subseteq O_{k-2}(a_{i})$. It follows that $O_{k-3}(a_{i})\subseteq
O_{k-3}(z)\subseteq O_{k-2}(a_{i})$, which shows that $z\in N_{k-2}(a_{i})$.
As this holds for any $i\in\llbracket 1,l\rrbracket$, then we conclude that
$z\in N_{k-2}(x)$.

Conversely, let $z\in N_{k-2}(x)$. Then, for all $i\in\llbracket
1,l\rrbracket$, $z\in N_{k-2}(a_{i})$. From recursion hypothesis $H_{N}(k-1)$
applied to $a_{i}$, we get
$(O_{1}(z),\ldots,O_{k-4}(z))=(O_{1}(a_{i}),\ldots,$ $O_{k-4}(a_{i}))$. And
for the same reason, we also have $O_{k-3}(a_{i})\subseteq O_{k-3}(z)$. As we
know that $(O_{1}(a_{i}),\ldots,O_{k-3}(a_{i}))=(O_{1}(x),\ldots,O_{k-3}(x))$,
we obtain $(O_{1}(z),\ldots,O_{k-4}(z))$ $=(O_{1}(x),\ldots,O_{k-4}(x))$ and
$O_{k-3}(x)\subseteq O_{k-3}(z)$. Then, the only thing left we have to show in
order to prove that $z\in W_{k-2}(x)$, which is our goal, is to prove that
$O_{k-3}(z)\subseteq O_{k-2}(x)$. In fact, we already proved this proposition
in the proof of $W_{k-1}(x)\subseteq N_{k-1}(x)$ above, referred as (Prop. A)
in the text. So we finally obtain that $N_{k-2}(x)\subseteq W_{k-2}(x)$, and
since we already proved the converse inclusion, we obtain the equality between
the two sets, $N_{k-2}(x)=W_{k-2}(x)$, which completes our proof of
$H_{N}(k)$.

Proof of $H_{tar}(k)$. From $H_{N}(k)$ we know that for any $i\in\llbracket
1,l\rrbracket$, $(O_{1}(a_{i}),\ldots,O_{k-3}(a_{i}))$
$=(O_{1}(x),\ldots,O_{k-3}(x))$. Then, from recursion hypothesis
$H_{tar}(k-1)$, we have $O_{1}(x)\subsetneq\ldots\subsetneq O_{k-3}(x)$ and,
in particular, we have $O_{1}(x)\in{\cal{O}}$ and so $|O_{1}(x)|\geq 2$. Since
$N_{k-2}(x)=W_{k-2}(x)$ and $|N_{k-2}(x)|>1$, necessarily
$O_{k-3}(x)\subsetneq O_{k-2}(x)$. Similarly, the fact that
$N_{k-1}(x)=W_{k-1}(x)$ and $|N_{k-1}(x)|>1$ implies that
$O_{k-2}(x)\subsetneq O_{k-1}(x)$. At last, from Remark 3, we have
$K(O_{k-1}(x))=N_{1}(x)$, and since $|N_{1}(x)|\geq 2$, it follows that
$|K(O_{k-1}(x))|\geq 2$. Combined with the fact that $|O_{1}(x)|\geq 2$, this
implies that for all $j\in\llbracket 1,k-1\rrbracket$, we have
$O_{j}(x)\in{\cal{O}}$. Thus, $H_{tar}(k)$ is true.

Proof of $H_{inj}(k)$. Let $x,x^{\prime}\in V_{k}$ such that
$S(x)=S(x^{\prime})$. From $H_{N}(k)$, $N_{k-1}(x)=W_{k-1}(x)$ and
$N_{k-1}(x^{\prime})=W_{k-1}(x^{\prime})$. And since $S(x)=S(x^{\prime})$, we
have $W_{k-1}(x)=W_{k-1}(x^{\prime})$. As a consequence,
$N_{k-1}(x)=N_{k-1}(x^{\prime})$ and so $x=x^{\prime}$. Therefore $H_{inj}(k)$
is true.

Proof of $H_{sur}(k)$. Let $(O_{1},\ldots,O_{k-1})\in{\cal{O}}^{k-1}$ such
that $O_{1}\subsetneq\ldots\subsetneq O_{k-1}$. From recursion hypothesis
$H_{sur}(k-1)$, for any $P\in{\cal{O}}$ such that $O_{k-3}\subsetneq P$, there
exists $y_{P}\in V_{k-1}$ such that $S(y_{P})=(O_{1},\ldots,O_{k-3},P)$. We
denote by $Y$ the set $Y=\\{y\in V_{k-1}\ |\
(O_{1}(y),\ldots,O_{k-3}(y))=(O_{1},\ldots,O_{k-3})\text{ and
}O_{k-2}\subseteq O_{k-2}(y)\subseteq O_{k-1}\\}$. Let $x=Y\cup\bigcap_{y\in
Y}N(y)$. We will show that $x$ is maximal in $V_{k}^{*}$ and that the
corresponding element of $V_{k}$ has the desired sequence
$S(x)=(O_{1},\ldots,O_{k-1})$.

Let us start by showing that $x\in V_{k}^{*}$. Since $O_{k-2}\subsetneq
O_{k-1}$, we have $|Y|\geq 2$, that is $|x\cap V_{k-1}|\geq 2$. From recursion
hypothesis $H_{N}(k-1)$, for any $y\in Y$, $N_{k-2}(y)=\\{t\in V_{k-2}\ |\
(O_{1}(t),\ldots,O_{k-4}(t))=(O_{1},\ldots,O_{k-4})$ and $O_{k-3}\subseteq
O_{k-3}(t)\subseteq O_{k-2}(y)\\}$. And since, by definition,
$O_{k-2}\subseteq O_{k-2}(y)$, then $N_{k-2}(y)$ contains at least the two
elements of $V_{k-2}$ having characterising sequences
$(O_{1},\ldots,O_{k-4},O_{k-3})$ and $(O_{1},\ldots,O_{k-4},O_{k-2})$, which
do exist from recursion hypothesis $H_{sur}$. Since this is true for all $y\in
N_{k-2}(x)$, then $x$ itself has these two elements as neighbours on level
$V_{k-2}$. Then, $|x\cap V_{k-2}|\geq 2$. Let us now show that $|x\cap
V_{1}|\geq 2$. For any $y\in Y$, from Remark 3, we have
$N_{1}(y)=K(O_{k-2}(y))$. Since $O_{k-2}(y)\subseteq O_{k-1}$ then
$K(O_{k-2}(y))\supseteq K(O_{k-1})$. Thus, we obtain $x\cap
V_{1}=\bigcap_{y\in Y}N_{1}(y)=\bigcap_{y\in Y}K(O_{k-2}(y))\supseteq
K(O_{k-1})$. And since $O_{k-1}\in{\cal{O}}$, $O_{k-1}$ contains at least two
elements and so does $x\cap V_{1}$. In order to complete the proof of $x\in
V_{k}^{*}$, we need to show that for all $y,y^{\prime}\in Y$, we have
$N_{k-3}(y)=N_{k-3}(y^{\prime})$. First, note that, by definition,
$(O_{1}(y),\ldots,O_{k-3}(y))=(O_{1}(y^{\prime}),\ldots,O_{k-3}(y^{\prime}))=(O_{1},\ldots,O_{k-3})$.
Moreover, recursion hypothesis $H_{N}(k-1)$ gives that the neighbourhood at
level $V_{k-3}$ of any vertex $z\in V_{k-1}$ only depends on the piece of
sequence $(O_{1}(z),\ldots,O_{k-3}(z))$. And since $y$ and $y^{\prime}$ have
the same such pieces of sequence, it follows that
$N_{k-3}(y)=N_{k-3}(y^{\prime})$. Thus $x\in V^{*}_{k}$.

We will now show that $x$ is maximal in $V^{*}_{k}$. Let $z\in
V_{k-1}\setminus Y$, we show that if for some $j\in\llbracket
1,k-3\rrbracket,O_{j}(z)\neq O_{j}$ then there is no element $B\in V_{k}^{*}$
containing $Y\cup\\{z\\}$. We denote $y\in Y$ an arbitrary element of $Y$ and
we distinguish between the case where $k=4$ and the case where $k\geq 5$.

Let us start with the general case where $k\geq 5$, we show that
$N_{k-3}(z)\neq N_{k-3}(y)$, which implies, from Definition 7, that there is
no element of $V_{k}^{*}$ containing both $y$ and $z$. So let $j\in\llbracket
1,k-3\rrbracket$, such that $O_{j}(z)\neq O_{j}$. Since $O_{j}(y)=O_{j}$, then
we have $O_{j}(z)\neq O_{j}(y)$. Moreover, from recursion hypothesis
$H_{N}(k-1)$, we have $N_{k-3}(z)=W_{k-3}(z)$ and $N_{k-3}(y)=W_{k-3}(y)$. We
again distinguish several cases depending on the value of $j$.
If $j\leq k-5$ (which may occur only when $k\geq 6$), from recursion
hypothesis $H_{sur}(k-3)$, there exists $t_{1}\in V_{k-3}$ such that
$S(t_{1})=(O_{1}(z),\ldots,O_{k-4}(z))$. Clearly, from the definition of
$W_{j}(z)$, we have $t_{1}\in W_{k-3}(z)=N_{k-3}(z)$. On the opposite, from
the definition of $W_{j}(y)$, and since $O_{j}(z)\neq O_{j}(y)$ with $j\leq
k-5$, we obtain $t_{1}\not\in W_{k-3}(y)=N_{k-3}(y)$ and it follows that
$N_{k-3}(z)\neq N_{k-3}(y)$.
If $j=k-4$. Since $O_{k-4}(z)\neq O_{k-4}(y)$, then one of the two sets
$O_{k-4}(z),O_{k-4}(y)$ is not included in the other, say
$O_{k-4}(y)\not\subseteq O_{k-4}(z)$ without loss of generality. Consider
again the element $t_{1}\in N_{k-3}(z)$ described above. Since
$O_{k-4}(t_{1})=O_{k-4}(z)\not\supseteq O_{k-4}(y)$, then it follows, from the
definition of $W_{k-4}(y)$, that $t_{1}\not\in W_{k-3}(y)=N_{k-3}(y)$, and so
$N_{k-3}(z)\neq N_{k-3}(y)$.
If $j=k-3$, without loss of generality we can assume that
$O_{k-3}(z)\not\subseteq O_{k-3}(y)$. From recursion hypothesis
$H_{sur}(k-3)$, there exists $t_{2}\in V_{k-3}$ such that
$O_{k-4}(t_{2})=O_{k-3}(z)$ and
$(O_{1}(z),\ldots,O_{k-5}(z))=(O_{1}(z),\ldots,O_{k-5}(z))$ (using, as usual,
the convention $(O_{1}(z),\ldots,O_{k-5}(z))=()$ if $k=5$). From the
definition of $W_{k-3}(z)$ and $W_{k-3}(y)$, we obtain that $t_{2}\in
W_{k-3}(z)=N_{k-3}(z)$ but, since $O_{k-3}(z)\not\subseteq O_{k-3}(y)$, we
have $t_{2}\not\in W_{k-3}(y)=N_{k-3}(y)$. Thus, in all cases where $k\geq 5$,
if there exists some $j\in\llbracket 1,k-3\rrbracket$ such that $O_{j}(z)\neq
O_{j}$, then $N_{k-3}(z)\neq N_{k-3}(y)$.

Let us now deal with the particular case where $k=4$. In this case,
necessarily the index $j\in\llbracket 1,k-3\rrbracket$ such that $O_{j}(z)\neq
O_{j}$ is $j=1$. We immediately obtain that $N_{0}(z)=O_{1}(z)\neq
O_{1}(y)=N_{0}(y)$. Then, from Definition 7 (case $k=4$), there is no element
$B\in V_{k}^{*}$ containing both $y$ and $z$.
Finally, we conclude that, regardless of the value of $k\geq 4$, if for some
$j\in\llbracket 1,k-3\rrbracket,O_{j}(z)\neq O_{j}$ then there is no element
$B\in V_{k}^{*}$ containing $Y\cup\\{z\\}$.

Thus, to show that $x$ is maximal in $V_{k}^{*}$ we only need to show that for
any $z\in V_{k-1}$ such that
$(O_{1}(z),\ldots,O_{k-3}(z))=(O_{1},\ldots,O_{k-3})$, if
$O_{k-2}\not\subseteq O_{k-2}(z)$ or $O_{k-2}(z)\not\subseteq O_{k-1}$, then
we have $\bigcap_{y\in Y}N(y)\not\subseteq N(z)$.

We first treat the case where $O_{k-2}(z)\not\subseteq O_{k-1}$. In this case,
from Remark 1, $K(O_{k-1})\not\subseteq K(O_{k-2}(z))$. From Remark 3, we have
$K(O_{k-2}(z))=N_{1}(z)$. We now show that $K(O_{k-1})=\bigcap_{y\in X\cap
V_{k-1}}N_{1}(y)$, which will give us the desired result: $\bigcap_{y\in x\cap
V_{k-1}}N_{1}(y)\not\subseteq N_{1}(z)$. From Remark 3, for any $y\in
V_{k-1}$, $N_{1}(y)=K(O_{k-2}(y))$. It follows that $\bigcap_{y\in x\cap
V_{k-1}}N_{1}(y)=\bigcap_{y\in x\cap V_{k-1}}K(O_{k-2}(y))$ and we also have
$\bigcap_{y\in x\cap V_{k-1}}K(O_{k-2}(y))=\bigcap_{P\in{\cal{O}}\text{ and
}O_{k-2}\subseteq P\subseteq O_{k-1}}K(P)$, from $H_{sur}(k-1)$ and the
definition of $x$. From Lemma 2, we get $\bigcap_{P\in{\cal{O}}\text{ and
}O_{k-2}\subseteq P\subseteq O_{k-1}}K(P)=$ $K(\bigcup_{P\in{\cal{O}}\text{
and }O_{k-2}\subseteq P\subseteq O_{k-1}}P)$, which is clearly equal to
$K(O_{k-1})$. And so we have $\bigcap_{y\in x\cap
V_{k-1}}N_{1}(y)=K(O_{k-1})$. As a consequence, we obtain $\bigcap_{y\in x\cap
V_{k-1}}N_{1}(y)\not\subseteq N_{1}(z)$. Then, adding $z$ to $x\cap V_{k-1}$
would strictly decrease $\bigcap_{y\in x\cap V_{k-1}}N_{1}(y)$.

Let us now consider the case where $O_{k-2}\not\subseteq O_{k-2}(z)$. Using
recursion hypothesis $H_{N}(k-1)$, for all $y\in x\cap V_{k-1}$ we have
$N_{k-2}(y)=\\{t\in V_{k-2}\ |\ O_{k-3}(y)\subseteq O_{k-3}(t)\subseteq
O_{k-2}(y)\text{ and }(O_{1}(t),\ldots,O_{k-4}(t))=(O_{1},\ldots,O_{k-4})\\}$.
Let us denote $Z=\\{t\in V_{k-2}\ |\ \bigcup_{y\in x\cap
V_{k-1}}O_{k-3}(y)\subseteq O_{k-3}(t)\subseteq\bigcap_{y\in x\cap
V_{k-1}}O_{k-2}(y)\text{ and }(O_{1}(t),\ldots,$
$O_{k-4}(t))=(O_{1},\ldots,O_{k-4})\\}$ (as usual, we use the convention
$(O_{1},\ldots,O_{k-4})=()$ when $k=4$). We show that $\bigcap_{y\in x\cap
V_{k-1}}N_{k-2}(y)=Z$. Let $t\in\bigcap_{y\in x\cap V_{k-1}}N_{k-2}(y)$, then
for all $y\in x\cap V_{k-1}$, $O_{k-3}(y)\subseteq O_{k-3}(t)\subseteq
O_{k-2}(y)$ and so $\bigcup_{y\in x\cap V_{k-1}}O_{k-3}(y)\subseteq
O_{k-3}(t)\subseteq\bigcap_{y\in x\cap V_{k-1}}O_{k-2}(y)$, that is $t\in Z$.
Conversely, if $t\in Z$ then we have $\bigcup_{y\in x\cap
V_{k-1}}O_{k-3}(y)\subseteq O_{k-3}(t)\subseteq\bigcap_{y\in x\cap
V_{k-1}}O_{k-2}(y)$ and so $O_{k-3}(y)\subseteq O_{k-3}(t)\subseteq
O_{k-2}(y)$ for all $y\in x\cap V_{k-1}$, that is $t\in\bigcap_{y\in x\cap
V_{k-1}}N_{k-2}(y)$. Thus, $\bigcap_{y\in x\cap V_{k-1}}N_{k-2}(y)$ $=Z$. By
definition, for all $y\in x\cap V_{k-1}$, $O_{k-3}(y)=O_{k-3}$ and
$O_{k-2}\subseteq O_{k-2}(y)$. It follows that $\bigcup_{y\in x\cap
V_{k-1}}O_{k-3}(y)=O_{k-3}$ and $O_{k-2}\subseteq\bigcap_{y\in x\cap
V_{k-1}}O_{k-2}(y)$. Moreover, from recursion hypothesis $H_{sur}$, there
exists $t^{\prime}\in V_{k-2}$ such that $O_{k-3}(t^{\prime})=O_{k-2}$ and
$(O_{1}(t^{\prime}),\ldots,O_{k-4}(t^{\prime}))=(O_{1},\ldots,O_{k-4})$. From
what precedes, since $O_{k-3}\subseteq O_{k-2}\subseteq\bigcap_{y\in x\cap
V_{k-1}}O_{k-2}(y)$, then $t^{\prime}\in Z$. On the other hand, from recursion
hypothesis $H_{N}(k-1)$, we have $N_{k-2}(z)=\\{t\in V_{k-2}\ |\
O_{k-3}\subseteq O_{k-3}(t)\subseteq O_{k-2}(z)\text{ and }(O_{1}(t),\ldots,$
$O_{k-4}(t))=(O_{1},\ldots,O_{k-4})\\}$. And since $O_{k-2}\not\subseteq
O_{k-2}(z)$, it follows that $t^{\prime}\not\in N_{k-2}(z)$, while
$t^{\prime}\in Z=\bigcap_{y\in x\cap V_{k-1}}N_{k-2}(y)$. Thus, $\bigcap_{y\in
x\cap V_{k-1}}N_{k-2}(y)\not\subseteq N_{k-2}(z)$ and adding $z$ to $x\cap
V_{k-1}$ would strictly decrease $\bigcap_{y\in x\cap V_{k-1}}N_{k-2}(y)$.
Finally, $x$ is maximal in $V^{*}_{k}$ and is therefore an element of $V_{k}$.

In order to conclude the proof of $H_{sur}(k)$, let us now show that the
element $x$ of $V_{k}$ has the desired characterising sequence
$(O_{1},\ldots,O_{k-1})$. First, from $H_{N}(k)$, which we already proved, we
know that $(O_{1}(x),\ldots,O_{k-3}(x))=(O_{1}(y),\ldots,O_{k-3}(y))$ for any
$y\in N_{k-1}(x)$, which gives
$(O_{1}(x),\ldots,O_{k-3}(x))=(O_{1},\ldots,O_{k-3})$, from the definition of
$x=Y\bigcup_{y\in Y}N(y)$. Second, from Remark 3, we have
$K(O_{k-1}(x))=N_{1}(x)$ and we already know that $|N_{1}(x)|\geq 2$ (see
beginning of the proof of $H_{sur}(k)$). This gives $|K(O_{k-1}(x))|\geq 2$,
and as we have $|O_{1}(x)|\geq 2$ and $O_{1}(x)\subseteq\ldots\subseteq
O_{k-2}(x)\subseteq O_{k-1}(x)$, we obtain that
$O_{k-2}(x),O_{k-1}(x)\in{\cal{O}}$. Now, from $H_{N}(k)$, we know that the
couple $(O_{k-2}(x),O_{k-1}(x))$ is such that $N_{k-1}(x)=\\{y\in V_{k-1}\ |\
O_{k-2}(x)\subseteq O_{k-2}(y)\subseteq O_{k-1}(x)\text{ and
}(O_{1}(y),\ldots,O_{k-3}(y))=(O_{1},\ldots,O_{k-3})\\}$. And by definition of
$x$, the couple $(O_{k-2},O_{k-1})$ also satisfies this condition. But since
$O_{k-2},O_{k-1},O_{k-2}(x),$ $O_{k-1}(x)$ all belong to ${\cal{O}}$, then,
from recursion hypothesis $H_{sur}(k-1)$, for any
$P\in\\{O_{k-2},O_{k-1},O_{k-2}(x),O_{k-1}(x)\\}$ there exists $y\in V_{k-1}$
such that $S(y)=(O_{1},\ldots,$ $O_{k-3},P)$. Then, for $P=O_{k-1}$, using the
definition of $N_{k-1}(x)$ based on the couple $(O_{k-2},O_{k-1})$, we obtain
that $y\in N_{k-1}(x)$, and consequently, using the definition of $N_{k-1}(x)$
based on the couple $(O_{k-2}(x),O_{k-1}(x))$, we have $O_{k-1}\subseteq
O_{k-1}(x)$. Similarly, for $P=O_{k-1}(x)$ we obtain $O_{k-1}(x)\subseteq
O_{k-1}$, and it follows that $O_{k-1}(x)=O_{k-1}$. Analogously, choosing
$P=O_{k-2}$ and then $P=O_{k-2}(x)$ shows that $O_{k-2}(x)=O_{k-2}$. Thus,
$H_{sur}(k)$ is true.

Proof of $H_{E}(k)$.

Let $k\geq 4$, and let $y_{1},y_{2}\in V_{k}$ such that
$N_{k-2}(y_{1})=N_{k-2}(y_{2})$. We will show that for all $p\in\llbracket
0,k-2\rrbracket\setminus\\{1\\},N_{p}(y_{1})=N_{p}(y_{2})$. From $H_{N}(k)$
applied to $y_{1}$ and $y_{2}$, we get:
$N_{k-2}(y_{1})=W_{k-2}(y_{1})=\\{t\in V_{k-2}\ |\
(O_{1}(t),\ldots,O_{k-4}(t))=(O_{1}(y_{1}),\ldots,O_{k-4}(y_{1}))$ $\text{ and
}O_{k-3}(y_{1})\subseteq O_{k-3}(t)\subseteq O_{k-2}(y_{1})\\}$, and
$N_{k-2}(y_{2})=W_{k-2}(y_{2})$. Since $N_{k-2}(y_{1})=N_{k-2}(y_{2})$, then
by considering a common element $t$ of these two sets (which are non empty
since $O_{k-2}(y_{1})\in{\cal{O}}$), we have
$(O_{1}(y_{1}),\ldots,O_{k-4}(y_{1}))=(O_{1}(y_{2}),\ldots,O_{k-4}(y_{2}))$
(using the usual convention on empty sequences). We now prove that
$O_{k-3}(y_{1})=O_{k-3}(y_{2})$. From recursion hypothesis $H_{sur}(k)$, we
know that there exists $t_{1}\in V_{k-2}$ such that
$S(t_{1})=(O_{1}(y_{1}),\ldots,O_{k-3}(y_{1}))$. This element $t_{1}$ is
clearly an element of $N_{k-2}(y_{1})$, and then is an element of
$N_{k-2}(y_{2})$. Then, we have $O_{k-3}(y_{2})\subseteq
O_{k-3}(t_{1})=O_{k-3}(y_{1})$. Symmetrically, by considering an element
$t_{2}\in V_{k-2}$ such that $S(t_{2})=(O_{1}(y_{2}),\ldots,O_{k-3}(y_{2}))$,
we obtain $O_{k-3}(y_{1})\subseteq O_{k-3}(y_{2})$. And finally, we have
$O_{k-3}(y_{1})=O_{k-3}(y_{2})$. Then, regardless of the value of $k\geq 4$,
we have $N_{0}(y_{1})=O_{1}(y_{1})=O_{1}(y_{2})=N_{0}(y_{2})$, which is enough
to prove $H_{E}(k)$ when $k=4$. Let us complete the general case where $k\geq
5$ by considering some $p\in\llbracket 2,k-3\rrbracket$ and showing that
$N_{p}(y_{1})=N_{p}(y_{2})$. From recursion hypothesis $H_{N}(k)$, we have
$N_{p}(y_{1})=\\{t\in V_{p}\ |\
(O_{1}(t),\ldots,O_{p-2}(t))=(O_{1}(y_{1}),\ldots,O_{p-2}(y_{1}))\text{ and
}O_{p-1}(y_{1})\subseteq O_{p-1}(t)\subseteq O_{p}(y_{1})\\}$. And since
$p\leq k-3$,
$(O_{1}(y_{1}),\ldots,O_{p}(y_{1}))=(O_{1}(y_{2}),\ldots,O_{p}(y_{2}))$, which
implies $N_{p}(y_{1})=N_{p}(y_{2})$. Thus, for all $p\in\llbracket
0,k-2\rrbracket\setminus\\{1\\},N_{p}(y_{1})=N_{p}(y_{2})$.

This shows that $H_{E}(k)$ is true, which ends the recursion step and the
proof of Theorem 1.

$\blacksquare$

The termination of the series directly follows from the bijection theorem
(Theorem 1 above) between the vertices of the multipartite graph and the
chains of ${\cal{L}}$.

######  Theorem 2 (Termination theorem)

For any graph $G$, the clean-factor series $(G_{i})_{i\geq 1}$ generated by
$G$ terminates.

Proof: Theorem 1 states that the characterising sequence
$(O_{1}(x),\ldots,O_{k-1}(x))$ of any node $x$ at level $k$ is such that
$O_{1}(x)\subsetneq\ldots\subsetneq O_{k-1}(x)$. The strict inclusions imply
that the length of the characterising sequence, which is equal to $k-1$,
cannot exceed $h+1$, where $h$ is the height of ${\cal{L}}$. Since $h\leq
n-2$, necessarily $V_{n+1}$ is empty. It follows that the clean-factor series
terminates and that the multipartite graph on which it terminates has at most
$n+1$ levels, that is the upper level has index at most $n$. $\blacksquare$

In our definition of the clean-factor series, the first bipartite graph of the
series is always the vertex-clique-incidence bipartite graph of some graph. It
is worth to note that our result of termination is actually more general: the
iteration of the clean-factor operator starting from an arbitrary bipartite
graph always terminates too.

###### Corollary 1

For any bipartite graph $H$, the series of multipartite graphs obtained by
iteratively applying the clean-factor operator starting from $H$ terminates.

Proof: Let $H=(V_{0},V_{1},E)$ be an arbitrary bipartite graph. Now, consider
the vertex-clique-incidence bipartite graph
$H^{\prime}=(V^{\prime}_{0},V_{1},E^{\prime})$ built from $H$ in the following
way: for each vertex $y\in V_{1}$, add a particularising vertex $x\in
V^{\prime}_{0}$ linked only to $y$. Then, in $H^{\prime}$, the sets of
neighbours on $V^{\prime}_{0}$ of vertices of $V_{1}$ are not pairwise
included and it follows that $H^{\prime}$ is the vertex-clique-incidence
bipartite graph of some graph666Graph $G^{\prime}$ is simply the graph whose
vertex set is $V^{\prime}_{0}$ and whose maximal cliques are the
neighbourhoods in $H^{\prime}$ of the vertices of $V_{1}$. $G^{\prime}$.
Moreover, since the vertices we added on level $V^{\prime}_{0}$ are included
in only one maximal clique of $G^{\prime}$, then the vertices at level $V_{2}$
in the clean-factor graph of $H$ and $H^{\prime}$ are the same and have the
same neighbourhoods. And this holds for all other levels of the series as
well: from level $V_{1}$ and above, the series of $H^{\prime}$ is identical to
the one of $H$. And since from Theorem 2, the series of $H^{\prime}$
terminates, so does the series of $H$. $\blacksquare$

##  4 Practical utility of the model

In addition to the theoretic questions we addressed, our work was motivated by
designing a model of complex networks that, while remaining very general,
encompass both the local density and the heterogeneous degree distribution of
those graphs encountered in practice. In this section, we emphasise on the
fact that our modelling object, the multipartite graph on which the clean
factor series terminates, which we call the _clean-factor decomposition_ , is
suitable for practical use, with regard to size and time of computation. This
allowed us to compute the clean-factor decomposition of very large graphs
having hundreds of thousands of vertices and millions of edges. These
practical results are not presented here since they are far beyond the scope
of this work. But, in the following, we give theoretic evidence of why the
clean-factor decomposition is a suitable model to manipulate large real-world
instances of graphs, based on common properties of those graphs.

The size of the multipartite graph $M$ obtained at termination of the clean-
factor series can be exponential in theory, as the number of maximal cliques
itself may be exponential. But in practice, its size is quite reasonable and
it can be computed efficiently. Indeed, the size of $M$ mainly depends on the
complexity of imbrication of maximal cliques, namely on the number of chains
of ${\cal{L}}$ (Theorem 1). Theorem 3 below shows that under reasonable
hypotheses, this number is linearly bounded and the size of $M$ only linearly
depends on the number of vertices of $G$.

It must be clear that our hypotheses imply that the number of maximal cliques
of $G$ is linearly bounded, as the vertices on level $V_{1}$ of $M$ are
precisely the maximal cliques of $G$. But on the other hand, note that this
bound on the number of maximal cliques is not sufficient to guarantee a
polynomial bound on the number of vertices of $M$: there may still be an
exponential number of vertices on the upper levels of $M$. Theorem 3 below
shows that this does not happen under our hypotheses.

###### Theorem 3

If every vertex of $G$ is involved in at most $k$ maximal cliques and if every
maximal clique of $G$ contains at most $c$ vertices, then we have

$|V(M)|\leq min(k\,2^{c}\,c!\,,2^{k}\,k!+1)\times n$

Proof: Thanks to Theorem 1, we obtain an upper bound on $|V(M)|$ by bounding
the number of strictly increasing sequences of the form $(O_{1},\ldots,O_{i})$
such that $O_{1},\ldots,O_{i-1}\in{\cal{O}}$.

First, we use the fact that all such sequences are sub-sequences of those
obtained starting from a clique $O_{i}$ and recursively removing one vertex at
each step until one obtains a pair $O_{1}$. The number of such sequences
starting with a fixed clique is at most the number of orders on the $c$
vertices of the clique, that is $c!$. And the number of sub-sequences of a
sequence of length $c$ is $2^{c}$. Finally, since each vertex is included in
at most $k$ maximal cliques, the number of maximal cliques is at most $k\,n$.
Then, there are at most $k\,2^{c}\,c!\,n$ increasing sequences made of
elements of ${\cal{O}}$, which are in bijection with the vertices of $M$ of
level at least $2$. Moreover, note that our counting also includes the
sequences made of one single maximal clique of $G$ and the sequences made of
one single set ${\cal{O}}$ which is a singleton. Those particular sequences
are in bijection with the vertices of $M$ at level $1$ and $0$ respectively.
Then, we obtain $|V(M)|\leq k\,2^{c}\,c!\,n$.

Clearly, since ${\cal{O}}\subseteq{\cal{O}}^{\prime}$, the number of strictly
increasing sequences made of elements of ${\cal{O}}$ is at most the number of
strictly increasing sequences made of elements of ${\cal{O}}^{\prime}$.
Another way to count those latter sequences is to count those starting with a
fixed minimal set $O_{min}\in{\cal{O}}^{\prime}\setminus\\{\varnothing\\}$.
Since ${\cal{O}}^{\prime}$ is closed under intersection, minimal elements of
${\cal{O}}^{\prime}\setminus\\{\varnothing\\}$ are pairwise disjoint and
therefore their number is at most $n$. The sequences having $O_{min}$ as first
set can be formed by starting from a clique containing $O_{min}$ and
iteratively intersecting it with another clique containing $O_{min}$. By
hypothesis, there are at most $k$ cliques containing a given $O_{min}$, and
therefore $k!$ orders on these $k$ cliques. Each order gives rise to a
sequence of elements of ${\cal{O}}^{\prime}$, which contains $2^{k}$ sub-
sequences. Thus, there are at most $k!\,2^{k}$ strictly decreasing sequences
of elements of ${\cal{O}}^{\prime}$ having $O_{min}$ as first element. Note
that the counting we made actually also comprises the sequences made of one
single maximal clique of $G$. Consequently, the number of vertices in $M$ at
level at least $1$ is at most $k!\,2^{k}\,n$, and adding the $n$ vertices at
level $0$ to this count we obtain the bound $|V(M)|\leq(2^{k}\,k!+1)\times n$,
which completes the proof. $\blacksquare$

In practice, parameters $k$ and $c$ are quite small, as they are often
constrained by the context where the graphs come from (e.g. social networks,
computer networks, citation networks) independently from the size of the
graph. Then, the size of $M$ is reasonable in practice, namely $O(n)$ for
class of graphs where $k$ and $c$ are bounded. An important consequence is
that for those graphs it is possible to compute $M$ in low polynomial time.
For example, under those hypotheses, the algorithm of [29] enumerates all
maximal cliques of graph $G$ in linear time with regard to the number of
maximal cliques, that is $O(n)$ time in this case. Moreover, [11] shows that,
for general bipartite graphs on $|B|$ vertices, it is possible to enumerate
their maximal bicliques in $O(|B|^{2})$ time per biclique (see also [2] for a
survey on maximal bicliques enumeration). In the computation of $M$, at any
stage we have to compute the maximal bicliques of the bipartite graph between
the uppermost level and the rest of the levels. Since, from Theorem 3, under
our hypotheses, the size of $M$ is $O(n)$, then the time needed to compute one
maximal biclique is $O(n^{2})$. And as we need to compute at most $O(n)$
bicliques along the algorithm, it follows that the total time spent by the
algorithm for computing the maximal bicliques involved in the construction of
$M$ is $O(n^{3})$. Finally, as the rest of the treatments needed for the
construction of $M$ can be achieved in polynomial time, it turns out that,
under the hypotheses of Theorem 3, $M$ can be computed in polynomial time.

These facts explain that, in practice, using as black boxes the implementation
[26] of [25]’s algorithm for enumeration of maximal cliques and the
implementation [27] of [28]’s algorithm for enumeration of maximal bicliques,
we could compute the clean-factor decomposition of graphs with thousands and
even hundred of thousands of nodes. Indeed, we did so for a protein
interaction network of $1\,458$ vertices and $1\,948$ edges, a movie actors
network of $392\,340$ vertices and $15\,038\,083$ edges, and a piece of the
world-wide-web graph of $325\,740$ nodes and $1\,090\,108$ edges (all can be
found at [3]).

This shows that, even though the problem of computing the maximal cliques and
bicliques is NP-hard for arbitrary graphs, for graphs encountered in practice,
since this computation can be done in polynomial time (under the hypotheses of
Theorem 3), it is possible to efficiently compute the clean-factor series.
This makes the clean-factor model a very promising tool for modelling complex
networks.

##  5 Conclusion

In this paper, we studied the termination of the weak-factor operator, which
is a multipartite graph operator appeared in the context of complex network
modelling. One key issue in this context is that the series obtained by
iteratively applying the operator terminates, as this is mandatory in order to
obtain an object suitable for modelling. Since the weak-factor series does not
always terminate, we designed a refinement of this operator, called the clean-
factor graph, whose series terminates for all input graphs. And we showed that
this modelling approach is practically efficient in the sense that the clean-
factor series can be computed even for large graphs, under reasonable
assumptions on their structure.

The first question arising from our work is to find minimal restrictions of
the weak-factor operator that guarantee termination for all graphs. Indeed, it
is crucial in practice to introduce constraints as light as possible, since
those constraints, that have to be respected during the random generation
process, makes this process more intricate to design and less efficient. In
particular we ask whether the condition requiring equality of the
neighbourhoods at level $V_{k-3}$ in the definition of the clean-factor graph
can be replaced by a condition requiring only that these neighbourhoods share
at least two common vertices.

Moreover, the use of multipartite graphs as models of complex networks, in the
spirit of the bipartite decomposition [14, 15], asks for some other important
questions. In this context, the key issue is to generate a random multipartite
graph while preserving the properties of the original graph. To do so, one has
to express the properties to preserve as functions of basic multipartite
properties (like degrees, for instance) and to generate random multipartite
graphs satisfying these properties. This is a very promising direction for
complex network modelling, but much remains to be done.

Acknowledgements. We warmly thank Thanh Qui Nguyen and The Hung Tran for
helpful discussions on the subject, as well as Clémence Magnien and Stéphan
Thomassé for their comments on the writing of the article.

## References

  * [1] R. Albert and A.-L. Barabási.  Statistical mechanics of complex networks.  Reviews of Modern Physics, 74, 47, 2002.
  * [2] Gabriela Alexe, Sorin Alexe, Yves Crama, Stephan Foldes, Peter L. Hammer, and Bruno Simeone.  Consensus algorithms for the generation of all maximal bicliques.  Discrete Applied Mathematics, 145(1):11–21, 2004.
  * [3] Albert-László Barabási and Zoltán Toroczkai.  Ccnr network databases.  http://nd.edu/ networks/resources.htm, 2007.
  * [4] A. Barrat, M. Barthélemy, and A. Vespignani.  Dynamical processes on complex networks.  Cambridge University Press, 2010.
  * [5] Edward A Bender and E.Rodney Canfield.  The asymptotic number of labeled graphs with given degree sequences.  Journal of Combinatorial Theory, Series A, 24(3):296 – 307, 1978\.
  * [6] Claudson F. Bornstein and Jayme L. Szwarcfiter.  On clique convergent graphs.  Graphs and Combinatorics, 11(3):213–220, 1995.
  * [7] Márcia R. Cerioli.  Clique graphs and edge-clique graphs.  Electronic Notes in Discrete Mathematics, 13:34 – 37, 2003.  2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization.
  * [8] Gary Chartrand, S. F. Kapoor, Terry A. McKee, and Farrokh Saba.  Edge-clique graphs.  Graphs and Combinatorics, 7(3):253–264, 1991.
  * [9] Christophe Crespelle, Thi Ha Duong Phan, and The Hung Tran.  Termination of the iterated strong-factor operator on multipartite graphs.  Submitted, 2013.
  * [10] T.S. Evans.  Clique graphs and overlapping communities.  Journal of Statistical Mechanics: Theory and Experiment, 2010(12):P12037, 2010.
  * [11] Alain Gély, Lhouari Nourine, and Bachir Sadi.  Enumeration aspects of maximal cliques and bicliques.  Discrete Applied Mathematics, 157(7):1447–1459, 2009.
  * [12] Marina Groshaus and Leandro P. Montero.  The number of convergent graphs under the biclique operator with no twin vertices is finite.  Electronic Notes in Discrete Mathematics, 35:241–246, 2009.
  * [13] Marina Groshaus and Leandro P. Montero.  On the iterated biclique operator.  Journal of Graph Theory, 73(2):181–190, 2013.
  * [14] Jean-Loup Guillaume and Matthieu Latapy.  Bipartite structure of all complex networks.  Information Processing Letters (IPL), 90(5):215–221, 2004.
  * [15] Jean-Loup Guillaume and Matthieu Latapy.  Bipartite graphs as models of complex networks.  Physica A, 371:795–813, 2006.
  * [16] F. Larrión, V. Neumann-Lara, and M. A. Pizaña.  Clique divergent clockwork graphs and partial orders.  Discrete Appl. Math., 141:195–207, May 2004.
  * [17] Francisco Larrión, Célia Picinin de Mello, Aurora Morgana, Victor Neumann-Lara, and Miguel A. Pizaña.  The clique operator on cographs and serial graphs.  Discrete Mathematics, 282(1-3):183–191, 2004.
  * [18] Francisco Larrión, Miguel A. Pizaña, and R. Villarroel-Flores.  Contractibility and the clique graph operator.  Discrete Mathematics, 308(16):3461–3469, 2008.
  * [19] Matthieu Latapy, Thi Ha Duong Phan, Christophe Crespelle, and Thanh Qui Nguyen.  Termination of multipartite graph series arising from complex network modelling.  In 4th International Conference on Combinatorial Optimization and Applications - COCOA’10, volume 6508 (Part I) of Lecture Notes in Computer Science, pages 1–10, 2010.
  * [20] Min Chih Lin, Francisco J. Soulignac, and Jayme L. Szwarcfiter.  The clique operator on circular-arc graphs.  Discrete Appl. Math., 158:1259–1267, June 2010.
  * [21] M. Molloy and B. Reed.  A critical point for random graphs with a given degree sequence.  Random Structures and Algorithms, 1995.
  * [22] V. Neumann-Lara.  On clique-divergent graphs.  In Problèmes Combin. Théorie Graphes (Colloques internationaux du C.N.R.S., Paris) 260, pages 313–315, 1978.
  * [23] Erich Prisner.  Convergence of iterated clique graphs.  Discrete Mathematics, 103(2):199 – 207, 1992.
  * [24] J. L. Szwarcfiter.  A survey on clique graphs.  In Jonathan M. Borwein, Peter Borwein, Bruce A. Reed, and Cláudia L. Sales, editors, Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, pages 109–136. Springer New York, 2003.
  * [25] Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi.  The worst-case time complexity for generating all maximal cliques and computational experiments.  Theor. Comput. Sci., 363(1):28–42, 2006.
  * [26] Takeaki Uno.  Implementation of Tomita et al.’s algorithm.  http://research.nii.ac.jp/ uno/code/macego10.zip, 2010.
  * [27] Takeaki Uno, Tatsuya Asai, Yuzo Uchida, and Hiroki Arimura.  Lcm program (linear time closed itemset miner).  http://research.nii.ac.jp/ uno/codes.htm.
  * [28] Takeaki Uno, Tatsuya Asai, Yuzo Uchida, and Hiroki Arimura.  An efficient algorithm for enumerating closed patterns in transaction databases.  In Discovery Science, 7th International Conference, volume 3245 of Lecture Notes in Computer Science, pages 16–31, 2004.
  * [29] Li Wan, Bin Wu, Nan Du, Qi Ye, and Ping Chen.  A new algorithm for enumerating all maximal cliques in complex network.  In Advanced Data Mining and Applications, Second International Conference - ADMA’06, volume 4093 of Lecture Notes in Computer Science, pages 606–617, 2006.
  * [30] D. Watts and S. Strogatz.  Collective dynamics of small-world networks.  Nature, 393:440–442, 1998.