Word-Representability of Graphs
with respect to Split Recomposition

Tithi Dwary
K. V. Krishna

Tithi Dwary K. V. Krishna

Institute of Technology Guwahati, Guwahati, India,

In this work, we show that the class of word-representable graphs is closed under split recomposition and determine the representation number of the graph obtained by recomposing two word-representable graphs. Accordingly, we show that the class of parity graphs is word-representable. Further, we obtain a characteristic property by which the recomposition of comparability graphs is a comparability graph. Consequently, we also establish the permutation-representation number (prn) of the resulting comparability graph. We also introduce a subclass of comparability graphs, called prn-irreducible graphs. We provide a criterion such that the split recomposition of two prn-irreducible graphs is a comparability graph and determine the prn of the resultant graph.

§ INTRODUCTION

A simple graph is called a word-representable graph if there is a word over its vertices such that any two vertices are adjacent in the graph if and only if they alternate in the word.  The class of word-representable graphs is an interesting class not only from graph theoretical point of view but also from algebraic and computational view points. Sergey Kitaev and Steven Seif first studied this class of graphs in the context of  Perkin semigroups [26]. The monograph [24] introduces word-representable graphs, surveys seminal contributions, and provides their connections to other contexts. The class of graphs which admit transitive orientations, known as comparability graphs, is an important subclass of word-representable graphs. This class has a special feature that they can be represented by a concatenation of permutations on their vertices, called permutationally representable graphs. In fact, the class of comparability graphs is precisely the class of permutationally representable graphs [26]. Every comparability graph induces a poset based on one of its transitive orientations.

A word-representable graph is said to be $k$-word-representable if it is represented by a word in which every letter appears exactly $k$ times. The smallest $k$ such that a graph is $k$-word-representable is said to be the representation number of the graph. Similarly, the smallest number $k$ such that a comparability graph is represented by a concatenation of $k$ permutations on its vertices is called the permutation-representation number (prn) of the comparability graph. The prn of a comparability graph is precisely the dimension of the induced poset [28]. The class of graphs with representation number at most two is characterized as the class of circle graphs ([19]) and that with prn at most two is the class of permutation graphs (cf. [27]). While there are no characterizations for the class of graphs with any of these numbers more than two, it is known that the general problems of determining the representation number of a word-representable graph, and the prn of a comparability graph are computationally hard [19, 36].

The concepts of split recomposition,  and its inverse operation, viz., split decomposition,  were introduced by Cunningham in [8, 9]. The split decomposition can be seen as a generalization of modular decomposition introduced by Gallai in [14]. The literature has several variants of split decomposition and recomposition, which include $1$-join composition [11]. In this paper, we use the version defined by Bouchet [5]. These concepts have a large range of applications including NP-hard optimization [30, 31] and the recognition of certain classes of graphs such as distance-hereditary graphs [15, 17], circle graphs [4, 13, 33], and parity graphs [6, 10]. The class of distance-hereditary graphs is characterized in terms of split components [5, 20, 22]. Further, it was shown in [5] that the distance-hereditary graphs are $2$-word-representable graphs.  In [4], through split decomposition and recomposition, 2-uniform words were constructed for recognizing circle graphs. In [1], split decomposition is used to give a full enumeration of some graph classes viz., plotemic, block, and various cactus graphs, and also to provide forbidden subgraph characterizations of certain graph classes.  The class of perfect graphs[A graph $G$ is said to be a perfect graph if for every induced subgraph $H$ of $G$, the chromatic number of $H$ is equal to the size of a largest clique in $H$.] has both word-representable graphs as well as non-word-representable graphs [24]. However, there is no characterization available for word-representable perfect graphs. It was shown in [2] that the class of perfect graphs is closed under split recomposition.

In this paper, our focus is on exploring the word-representability of graphs with respect to split recomposition. In Section 3, we show that the class of word-representable graphs is closed under split recomposition and also determine the representation number of the resulting graph obtained by recomposing two word-representable graphs. Accordingly, we establish the word-representability of a subclass of perfect graphs, known as parity graphs. The class of parity graphs includes both bipartite graphs and distance-hereditary graphs. While the class of comparability graphs is not closed under split recomposition, in Section 4, we obtain a characteristic property by which the recomposition of comparability graphs is a comparability graph. Consequently, we establish the prn of the resulting comparability graph. In this connection, we also investigate the prn of a graph obtained by connecting two graphs by an edge between specified vertices. In Section 5, we introduce a subclass of comparability graphs, which we call prn-irreducible graphs, and study their split recomposition. We provide a criteria such that the split recomposition of two prn-irreducible graphs is a comparability graph and accordingly determine the prn of the resultant graph.  We also observe that the split recomposition of prn-irreducible graphs is not prn-irreducible.

§ PRELIMINARIES

This section provides the necessary background material on word-representable graphs, posets and split decomposition. For more details, one may refer to [8, 24, 34].

A word over a finite set of letters is a finite sequence written by juxtaposing the letters of the sequence. A subword $u$ of a word $w$ is a subsequence of the sequence $w$, denoted by $u \preceq w$. For instance, $baabb \preceq aabbaaabb$. Let $w$ be a word over $A$ and $B$ be a subset of $A$. We write $w_B$ to denote the subword of $w$ that precisely consists of all occurrences of the letters of $B$. For example, if $w=baabdca$, then $w_{\{a, b\}} = baaba$. We say that the letters $a$ and $b$ alternate in $w$ if $w_{\{a, b\}}$ is either of the form $abababa\cdots$ or $bababab\cdots$ which can be of even or odd length. A word $w$ is called $k$-uniform if every letter occurs exactly $k$ times in $w$. A $1$-uniform word $w$ is a permutation on the set of letters of $w$. We say a word $u$ is a factor of a word $w$ if $w = xuy$ for some words $x$ and $y$, possibly empty words.

In this paper, we consider only simple (i.e., without loops or parallel edges) and connected graphs. A graph $G = (V, E)$, where $V$ is a set of vertices and $E$ is the set of edges, is called a word-representable graph if there is a word $w$ with the symbols of $V$ such that, for all $a, b \in V$, $a$ and $b$ are adjacent in $G$ if and only if $a$ and $b$ alternate in $w$. A word-representable graph $G$ is said to be $k$-word-representable if a $k$-uniform word represents it. It is known that every word-representable graph is $k$-word-representable, for some $k$ [25]. The smallest number $k$ such that a graph $G$ is $k$-word-representable is called the representation number of $G$, denoted by $\mathcal{R}(G)$.

A word-representable graph $G$ is said to be permutationally representable if it can be represented by a concatenation of some number of permutations on the vertices of $G$. If $G$ is represented by $p_1p_2 \cdots p_k$, where each $p_i$ is a permutation on the vertices of $G$, then we say $G$ is a permutationally $k$-representable graph. The permutation-representation number (in short prn) of $G$, denoted by $\mathcal{R}^p(G)$, is the smallest number $k$ such that $G$ is permutationally $k$-representable. It is clear that $\mathcal{R}(G) \le \mathcal{R}^p(G)$. Note that for the complete graph $K_n$ on $n$ vertices, $\mathcal{R}^p(K_n) = 1 = \mathcal{R}(K_n)$. The class of word-representable graphs as well as the class of comparability graphs are hereditary with respect to the induced subgraphs (cf. [24]). Moreover, if $H$ is an induced subgraph of a word-representable graph $G$, then $\mathcal{R}(H) \le \mathcal{R}(G)$; further, if $G$ is a comparability graph, then $\mathcal{R}^p(H) \le \mathcal{R}^p(G)$.

To distinguish between two-letter words and edges of graphs, we write $\overline{ab}$ to denote an undirected edge between vertices $a$ and $b$. A directed edge from $a$ to $b$ is denoted by $\overrightarrow{ab}$. An orientation of a graph is an assignment of direction to each edge so that the resulting graph is a directed graph. A vertex $a$ of a graph is said to be a source with respect to an orientation, if the in-degree of $a$ is zero. Similarly, if the out-degree of $a$ is zero, then $a$ is called a sink with respect to the orientation. Note that a source with respect to an orientation of a graph can be seen as a sink with respect to the orientation obtained by reversing the direction of each edge, and vice versa. An orientation of a graph $G = (V, E)$ is said to be a transitive orientation if $\overrightarrow{ab}$ and $\overrightarrow{bc}$, then $\overrightarrow{ac}$ with respect to the orientation, for all $a, b, c \in V$. If a graph admits a transitive orientation, then it is called a comparability graph. It is known that a graph is permutationally representable if and only if it is a comparability graph [26].

A set $P$ with a partial order, say $<$ on $P$, is called a partially ordered set or simply a poset. Two elements $a, b \in P$ are said to be comparable if $a < b$ or $b < a$; otherwise, they are called incomparable. An element $a \in P$ is called a maximal element if there is no element $b \in P$ such that $a < b$ in $P$. Similarly, an element $a$ is called minimal in $P$, if there is no element $b$ such that $b < a$ in $P$. For every poset $P$ there is a corresponding comparability graph whose vertices are the elements of $P$ and two vertices are adjacent if and only if they are comparable in $P$. Conversely, every comparability graph $G$ induces a poset, denoted by $P_G$, based on a given transitive orientation on $G$.

We now recall the notion of the dimension of a poset from [12] and relate it with the prn of the corresponding comparability graph. A partial order on a set $P$ is said to be a linear order if any two elements are comparable. A realizer of a poset $P$ is a collection of linear orders $\{L_1, L_2, \ldots, L_k\}$ on $P$ such that for every $a, b \in P$, $a < b$ in $P$ if and only if $a < b$ in $L_i$, for all $1 \le i \le k$. The  dimension of a poset $P$, denoted by $\dim(P)$, is the smallest positive integer $k$ such that $P$ has a realizer of size $k$. It was shown in [19] that a comparability graph $G$ is permutationally $k$-representable if and only if the poset $P_G$ has dimension at most $k$. Consequently,
if $G$ is a comparability graph, then $\mathcal{R}^p(G) = k$ if and only if $\dim(P_G) = k$ (cf. [28]).

We use the following notations in this paper. Let $G = (V, E)$ be a graph. The neighborhood of a vertex $a \in V$ is denoted by $N_G(a)$, and is defined by $N_G(a) = \{b \in V \mid \overline{ab}\in E\}$. For $A \subseteq V$, the neighborhood of $A$, $N_G(A) = \bigcup_{a \in A} N_G(a) \setminus A$. Further, the subgraph of $G$ induced by $A$ is denoted by $G[A]$.

We recall the concepts of split decomposition of a connected graph and its inverse operation, viz., split recomposition. A split of a connected graph $G = (V, E)$ is a bipartition $\{V_1, V_2\}$ of $V$ (i.e., $V = V_1 \cup V_2$ and $V_1 \cap V_2 = \emptyset$) satisfying the following: (i) $|V_1| \geq 2$ and $|V_2| \geq 2$, (ii) Each $x \in N_G(V_1)$ is adjacent to every $y \in N_G(V_2)$. If a graph has no split, then it is said to be a prime graph.

A split decomposition of a graph $G = (V, E)$ with split $\{V_1, V_2\}$  is represented as a disjoint union of the induced subgraphs $G[V_1]$ and $G[V_2]$ along with an edge $e = \overline{v_1v_2}$, where $v_1$ and $v_2$ are two new vertices such that $v_1$ and $v_2$ are adjacent to each vertices of $N_G(V_2)$  and $N_G(V_1)$, respectively. By deleting the edge $e$, we obtain two components with vertex sets $V_1 \cup \{v_1\}$ and $V_2 \cup \{v_2\}$ called the split components. The two components are then decomposed recursively to obtain a split decomposition of $G$.

Note that each split component of a graph $G$ is isomorphic to an induced subgraph of $G$ [6]. A minimal split decomposition of a graph is a split decomposition whose split components can be cliques, stars and prime graphs such that the number of split components is minimized. While there can be multiple split decompositions of a graph, a minimal split decomposition of a graph is unique [8, 9].

Let $G = (V \cup \{m\}, E)$ and $G' = (V' \cup \{m'\}, E')$ be two graphs with disjoint vertex sets. Then the split recomposition of $G$ and $G'$ with respect to the vertices $m$ and $m'$, called the marked vertices, is denoted by $G \srec G'$, and defined by $G \srec G' = (V'', E'')$, where the vertex set $V'' = V \cup V'$ and edge set $E''$ contains edges of $G[V]$, edges of $G'[V']$ and $\{\overline{ab} \mid a \in N_{G}(m), b \in N_{G'}(m')\}$.

Let $G = (V \cup \{m\}, E)$ and $G' = (V' \cup \{m'\}, E')$ be two graphs. Then $G$ and $G'$ are induced subgraphs of $G \srec G'$. For instance, if $b \in N_{G}(m)$ and $b' \in N_{G'}(m')$, then $(G \srec G')[V \cup \{b'\}]$ is isomorphic to $G$, and $G'$ is isomorphic to $(G \srec G')[V' \cup \{b\}]$.

§ WORD-REPRESENTABLE GRAPHS

As stated in the following remark, while word-representability is preserved by split decomposition, in this section, we show that split recomposition also preserves the word-representability of graphs. Consequently, we observe that the class of parity graphs is word-representable. We also relate the representation number of the graph obtained by the recomposition with its components.

If a graph $G$ is word-representable, then its split components are word-representable, as they are induced subgraphs of $G$.

If $G = (V \cup \{m\}, E)$ and $G' = (V' \cup \{m'\}, E')$ are two $k$-word-representable graphs, then so is the split recomposition $G \srec G'$.

Let $w$ and $w'$ be two $k$-uniform words representing the graphs $G$ and $G'$, respectively. In view of <cit.>, note that a cyclic shift of a $k$-uniform word representing a graph also represents the graph. Accordingly, assume $w = w_1mw_2m \cdots w_km$ and $w' = m'w'_1m'w'_2 \cdots m'w'_k$.  Note that $w_V = w_1w_2 \cdots w_k$ and $w'_{V'} = w'_1w'_2 \cdots w'_k$. Moreover, $w_V$ and $w'_{V'}$ are $k$-uniform words. We will show that the $k$-uniform word $u = w_1w'_1w_2w'_2 \cdots w_kw'_k$ represents the graph $G \srec G'$.

Note that the induced subgraphs $G[V]$ and $G'[V']$ are induced subgraphs of $G \srec G'$. Further, the $k$-uniform words $w_V$ and $w'_{V'}$ represent $G[V]$ and $G'[V']$, respectively. Accordingly, since $u_V = w_V$ and $u_{V'} = w'_{V'}$, any two vertices of $G[V]$ or of $G'[V']$ are adjacent if and only if they alternate in the word $u$.

For $a \in V$ and $b \in V'$, note that $a$ and $b$ are adjacent in $G \srec G'$ if and only if $a \in N_G(m)$ and $b \in N_{G'}(m')$. Accordingly, we consider the following cases to complete the proof.

Let $a \in N_G(m)$ and $b \in N_{G'}(m')$. Note that $w_{\{a, m\}} =\; \stackrel{k}{am\; \cdots\; am}$ (i.e., the word obtained by concatenating $am$ for $k$ times) and $w'_{\{b, m'\}} =\; \stackrel{k}{m'b\; \cdots\; m'b}$. Accordingly, for all $1 \le i \le k$, $w_i$ and $w'_i$ contain exactly one copy of $a$ and $b$, respectively. Hence, $u_{\{a, b\}} =\; \stackrel{k}{ab\; \cdots\; ab}$ so that $a$ and $b$ alternate in $u$.

Let $a \notin N_{G}(m)$. Since the $k$-uniform word $w$ represents $G$, the vertices $a$ and $m$ do not alternate in $w$. Hence, $aa$ is a substring of $w_t$, for some $t$. For any $b \in V'$, note that $b$ does not appear in $w_t$. According to the construction of $u$, the subword $u_{\{a, b\}}$ has $aa$ as a factor. Hence, $a$ and $b$ do not alternate in $u$. Similarly, when  $b \notin N_{G'}(m')$, we can observe that $b$ does not alternate with any $a \in V$.

Hence, the $k$-uniform word $u$ represents $G \srec G'$.

If $G = (V \cup \{m\}, E)$ and $G' = (V' \cup \{m'\}, E')$ are two word-representable graphs such that $\mathcal{R}(G) = k$ and $\mathcal{R}(G') = k'$, then $\mathcal{R}(G \srec G') = \max\{k, k'\}$.

Let $t = \max\{k, k'\}$. Using <cit.>, both $G$ and $G'$ are $t$-word-representable. Consequently, by Theorem <ref>,  $G \srec G'$ is $t$-word-representable so that $\mathcal{R}(G \srec G') \leq t$. But, by Remark <ref>, since $G$ and $G'$ are isomorphic to certain induced subgraphs of $G \srec G'$, we have $\mathcal{R}(G \srec G') \geq t$. Hence, $\mathcal{R}(G \srec G') = \max\{k, k'\}$.

We now summarize the characterization of word-representability of a graph with respect to its split decomposition in the following theorem.

Let $H_i$ $(1 \le i \le s)$ be the components of a split decomposition of a graph $G$. Then $G$ is word-representable if and only if $H_i$ is word-representable for all $1 \le i \le s$. Further,  $\mathcal{R}(G) = \displaystyle\max_{1 \le i \le s} \mathcal{R}(H_i)$.

In view of the fact that the class of perfect graphs is closed under split recomposition [2], we have the following corollary of Theorem <ref>. Although a characterization for word-representable perfect graphs is an open problem, this corollary may be useful in this regard.

A perfect graph is not word-representable if and only if at least one of its prime components is a non-word-representable perfect graph.

Thus, the class of prime perfect graphs that are not word-representable completely determines the class of  perfect graphs that are not word-representable.

A graph is called a parity graph if the lengths of any two induced paths between a pair of vertices are of the same parity. The class of parity graphs is a subclass of perfect graphs [32].  Recall from [6] that a graph $G$ is a parity graph if and only if every component in its minimal split decomposition is a clique or a bipartite graph.  Accordingly, since cliques and bipartite graphs are word-representable, we have the following corollary of Theorem <ref>. Thus, we establish a class of word-representable graphs within perfect graphs which includes bipartite graphs as well as distance-hereditary graphs.

The class of parity graphs is word-representable.

§ COMPARABILITY GRAPHS

In this section, we study the recomposition of comparability graphs. First we observe that the class of comparability graphs is not closed under split recomposition. In Subsection 4.1, we give a sufficient condition so that a recomposition is a comparability graph. Further, in Subsection 4.2, we investigate the prn of a recomposition of comparability graphs. Finally, in Subsection 4.3, we provide a characteristic property by which a recomposition of comparability graphs is a comparability graph.

Let $G$ be a comparability graph. Note that every split component of $G$ is a comparability graph, as it is (isomorphic) an induced subgraph of $G$. However, as shown in the following example, split recomposition of two comparability graphs is not always a comparability graph.

The graphs $G$ and $G'$ shown in Fig. <ref> are comparability graphs. However, the split recomposition $G \srec G'$ is not a comparability graph (cf. <cit.>).

\[\begin{tikzpicture}[scale=0.6]
\vertex (a_8) at (-3.4,0) [fill=black, label=below:$1$] {};
\vertex (a_7) at (-2.4,0) [fill=black, label=below:$2$] {};
\vertex (a_6) at (-1.4,0) [label=below:$m$] {};
\vertex (a_1) at (1,0) [label=below:$m'$] {};
\vertex (a_4) at (2,1.5) [fill=black, label=right:$3$] {};
\vertex (a_2) at (2,0.5) [fill=black, label=right:$4$] {};
\vertex (a_3) at (2,-0.5) [fill=black, label=right:$5$] {};
\vertex (a_5) at (2,-1.5) [fill=black, label=right:$6$] {};
\node (a_9) at (-2.4,-1.5) [label=below:$G$] {};
\node (a_{10}) at (2,-1.5) [label=below:$G'$] {};

\path
(a_1) edge (a_2)
(a_1) edge (a_3)
(a_2) edge (a_3)

(a_2) edge (a_4)
(a_3) edge (a_5)
(a_6) edge (a_7)
(a_7) edge (a_8) ;
\end{tikzpicture}\]

\[\begin{tikzpicture}[scale=0.6]
\vertex (a_1) at (-0.4,0) [fill=black,label=below:$2$] {};
\vertex (a_2) at (1,0.5) [fill=black,label=right:$4$] {};
\vertex (a_3) at (1,-0.5) [fill=black,label=right:$5$] {};
\vertex (a_4) at (1,1.5) [fill=black,label=right:$3$] {};
\vertex (a_5) at (1,-1.5) [fill=black,label=right:$6$] {};
\vertex (a_6) at (-1.4,0) [fill=black,label=below:$1$] {};
\node (a_{10}) at (-0.4,-1.5) [label=below:$G \srec G'$] {};

\path
(a_1) edge (a_2)
(a_1) edge (a_3)
(a_2) edge (a_3)
(a_1) edge (a_6)
(a_2) edge (a_4)
(a_3) edge (a_5);
\end{tikzpicture}\]

Recomposition of two comparability graphs

For the rest of the paper, let $G = (V \cup \{m\}, E)$ and $G' = (V' \cup \{m'\}, E')$ be two graphs with disjoint vertex sets. Consider the graph
$$H = (V \cup V' \cup \{m, m'\}, E \cup E' \cup \{\overline{mm'}\}),$$
which is obtained by adding the edge $\overline{mm'}$ between $G$ and $G'$. This graph operation is useful in the sequel for investigating a sufficient condition and the prn of $G \srec G'$.

§.§ Sufficient Condition

In this subsection, we give a necessary and sufficient condition for $H$ to be a comparability graph. Further, we also discuss the conditions under which the recomposition $G \srec G'$ is a comparability graph. As a consequence, we also establish that a recomposition of bipartite graphs is a bipartite graph.

The graph $H$ is a comparability graph if and only if there exist transitive orientations $T$ and $T'$ of $G$ and $G'$, respectively, such that $m$ is a source of $T$ and $m'$ is a sink of $T'$, or vice versa.

Suppose $T$ and $T'$ are transitive orientations of $G$ and $G'$, respectively, such that  $m$ is a source of $T$ and $m'$ is a sink of $T'$. We extend $T$ and $T'$ to an orientation $T_H$ of $H$ by orienting the edge $\overline{mm'}$ as $\overrightarrow{mm'}$. In case, if $m$ is a sink of $T$ and $m'$ is a source of $T'$, then assign $\overrightarrow{m'm}$ as the orientation to the edge $\overline{mm'}$ in $T_H$. In both the cases, clearly, $T_H$ is a transitive orientation of $H$ so that $H$ is a comparability graph.

Conversely, suppose $H$ is a comparability graph. Let $T_H$ be a transitive orientation of $H$ in which the edge $\overline{mm'}$ is oriented as $\overrightarrow{mm'}$. We claim that $m$ is a source and $m'$ is a sink with respect to $T_H$. On the contrary, we have the following cases:

* $m$ is not a source: Then, for some $a \in V$,  we have $\overrightarrow{am}$ in $T_H$. By transitivity of $T_H$, $\overrightarrow{am'}$ exists in $T_H$; which is a contradiction as $\overline{am'}$ is not an edge in $H$.

* $m'$ is not a sink: Then, for some $b \in V'$,  we have $\overrightarrow{m'b}$ in $T_H$. By transitivity of $T_H$, $\overrightarrow{mb}$ exists in $T_H$; which is a contradiction as $\overline{mb}$ is not an edge in $H$.

This proves our claim. Note that $H[V \cup \{m\}] = G$ and $H[V' \cup \{m'\}] = G'$. Further, let $T$ and $T'$ be the restrictions of $T_H$ to $G$ and $G'$, respectively. Clearly, $T$ and $T'$ are transitive orientations of $G$ and $G'$, respectively. Moreover, $m$ is a source of $T$ and $m'$ is a sink of $T'$.

Similarly, if the edge $\overline{mm'}$ of $H$ is oriented as $\overrightarrow{m'm}$ in $T_H$, then we can show that there exist transitive orientations $T$ and $T'$ of $G$ and $G'$, respectively, such that $m$ is a sink of $T$ and $m'$ is a source of $T'$.

We now present a condition under which a recomposition of comparability graphs is a comparability graph.

If $G$ and $G'$ are comparability graphs such that $m$ is a source of $G$ and $m'$ is a sink of $G'$ with respect to some transitive orientations of $G$ and $G'$,  then $G \srec G'$ is a comparability graph.

By Theorem <ref>, $H$ is a comparability graph in which $m$ is a source and $m'$ is a sink. In view of the discussion in <cit.>, we give a transitive orientation to $G \srec G'$ from a transitive orientation of $H$ by deleting $m$ and $m'$ and by orienting $\overrightarrow{ba}$ for all adjacent vertices $a (\neq m')$ of $m$ and $b (\neq m)$ of $m'$.

In Theorem <ref>, if $m$ is a sink and $m'$ is a source with respect to some transitive orientations of $G$ and $G'$, respectively, then also a transitive orientation can be assigned to $G \srec G'$. Hence, in the rest of the paper, we consider one of the combinations to state the corresponding results.

Since every bipartite graph is a comparability graph, we have the following corollary.

If $G$ and $G'$ are two bipartite graphs, then for any choice of vertices $m$ and $m'$, the split recomposition $G \srec G'$ is a comparability graph.

Let $\{A, B\}$ be a bipartition of $G$ and $\{A', B'\}$ be a bipartition of $G'$. Without loss of generality, suppose $m \in A$ and $m' \in A'$. Assign orientation to the edges in $E$ as $\overrightarrow{ab}$ such that $a \in A, b \in B$ and the edges in $E'$ as $\overrightarrow{b'a'}$ such that $b' \in B', a' \in A'$. In this transitive orientation, $m$ is a source and $m'$ is a sink. Hence, the result follows from Theorem <ref>.

Moreover, we have the following result for bipartite graphs.

If $G$ and $G'$ are two bipartite graphs, then for any choice of vertices $m$ and $m'$, the split recomposition $G \srec G'$ is a bipartite graph.

Let $\{A, B\}$ be a bipartition of $G$ and $\{A', B'\}$ be a bipartition of $G'$. Without loss of generality, suppose $m \in A$ and $m' \in A'$.
We prove that $\{(A \setminus \{m\}) \cup B', (A' \setminus \{m'\}) \cup B\}$ is a bipartition of the vertices of $G \srec G'$. Consider an edge $\overline{ab}$ of $G \srec G'$. Then $\overline{ab}$ is in one of the induced subgraphs $G[V]$ and $G'[V']$, or it is an edge between $N_{G}(m)$ and $N_{G'}(m')$. In any case, it can be observed that if $a \in (A \setminus \{m\}) \cup B'$ then $b \in (A' \setminus \{m'\}) \cup B$, or vice versa.

§.§ Permutation-Representation Number

In this subsection, we study the prn of the graph $H$ and obtain a partial result on the prn of $G \srec G'$. A complete result on the prn of $G \srec G'$ is given in Subsection 4.3, subsequent to its characterization.

Let $G$ be a comparability graph with a transitive orientation $T$. If $m$ is a source with respect to $T$, then $m$ is a minimal element of the induced poset $P_G$. Similarly, if $m$ is a sink, then $m$ is a maximal element of $P_G$.

Let us assume that $m$ is not a minimal element of $P_G$. Then there exists $a$ in $P_G$ such that $a < m$ in $P_G$ which implies there is an edge $\overrightarrow{am}$ in $G$ with respect to $T$. This is a contradiction to $m$ is a source. Similarly, the result can be proved when $m$ is a sink.

The following remark produces a word to represent a comparability graph based on a realizer of its induced poset.

Let $C$ be a comparability graph and $P_{C}$ be the poset induced by a  transitive orientation of $C$. Let $\{L_1, L_2, \ldots, L_k\}$ be a realizer of $P_C$. For $1 \le i \le k$, construct permutations $p_i$ from $L_i$ on the vertices of $C$ such that $a$ occurs before $b$ in the permutation $p_i$ if $a < b$ in $L_i$. Then, in view of <cit.>, the word $ p_1p_2 \cdots p_k$ represents $C$.

Let $G$ be a comparability graph such that $m$ is a source (or sink) with respect to some transitive orientation of $G$. Then there exist $k$ and permutations $p_i$ on $V$, for $1 \le i \le k$, which can be extended to permutations $q_i$ on $V \cup \{m\}$, for $1 \le i \le k+1$, such that $p_1\cdots p_k$ represents $G[V]$ and $q_1 \cdots q_kq_{k+1}$ represents $G$.

Consider the poset $P_G$ induced by the transitive orientation of $G$ for which $m$ is a source. Note that $m$ is a minimal element of $P_{G}$. Now consider the subposet of $P_{G}$ with the elements of $V$ and note that the corresponding comparability graph is $G[V]$. Accordingly, we denote the subposet by $P_{G[V]}$.

Consider a realizer $L = \{L_1, L_2, \ldots, L_k\}$ of $P_{G[V]}$. Using the construction in <cit.> (see also <cit.> and <cit.>), we extend $L$ to a realizer $M = \{M_1, M_2, \ldots, M_k, M_{k+1}\}$ of $P_{G}$ as per the following:	Let $U(m)= \{a \in V \mid a > m  \text{ in }  P_{G}\}$ and set

\begin{align*}
M_i &= m < L_i, \quad (1 \le i \le k); \\
M_{k+1} &= L_k(V \setminus U(m)) < m < L_k(U(m)),
\end{align*}

where, for $X \subseteq V$, $L_k(X)$ is the linear order on $X$ obtained from $L_k$ by restricting it to $X$.

For $1 \le i \le k$, construct permutations $p_i$ from $L_i$ such that $a$ occurs before $b$ in $p_i$ if $a < b$ in $L_i$. Similarly, for $1 \le i \le k+1$, construct permutations $q_i$  from $M_i$. Note that, as $m$ is a minimal element of $P_{G}$, we have $N_{G}(m) = U(m)$. Accordingly, note that

\begin{align*}
q_{i} &= mp_{i}, \quad(1 \le i \le k); \\
q_{k + 1} &= p_{{k}_{V \setminus N_{G}(m)}}m p_{{k}_{N_{G}(m)}}.
\end{align*}

Hence, by Remark <ref>, the words $p_1p_2 \cdots p_{k}$ and $q_1q_2 \cdots q_{k}q_{k + 1}$ represent the graphs $G[V]$ and  $G$, respectively.

Similarly, if $m$ is a sink, there exist permutations $p_i$ on $V$, for $1 \le i \le k$, and permutations $q_i$ on $V \cup \{m\}$, for $1 \le i \le k+1$, such that the words $p_1p_2 \cdots p_{k}$ and  $q_1q_2 \cdots q_{k}q_{k + 1}$ represent $G[V]$ and $G$, respectively, where the permutations $q_i$ are as per the following:

\begin{align*}
q_{i} &= p_{i}m, \quad(1 \le i \le k); \\
q_{k + 1} &= p_{{k}_{N_{G}(m)}}mp_{{k}_{V \setminus  N_{G}(m)}}.
\end{align*}

Note that $\mathcal{R}^p(G) = k$ implies $\dim(P_G) = k$ so that $\dim(P_{G[V]}) \le k$. Accordingly, Proposition <ref> is rephrased in the following lemma for the graphs $G$ and $G'$. The lemma is useful for obtaining the prn of their recomposition and also that of $H$.

Suppose $G$ and $G'$ are comparability graphs such that $m$ is a source of $G$ and $m'$ is a sink of $G'$ with respect to some transitive orientations of $G$ and $G'$. Let $\mathcal{R}^p(G) =k$ and $\mathcal{R}^p(G') =k'$. Then there exist permutations $p_i$  $(1 \le i \le k)$ on $V$, $p'_i$  $(1 \le i \le k')$ on $V'$ which can be extended to the permutations $q_i$ $(1 \le i \le k+1)$ on the vertices of $G$ and permutations $q'_i$ $(1 \le i \le k'+1)$ on the vertices of $G'$ such that the words $p_1p_2 \cdots p_{k}$ and $p'_1p'_2 \cdots p'_{k'}$ represent $G[V]$ and $G'[V']$, respectively and the words $w = q_1q_2 \cdots q_{k}q_{k + 1}$ and $w' = q'_1q'_2 \cdots q'_{k'}q'_{k' + 1}$ represent the graphs $G$ and $G'$, respectively, where

\[\begin{array}{rlrl}
q_{i} &= mp_{i}, \quad(1 \le i \le k); \quad \quad & q'_{i} &= p'_{i}m', \quad(1 \le i \le k'); \\
q_{k + 1} &= p_{{k}_{V \setminus N_{G}(m)}}m p_{{k}_{N_{G}(m)}}; \quad \quad & q'_{k' + 1} &= p'_{{k'}_{N_{G'}(m')}}m'p'_{{k'}_{V' \setminus  N_{G'}(m')}}. \\
\end{array}\]

Let $G$ and $G'$ be comparability graphs such that  $\mathcal{R}^p(G) = k$ and $\mathcal{R}^p(G') = k'$.  If the graph $H$ is a comparability graph, then $\mathcal{R}^p(H) = \max\{k, k'\}$ or $1 + \max\{k, k'\}$.

Suppose $H$ is a comparability graph. By Theorem <ref>, $m$ is a source and  $m'$ is a sink with respect to some transitive orientations of $G$ and $G'$, respectively.

As $\mathcal{R}^p(G) = k$ and $\mathcal{R}^p(G') = k'$, using Lemma <ref>, consider the permutations $p_i$ $(1 \le i \le k)$ on $V$, $p'_i$ $(1 \le i \le k')$ on $V'$, $q_i$ $(1 \le i \le k+1)$ on the vertices of $G$, and $q'_i$ $(1 \le i \le k'+1)$ on the vertices of $G'$ such that the words $w = q_1q_2 \cdots q_{k}q_{k + 1}$ and $w' = q'_1q'_2 \cdots q'_{k'}q'_{k' + 1}$ represent the graphs $G$ and $G'$, respectively.

Suppose $k' \le k$. We construct $k+1$ number of permutations $u_i$ ($1 \le i \le k+1$) on the vertices of $H$ as per the following:

\begin{align*}
u_{1} & = p'_1mp_1m', \\
u_{i} & = p'_imm'p_i, \quad(2 \le i \le k') \\
u_{j} & = p'_{k'}mm'p_{j}, \quad(k' + 1 \le j \le k) \\
u_{k + 1} & = q_{k + 1}q'_{k' + 1} \\
& =p_{{k}_{V \setminus N_{G}(m)}}m p_{{k}_{N_{G}(m)}}p'_{{k'}_{N_{G'}(m')}}m'p'_{{k'}_{V' \setminus  N_{G'}(m')}}
\end{align*}

We now show that the word $u = u_1u_2 \cdots u_{k}u_{k + 1}$ represents the graph $H$.
Note that $H[V \cup \{m\}] = G$ and $H[V' \cup \{m'\}] = G'$. Further, since

\begin{align*}
u_{V \cup \{m\}} & = q_1q_2\; \cdots \; q_kq_{k+1}, \text{and} \\
u_{V' \cup \{m'\}} & = q'_1q'_2\; \cdots \;q'_{k'-1} \overbrace{q'_{k'}\; \cdots \; q'_{k'}}^{k-k'+1}q'_{k'+1},
\end{align*}

we have $u_{V \cup \{m\}}$ and $u_{V' \cup \{m'\}}$ represent the graphs $G$ and $G'$, respectively. Hence, any two vertices of $G$ or of $G'$ are adjacent if and only if they alternate in the word $u$.
Also, corresponding to the edge $\overline{mm'}$ in $H$,  it is easy to see that $m$ and $m'$ alternate in $u$, as $mm' \preceq u_i$ for all $1 \le i \le k + 1$.

Note that there are no edges between the graphs $G$ and $G'$ except $\overline{mm'}$; accordingly, we show that the corresponding vertices do not alternate in $u$.
For $a \in V$ and $a' \in V' \cup \{m'\}$, as $a'a \preceq u_2$ but $aa' \preceq u_{k + 1}$, it is evident that $a$ and $a'$ do not alternate in $u$. Also, for $a \in V \cup \{m\}$ and $a' \in V'$, we have $a$ and $a'$ do not alternate in $u$ as $a'a \preceq u_1$ but $aa' \preceq u_{k + 1}$. Hence, the word $u$ represents the graph $H$.

Similarly, when $k \le k'$, we can show that the word $u = u_1u_2 \cdots u_{k'}u_{k' + 1}$ represents the graph $H$, where

\begin{align*}
u_{1} & = p'_1mp_1m'; \\
u_{i} & = p'_imm'p_i, \quad(2 \le i \le k); \\
u_{j} & = p'_{j}mm'p_{k}, \quad(k + 1 \le j \le k'); \\
u_{k' + 1} & = q_{k + 1}q'_{k' + 1} \\
& =p_{{k}_{V \setminus N_{G}(m)}}m p_{{k}_{N_{G}(m)}}p'_{{k'}_{N_{G'}(m')}}m'p'_{{k'}_{V' \setminus  N_{G'}(m')}}.
\end{align*}

In any case, since $u$ is a concatenation of $1 + \max\{k, k'\}$ number of permutations, we have $\mathcal{R}^p(H) \le 1 + \max\{k, k'\}$. Also, since $G$ and $G'$ are induced subgraphs of $H$, we have  $\mathcal{R}^p(H) \ge \max\{k, k'\}$. Hence, $\mathcal{R}^p(H) = \max\{k, k'\}$ or $1 + \max\{k, k'\}$.

Let $G$ and $G'$ be comparability graphs such that $m$ is a source of $G$ and $m'$ is a sink of $G'$ with respect to some transitive orientations of $G$ and $G'$. If $\mathcal{R}^p(G) = k$ and $\mathcal{R}^p(G') = k'$, then $\mathcal{R}^p(G \srec G') = \max\{k, k'\}$ or $1+ \max\{k, k'\}$.

Let us assume that  $m$ is a source of $G$ and $m'$ is a sink of $G'$ with respect to some transitive orientations of $G$ and $G'$. Then, by Theorem <ref>, $G \srec G'$ is a comparability graph and hence permutationally representable. As $\mathcal{R}^p(G) = k$ and $\mathcal{R}^p(G') = k'$, using Lemma <ref>, consider the permutations $p_i$ $(1 \le i \le k)$ on $V$, $p'_i$ $(1 \le i \le k')$ on $V'$, $q_i$ $(1 \le i \le k+1)$ on the vertices of $G$, and $q'_i$ $(1 \le i \le k'+1)$ on the vertices of $G'$ such that the words $w = q_1q_2 \cdots q_{k}q_{k + 1}$ and $w' = q'_1q'_2 \cdots q'_{k'}q'_{k' + 1}$ represent the graphs $G$ and $G'$, respectively.

Suppose $k \le k'$. We construct $k' +1 $ number of permutations $v_i$ ($1 \le i \le k' + 1$) on the vertices of $G \srec G'$ as per the following:

\begin{align*}
v_{i} & = p'_ip_i, \quad(1 \le i \le k) \\
v_{j} & = p'_jp_{k}, \quad(k + 1 \le j \le k') \\
v_{k' + 1} & = p_{{k}_{V \setminus N_{G}(m)}}p'_{{k'}_{N_{G'}(m')}}p_{{k}_{N_{G}(m)}}p'_{{k'}_{V' \setminus N_{G'}(m')}}
\end{align*}

We now show that the word $v = v_1v_2 \cdots v_{k'}v_{k'+1}$ represents the graph $G \srec G'$.	Note that $G[V]$ and $G'[V']$ are induced subgraphs of $G \srec G'$ represented by

\begin{align*}
w_{V} & =  p_1p_2 \; \cdots \; p_{k} p_{{k}_{V \setminus N_{G}(m)}}p_{{k}_{N_{G}(m)}}, \text{and} \\
w'_{V'} & = p'_1p'_2 \; \cdots \; p'_{k'}p'_{{k'}_{N_{G'}(m')}}p'_{{k'}_{V' \setminus  N_{G'}(m')}},
\end{align*}

respectively. Further, note that

\begin{align*}
v_{V} & = p_1p_2 \; \cdots \; p_{k-1} \overbrace{p_k \; \cdots \; p_k}^{k' - k +1}p_{{k}_{V \setminus N_{G}(m)}}p_{{k}_{N_{G}(m)}}, \text{and} \\
v_{V'} & = p'_1p'_2 \; \cdots \; p'_{k'}p'_{{k'}_{N_{G'}(m')}}p'_{{k'}_{V' \setminus  N_{G'}(m')}}.
\end{align*}

Thus, any two vertices of $G[V]$ or of $G'[V']$ are adjacent if and only if they alternate in the word $v$.

For $a \in V$ and $a' \in V'$, note that $a$ and $a'$ are adjacent in $G \srec G'$ if and only if $a \in N_G(m)$ and $a' \in N_{G'}(m')$. Accordingly, we consider the following cases to show that $a$ and $a'$ are adjacent in $G \srec G'$ if and only if they alternate in $v$. If $a \in N_G(m)$ and $a' \in N_{G'}(m')$, then from the construction of $v$, we have $a'a \preceq v_i$ for all $1 \le i \le k' + 1$, so that $a$ and $a'$ alternate in $v$. If $a \notin N_{G}(m)$, then for any $a' \in V'$, we have $a'a \preceq v_1$ but $aa' \preceq v_{k' + 1}$.  Similarly, if $a' \notin N_{G'}(m')$, then for any vertex $a \in V$, we have $a'a \preceq v_1$ but $aa' \preceq v_{k' + 1}$. Hence, $a$ and $a'$ do not alternate in $v$, if $a \notin N_G(m)$ or $a' \notin N_{G'}(m')$. Hence the word $v$ represents $G \srec G'$ permutationally.

Similarly, when $k' \le k$, we can show that the word $v = v_1v_2 \cdots v_kv_{k+1}$ represents the graph $G \srec G'$ permutationally, where

\begin{align*}
v_{i} & = p'_ip_i, \quad(1 \le i \le k'); \\
v_{j} & = p'_{k'}p_{j}, \quad(k' + 1 \le j \le k); \\
v_{k + 1} & = p_{{k}_{V \setminus N_{G}(m)}}p'_{{k'}_{N_{G'}(m')}}p_{{k}_{N_{G}(m)}}p'_{{k'}_{V' \setminus N_{G'}(m')}}.
\end{align*}

In any case, since $v$ is a concatenation of $1 + \max\{k, k'\}$ number of permutations, we have $\mathcal{R}^p(G \srec G') \le 1 + \max\{k, k'\}$. Also, since $G$ and $G'$ are isomorphic to certain induced subgraphs of $G \srec G'$ (cf. Remark <ref>), we have  $\mathcal{R}^p(G \srec G') \ge \max\{k, k'\}$. Hence,
$\mathcal{R}^p(G \srec G') = \max\{k, k'\}$ or $1+ \max\{k, k'\}$.

In view of Corollary <ref>, we have the following corollary of Theorem <ref>.

If $G$ and $G'$ are bipartite graphs with $\mathcal{R}^p(G) = k$ and $\mathcal{R}^p(G') = k'$,  then $\mathcal{R}^p(G \srec G') = \max\{k, k'\}$ or $1 + \max\{k, k'\}$.

§.§ Characterization

In summary, we obtained a transitive orientation for a recomposition of comparability graphs when the marked vertices are source and sink with respect to their transitive orientations. However, the marked vertices need not be source or sink to give a transitive orientation to the recomposition, as shown in the following example.

Consider the comparability graphs $G_1$ and $G_2$ given in Fig. <ref> in which $a$ and $b$ are the marked vertices. Note that $b$ is not a source or sink under any transitive orientation given to $G_2$. However, $G_1 \psrec{a}{b} G_2$ is a comparability graph.

\[\begin{tikzpicture}[scale=0.6]
\vertex (a_8) at (-2.5,0.5) [fill=black, label=above:$1$] {};
\vertex (a_7) at (-2.5,-0.5) [fill=black, label=below:$2$] {};
\vertex (a_6) at (-1.4,0) [label=below:$a$] {};
\vertex (a_1) at (1,0) [label=below:$b$] {};
\vertex (a_4) at (2,1.5) [fill=black, label=right:$3$] {};
\vertex (a_2) at (2,0.5) [fill=black, label=right:$4$] {};
\vertex (a_3) at (2,-0.5) [fill=black, label=right:$5$] {};
\vertex (a_5) at (2,-1.5) [fill=black, label=right:$6$] {};
\node (a_9) at (-2.4,-2) [label=below:$G_1$] {};
\node (a_{10}) at (2,-2) [label=below:$G_2$] {};

\path
(a_1) edge (a_2)
(a_1) edge (a_3)
(a_2) edge (a_3)

(a_2) edge (a_4)
(a_3) edge (a_5)
(a_6) edge (a_7)
(a_6) edge (a_8) ;
\end{tikzpicture}\]

\[\begin{tikzpicture}[scale=0.6]
\vertex (a_1) at (-0.4,0.5) [fill=black,label=above:$1$] {};
\vertex (a_2) at (1,0.5) [fill=black,label=right:$4$] {};
\vertex (a_3) at (1,-0.5) [fill=black,label=right:$5$] {};
\vertex (a_4) at (1,1.5) [fill=black,label=right:$3$] {};
\vertex (a_5) at (1,-1.5) [fill=black,label=right:$6$] {};
\vertex (a_6) at (-0.4,-0.5) [fill=black,label=below:$2$] {};
\node (a_{10}) at (0.3,-2) [label=below:$G_1 \psrec{a}{b} G_2$] {};

\path
(a_1) edge (a_2)
(a_1) edge (a_3)
(a_2) edge (a_3)
(a_2) edge (a_6)
(a_3) edge (a_6)
(a_2) edge (a_4)
(a_3) edge (a_5);
\end{tikzpicture}\]

Recomposition of comparability graphs

However, in Example <ref>,  the vertex $a$ is an all-adjacent vertex, i.e., $a$ is adjacent to all other vertices of $G_1$. In connection to this observation we prove the following theorem.

Let $G$ and $G'$ be two comparability graphs such that  at least one of $m$ and $m'$ is an all-adjacent vertex. Then $G \srec G'$ is a comparability graph. Moreover, if $\mathcal{R}^p(G) = k$ and $\mathcal{R}^p(G') = k'$, then $\mathcal{R}^p(G \srec G') = \max\{k, k'\}$.

We prove the result by constructing requisite number of permutations on the vertices of $G \srec G'$ whose concatenation represents $G \srec G'$.

Let the words $p_1p_2 \cdots p_k$ and $p'_1p'_2 \cdots p'_{k'}$ represent $G$ and $G'$, respectively, where each $p_i$ $(1 \leq i \leq k)$ is a permutation on the vertices of $G$ and each $p'_i$ $(1 \leq i \leq k')$ is a permutation on the vertices of $G'$.

Suppose $\max\{k, k'\} = t$. If $k' < k$, then set $p'_j = p'_{k'}$ for all $k'+ 1 \le j \le t$ and note that $p'_1p'_2 \cdots p'_t$ represents $G'$. Similarly, if $k < k'$, then set $p_j = p_{k}$ for all $k + 1 \le j \le t$ and note that $p_1p_2 \cdots p_t$ represents $G$. In any case, the words $w = p_1p_2 \cdots p_t$ and $w' = p'_1p'_2 \cdots p'_t$ represent the graphs $G$ and $G'$, respectively. For $1 \le i \le t$, let $p_i = r_ims_i$  and $p'_i = r'_im's'_i$ so that $p_{i_V} = r_is_i$ and $p'_{i_{V'}} = r'_is'_i$.

Suppose $m$ is an all-adjacent vertex of $G$. Let $u_i = r'_ir_is_is'_i$, for all $1 \le i \le t$. Note that each $u_i$ is a permutation on the vertices of $G \srec G'$.  We show that the word $u = u_1u_2 \cdots u_t$  represents the graph $G \srec G'$ permutationally.

Note that the induced subgraphs $G[V]$ and $G'[V']$ are induced subgraphs of $G \srec G'$. Further, since $u_{V} = p_{1_V}p_{2_V} \cdots p_{t_V} = w_{V}$ and $u_{V'} = p'_{1_{V'}}p'_{2_{V'}} \cdots p'_{{t}_{V'}} = w'_{V'}$, the subwords $u_{V}$ and $u_{V'}$ of $u$ represent the graphs $G[V]$ and $G'[V']$, respectively. Thus, any two vertices of $G[V]$ or of $G'[V']$ are adjacent if and only if they alternate in the word $u$.

For $a \in V$ and $a' \in V'$, note that $a$ and $a'$ are adjacent in $G \srec G'$ if and only if $a \in N_G(m)$ and $a' \in N_{G'}(m')$. However, note that $V = N_{G}(m)$ as $m$ is an all-adjacent vertex of $G$.  Accordingly, we consider the two cases based on $a' \in N_{G'}(m')$ or not to show that $a$ and $a'$ are adjacent in $G \srec G'$ if and only if they alternate in $u$ so that $u$ represents the graph $G \srec G'$.

* Case-1: $a' \in N_{G'}(m')$. Since $w'$ represents $G'$, we have $a'm' \preceq p'_i$ for all $i$, or $m'a' \preceq p'_i$ for all $i$, $1 \le i \le t$. Observe that each $u_i$ ($1 \le i \le t$) is constructed from $p'_i$ by replacing $m'$ with the permutation $p_{i_V}$. Hence, if $a'm' \preceq p'_i$ for all $i$, then $a'a \preceq u_i$ for all $i$. If $m'a' \preceq p'_i$ for all $i$, then $aa' \preceq u_i$ for all $i$. In any case, $a$ and $a'$ alternate in $u$.

* Case-2: $a' \notin N_{G'}(m')$. Then $a'$ and $m'$ do not alternate in $w'$. Accordingly, there exist $i$ and $j$ $(1 \le i, j \le t)$ such that $a'm' \preceq p'_i$ and $m'a' \preceq p'_j$. Again, as per the construction of $u_i$ and $u_j$, we have $a'a \preceq u_i$ and $aa' \preceq u_j$. Hence, $a$ and $a'$ do not alternate in $u$.

Similarly, if $m'$ is an all-adjacent vertex of $G'$, we can show that the word $u = u_1u_2 \cdots u_t$ represents the graph $G \srec G'$ permutationally, where $u_i = r_ir'_is'_is_i$, for $1 \le i \le t$.

Therefore, we have $\mathcal{R}^p(G \srec G') \le t = \max\{k, k'\}$. But, by Remark <ref>, since $G$ and $G'$ are isomorphic to certain induced subgraphs of $G \srec G'$, we have $\mathcal{R}^p(G \srec G') \geq t$. Hence, $\mathcal{R}^p(G \srec G') = \max\{k, k'\}$.

We now recall a theorem that characterizes a source of a comparability graph using a graph that is constructed as follows. Let $v$ be a vertex of a graph $C$ and $C^v$ be the graph obtained from $C$ by adding a new vertex $v^\prime$ adjacent only to the vertex $v$ of $C$. Then we have the following theorem.

Let $C$ be a comparability graph and $v$ be a vertex of $C$. Then $v$ is a source with respect to some transitive orientation of $C$ if and only if $C^v$ is a comparability graph.

Now, using Theorem <ref>, we find a necessary and sufficient condition to make $G \srec G'$ a comparability graph, when one of $m$ and $m'$ is not a source (or sink) with respect to any transitive orientation of $G$ or $G'$.

Let $G$ and $G'$ be two comparability graphs such that $m$ is not a source with respect to any transitive orientation of $G$. If $G \srec G'$ is a comparability graph, then $m'$ is an all-adjacent vertex of $G'$.

Let $G \srec G'$ be a comparability graph. Assume $m'$ is not an all-adjacent vertex of $G'$. Then there exists a vertex $c' \in V'$ such that $c' \notin N_{G'}(m')$ but $\overline{b'c'} \in E'$ for some vertex $b' \in N_{G'}(m')$. The connectedness of the graph $G'$ ensures the existence of such vertex $c'$.

Consider the induced subgraph $(G \srec G')[V \cup \{b'\}]$, say ${^m}G_{b'}$. Note that $b'$ is adjacent to all vertices of $N_{G}(m)$ in $G \srec G'$. Hence, ${^m}G_{b'}$ is isomorphic to $G$ as it can be obtained from $G$ by replacing $m$ with $b'$. While ${^m}G_{b'}$ is a comparability graph, $b'$ cannot be a source with respect to any transitive orientation of ${^m}G_{b'}$, as $G$ does.

Now consider the induced subgraph $(G \srec G')[V \cup \{b', c'\}]$ of $G \srec G'$. Note that $(G \srec G')[V \cup \{b', c'\}] = ({^m}G_{b'})^{b'}$, the graph obtained from ${^m}G_{b'}$ by making $c'$ adjacent only to $b'$. Since $b'$ cannot be a source, $({^m}G_{b'})^{b'}$ is not a comparability graph, by Theorem source. However, $({^m}G_{b'})^{b'}$ is a comparability graph as it is an induced subgraph of the comparability graph $G \srec G'$; a contradiction.  Hence, $m'$ should be an all-adjacent vertex of $G'$.

We summarize the results of this section in the following theorem.

Let $G = (V \cup \{m\}, E)$ and $G' = (V' \cup \{m'\}, E')$ be two comparability graphs with disjoint vertex sets. Suppose $\mathcal{R}^p(G) = k$ and $\mathcal{R}^p(G') = k'$. Then we have the following:

* The split recomposition $G \srec G'$  is a comparability graph if and only if one of the following holds:

* The vertices $m$ and $m'$ are source and sink, or vice versa, with respect to some transitive orientations on $G$ and $G'$.

* At least one of the vertices $m$ and $m'$ is an all-adjacent vertex.

* Moreover, if the split recomposition $G \srec G'$ is a comparability graph, then $\mathcal{R}^p(G \srec G') = \max\{k, k'\}$ or $1 + \max\{k, k'\}$.

As a consequence, we also provide the prn of the graph construction $G^m$ in the following corollary.

Let $G$ be a comparability graph such that $\mathcal{R}^p(G) = k$. If $G^m$ is a comparability graph, then $\mathcal{R}^p(G^m) = k$ or $1 + k$.

If $G^m$ is a comparability graph, then by Theorem <ref>, $m$ is a source of $G$. Consider a path $P_3$: $\begin{tikzpicture}[scale=0.6]
\vertex (a_1) at (0,0) [fill=black, label=above:$m'$] {};
\vertex (a_2) at (1,0) [fill=black, label=above:$b$] {};
\vertex (a_3) at (2,0) [fill=black, label=above:$a$] {};

\path
(a_1) edge (a_2)
(a_2) edge (a_3);
\end{tikzpicture}$ and note that $\mathcal{R}^p(P_3) = 2$, as the word $bam'bm'a$ represents $P_3$, which is not a complete graph.  Further, it can be observed that $G^m$ is isomorphic to $G \srec P_3$.

If $k = 1$, then $G$ is a complete graph so that $m$ is an all-adjacent vertex of $G$. Accordingly, by Theorem <ref>, $\mathcal{R}^p(G^m) = \mathcal{R}^p(G \srec P_3) = \max\{1, 2\} = 2$. Otherwise, for $k \ge 2$, $\max\{k, 2\} = k$. Then, by Theorem <ref>, $\mathcal{R}^p(G^m) = k$ or $1 + k$. Hence, in any case, we have $\mathcal{R}^p(G^m) = k$ or $1 + k$.

§ PRN-IRREDUCIBLE GRAPHS

Following the notion of irreducible posets in order theory (cf. [34]), in this section, we define the concept of  prn-irreducible comparability graphs and study them with respect to split recomposition. In this connection, we characterize prn-irreducible graphs such that their recomposition is a comparability graph. Accordingly, we determine the prn of the resultant comparability graph based on the prns of its split components. We also observe that the split recomposition of prn-irreducible graphs is not prn-irreducible.

A comparability graph $C = (V, E)$ is said to be $k$-prn-irreducible for some $k \geq 2$, if $\mathcal{R}^p(C) = k$ and $\mathcal{R}^p(C[V \setminus \{a\}]) = k - 1$ for every $a \in V$. Further, a comparability graph is said to be prn-irreducible if it is $k$-prn-irreducible for some $k \geq 2$.

A comparability graph is $2$-prn-irreducible if and only if it is an edgeless graph on two vertices. For instance, any connected graph $C$ on at least 3 vertices with $\mathcal{R}^p(C) = 2$ has a vertex $a$ that is not adjacent to all other vertices. If we remove any vertex adjacent to $a$ from $C$, the prn of the resultant graph is not one, as it is not a complete graph.

For $n \ge 3$, consider the crown graph $H_{n,n}$ (a graph which is obtained by deleting a perfect matching from the complete bipartite graph $K_{n, n}$). From [19], recall that $\mathcal{R}^p(H_{n,n}) = n$. Let $H'$ be the bipartite graph obtained by deleting a vertex from $H_{n,n}$. Note that $\mathcal{R}^p(H') \le n-1$ as $n-1$ is the size of one of the partite sets of $H'$, and $n-1 \le \mathcal{R}^p(H')$ as $H_{n-1, n-1}$ is an induced subgraph of $H'$ (cf. [28]). Hence, $\mathcal{R}^p(H') = n-1$ so that $H_{n, n}$ is $n$-prn-irreducible.

For $n \ge 3$, the cycle $C_{2n}$ is $3$-prn-irreducible. Note that by deleting a vertex from $C_{2n}$ we get the path $P_{2n-1}$ with $2n-1$ vertices. For $n \ge 3$, $\mathcal{R}^p(C_{2n}) = 3$ and $\mathcal{R}^p(P_n) = 2$ (cf. [27]).

Trotter and Moore, as well as Kelly independently and simultaneously obtained the complete list of 3-irreducible posets [23, 35]. A complete list of $3$-prn-irreducible comparability graphs can be derived from the corresponding posets.

For $k \ge 2$, any $k$-prn-irreducible comparability graph does not have an all-adjacent vertex.

On the contrary, suppose $a$ is an all-adjacent vertex of a $k$-prn-irreducible comparability graph $C = (V, E)$. As $\mathcal{R}^p(C[V \setminus \{a\}]) = k-1$, let $p_1p_2 \cdots p_{k-1}$ represents the induced subgraph  $C[V \setminus \{a\}]$, where each $p_i$ $(1 \le i \le k-1)$ is a permutation on $V \setminus \{a\}$. Then consider the permutations $q_i = ap_i$, for all $1 \le i \le k-1$, on $V$  and note that the word $q_1q_2 \cdots q_{k-1}$ represents the graph $C$. Hence, $\mathcal{R}^p(C) = k-1$; a contradiction.

In view of Proposition <ref>, we have the following corollary of Theorem <ref>.

Let $G$ and $G'$ be comparability graphs such that $G$ is $k$-prn-irreducible and $G'$ is $k'$-prn-irreducible. Then $G \srec G'$ is a comparability graph if and only if $m$ is a source of $G$ and $m'$ is a sink of $G'$ with respect to some transitive orientations of $G$ and $G'$.

We now obtain the permutation-representation number of a split recomposition of two prn-irreducible comparability graphs in the following theorem.

For $k, k' \geq 3$, let $G$ and $G'$ be $k$-prn-irreducible and $k'$-prn-irreducible comparability graphs, respectively.  If $G \srec G'$ is a comparability graph, then  $\mathcal{R}^p(G \srec G') = \max\{k, k'\}$.

Suppose $G \srec G'$ is a comparability graph. In view of Corollary <ref>, let $m$ be a source of $G$ and $m'$ be a sink of $G'$ with respect to some transitive orientations of $G$ and $G'$. Note that $\mathcal{R}^p(G) = k$, $\mathcal{R}^p(G') = k'$ and $\mathcal{R}^p(G[V]) = k - 1$, $\mathcal{R}^p(G'[V']) = k' - 1$. Along the lines of Lemma <ref>, consider the permutations $p_i$ $(1 \le i \le k-1)$ on $V$, $p'_i$ $(1 \le i \le k'-1)$ on $V'$, $q_i$ $(1 \le i \le k)$ on the vertices of $G$, and $q'_i$ $(1 \le i \le k')$ on the vertices of $G'$ such that the words $w = q_1q_2 \cdots q_{k-1}q_{k}$ and $w' = q'_1q'_2 \cdots q'_{k'-1}q'_{k'}$ represent the graphs $G$ and $G'$, respectively, where

\[\begin{array}{ll}
q_{i} = mp_{i}, \quad(1 \le i \le k-1); \quad \quad & q'_{i} = p'_{i}m', \quad(1 \le i \le k'-1); \\
q_{k} = p_{{k-1}_{V \setminus N_{G}(m)}}m p_{{k-1}_{N_{G}(m)}}; \quad \quad & q'_{k'} = p'_{{k'-1}_{N_{G'}(m')}}m'p'_{{k'-1}_{V' \setminus  N_{G'}(m')}}. \\
\end{array}\]

Suppose $k' \le k$.  We construct $k$ number of permutations $v_i$ ($1 \le i \le k$) on the vertices of $G \srec G'$ as per the following and show that the word $v = v_1v_2 \cdots v_{k}$ represents the graph $G \srec G'$.

\begin{align*}
v_{i} & = p'_ip_i, \quad(1 \le i \le k'-1) \\
v_{j} & = p'_{k'-1}p_{j}, \quad(k' \le j \le k-1) \\
v_{k } & = p_{{k-1}_{V \setminus N_{G}(m)}}p'_{{k'-1}_{N_{G'}(m')}}p_{{k-1}_{N_{G}(m)}}p'_{{k'-1}_{V' \setminus N_{G'}(m')}}
\end{align*}

Note that $G[V]$ and $G'[V']$ are induced subgraphs of $G \srec G'$ represented by

\begin{align*}
w_{V} &=  p_1p_2 \; \cdots \; p_{k-1} p_{{k-1}_{V \setminus N_{G}(m)}}p_{{k-1}_{N_{G}(m)}}, \; \text{and}\\
w'_{V'} &= p'_1p'_2 \; \cdots \; p'_{k'-1}p'_{{k'-1}_{N_{G'}(m')}}p'_{{k'-1}_{V' \setminus  N_{G'}(m')}},
\end{align*}

respectively. Further, note that

\begin{align*}
v_{V} &= p_1p_2 \; \cdots \; p_{k-1}p_{{k-1}_{V \setminus N_{G}(m)}}p_{{k-1}_{N_{G}(m)}}\; \text{and}\\
v_{V'} &= p'_1p'_2 \; \cdots \; p'_{k'-2} \overbrace{p'_{k'-1} \; \cdots \; p'_{k'-1}}^{k - k'+1}p'_{{k'-1}_{N_{G'}(m')}}p'_{{k'-1}_{V' \setminus  N_{G'}(m')}}.
\end{align*}

Thus, any two vertices of $G[V]$ or of $G'[V']$ are adjacent if and only if they alternate in the word $v$.

For $a \in V$ and $a' \in V'$, note that $a$ and $a'$ are adjacent in $G \srec G'$ if and only if $a \in N_G(m)$ and $a' \in N_{G'}(m')$. Accordingly, we consider the following cases to show that $a$ and $a'$ are adjacent in $G \srec G'$ if and only if they alternate in $v$. If $a \in N_G(m)$ and $a' \in N_{G'}(m')$, then from the construction of $v$, we have $a'a \preceq v_i$ for all $1 \le i \le k$, so that $a$ and $a'$ alternate in $v$. If $a \notin N_{G}(m)$, then for any $a' \in V'$, we have $a'a \preceq v_1$ but $aa' \preceq v_{k}$.  Similarly, if $a' \notin N_{G'}(m')$, then for any vertex $a \in V$, we have $a'a \preceq v_1$ but $aa' \preceq v_{k}$. Hence, $a$ and $a'$ do not alternate in $v$, if $a \notin N_G(m)$ or $a' \notin N_{G'}(m')$. Hence the word $v$ represents $G \srec G'$ permutationally.

Similarly, when $k \le k'$, we can show that the word $v = v_1v_2 \cdots v_{k'-1}v_{k'}$ represents the graph $G \srec G'$ permutationally, where

\begin{align*}
v_{i} & = p'_ip_i, \quad(1 \le i \le k-1); \\
v_{j} & = p'_jp_{k-1}, \quad(k \le j \le k'-1); \\
v_{k'} & = p_{{k-1}_{V \setminus N_{G}(m)}}p'_{{k'-1}_{N_{G'}(m')}}p_{{k-1}_{N_{G}(m)}}p'_{{k'-1}_{V' \setminus N_{G'}(m')}}.
\end{align*}

In any case, since $v$ is a concatenation of $\max\{k, k'\}$ number of permutations, we have $\mathcal{R}^p(G \srec G') \le \max\{k, k'\}$. Also, since $G$ and $G'$ are isomorphic to certain induced subgraphs of $G \srec G'$ (cf. Remark <ref>), we have  $\mathcal{R}^p(G \srec G') \ge \max\{k, k'\}$. Hence,
$\mathcal{R}^p(G \srec G') = \max\{k, k'\}$.

In view of Theorem <ref>, we have the prn of following bipartite graphs which are obtained from the recomposition of prn-irreducible graphs.

For $k, k' \ge 3$,  the prn of the recomposition of crown graphs $H_{k, k}$ and $H_{k', k'}$ is $\max\{k, k'\}$.

For $k, k' \ge 3$,  the prn of the recomposition of even cycles $C_{2k}$ and $C_{2k'}$ is 3.

For $k, k' \geq 3$, if $G$ and $G'$ be $k$-prn-irreducible and $k'$-prn-irreducible comparability graphs, respectively, then $G \srec G'$ is not prn-irreducible.

Suppose $G \srec G'$ is a comparability graph. By Proposition <ref>, $m$ and $m'$ are not all-adjacent vertices. Also, by Theorem <ref>, we have $\mathcal{R}^p(G \srec G') = \max\{k, k'\} = k$, say, without loss of generality.

Since $m'$ is not an all-adjacent vertex of $G'$, there exists $c' \in V'$ such that $c' \notin N_{G'}(m')$. Consider the induced subgraph $L = (G \srec G')[V \cup (V' \setminus \{c'\})]$.
Clearly, $\mathcal{R}^p(L) \le k$. We show that $\mathcal{R}^p(L) = k$ so that $G \srec G'$ is not prn-irreducible.

For $b' \in N_{G'}(m')$, note that the induced subgraph $(G \srec G')[V \cup \{b'\}]$ is isomorphic to $G$ and it is also an induced subgraph of $L$. Thus, $\mathcal{R}^p(L) \ge k$ and hence, $\mathcal{R}^p(L) = k$.

§ CONCLUSION

This work paves a way, in general, to study the word-representability of graphs using split decomposition and recomposition. As the problem of deciding whether a given graph is word-representable is NP-complete, using split decomposition and recomposition, the problem can be reduced to its prime components. For example, the parity graphs are established as word-representable, because their prime components are word-representable (see Corollary <ref>). In view of Corollary <ref>, the open problem of characterizing word-representable perfect graphs can be approached through the following problem: What are the prime perfect graphs that are not word-representable? Similar to bipartite graphs, it is also interesting to find the subclasses of comparability graphs which are closed under recomposition. If one of the marked vertices is an all-adjacent vertex in a general case, or in the case $G$ and $G'$ are prn-irreducible graphs, we proved that $\mathcal{R}^p(G \srec G') = \kappa$, where  $\kappa = \max\{\mathcal{R}^p(G), \mathcal{R}^p(G')\}$.  However, there are two categories of prn for the recomposed comparability graph, i.e., $\mathcal{R}^p(G \srec G') = \kappa$ or $1 + \kappa$. Accordingly, one may target to classify the graphs with respect to the prn of their recomposition amongst the two categories.

[1]
M. Bahrani and J. Lumbroso.
Enumerations, forbidden subgraph characterizations, and the
Electron. J. Combin., 25(4):Paper No. 4.47, 45pp, 2018.

[2]
R. E. Bixby.
A composition for perfect graphs.
In Topics on perfect graphs, volume 88 of North-Holland
Math. Stud., pages 221–224. North-Holland, Amsterdam, 1984.

[3]
K. P. Bogart.
Maximal dimensional partially ordered sets. I. Hiraguchi's
Discrete Math., 5:21–31, 1973.

[4]
A. Bouchet.
Reducing prime graphs and recognizing circle graphs.
Combinatorica, 7(3):243–254, 1987.

[5]
A. Bouchet.
Transforming trees by successive local complementations.
J. Graph Theory, 12(2):195–207, 1988.

[6]
S. Cicerone and G. Di Stefano.
On the extension of bipartite to parity graphs.
Discrete Appl. Math., 95(1-3):181–195, 1999.

[7]
S. Cornelsen and G. Di Stefano.
Treelike comparability graphs.
Discrete Appl. Math., 157(8):1711–1722, 2009.

[8]
W. H. Cunningham.
Decomposition of directed graphs.
SIAM J. Algebraic Discrete Methods, 3(2):214–228, 1982.

[9]
W. H. Cunningham and J. Edmonds.
A combinatorial decomposition theory.
Canadian J. Math., 32(3):734–765, 1980.

[10]
E. Dahlhaus.
Parallel algorithms for hierarchical clustering and applications to
split decomposition and parity graph recognition.
J. Algorithms, 36(2):205–240, 2000.

[11]
C. M. H. de Figueiredo, S. Klein, and K. Vus̆ković.
The graph sandwich problem for 1-join composition is NP-complete.
Discrete Appl. Math., 121(1-3):73–82, 2002.

[12]
B. Dushnik and E. W. Miller.
Partially ordered sets.
Amer. J. Math., 63:600–610, 1941.

[13]
C. P. Gabor, K. J. Supowit, and W. L. Hsu.
Recognizing circle graphs in polynomial time.
J. Assoc. Comput. Mach., 36(3):435–473, 1989.

[14]
T. Gallai.
Transitiv orientierbare Graphen.
Acta Math. Acad. Sci. Hungar., 18:25–66, 1967.

[15]
C. Gavoille and C. Paul.
Distance labeling scheme and split decomposition.
Discrete Math., 273(1-3):115–130, 2003.

[16]
J. Gimbel.
Sources in posets and comparability graphs.
Order, 9(4):361–365, 1992.

[17]
E. Gioan and C. Paul.
Dynamic distance hereditary graphs using split decomposition.
In Algorithms and computation, volume 4835 of Lecture
Notes in Comput. Sci., pages 41–51. Springer, Berlin, 2007.

[18]
M. C. Golumbic.
Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics.
Elsevier Science B.V., Amsterdam, second edition, 2004.

[19]
M. M. Halldórsson, S. Kitaev, and A. Pyatkin.
Alternation graphs.
In Graph-theoretic concepts in computer science, volume 6986 of
Lecture Notes in Comput. Sci., pages 191–202. Springer, Heidelberg,

[20]
P. L. Hammer and F. Maffray.
Completely separable graphs.
Discrete Appl. Math., 27(1-2):85–99, 1990.

[21]
T. Hiraguti.
On the dimension of orders.
Sci. Rep. Kanazawa Univ., 4(1):1–20, 1955.

[22]
E. Howorka.
A characterization of distance-hereditary graphs.
Quart. J. Math. Oxford Ser. (2), 28(112):417–420, 1977.

[23]
D. Kelly.
The $3$-irreducible partially ordered sets.
Canadian J. Math., 29(2):367–383, 1977.

[24]
S. Kitaev and V. Lozin.
Words and graphs.
Monographs in Theoretical Computer Science. An EATCS Series.
Springer, Cham, 2015.

[25]
S. Kitaev and A. Pyatkin.
On representable graphs.
J. Autom. Lang. Comb., 13(1):45–54, 2008.

[26]
S. Kitaev and S. Seif.
Word problem of the Perkins semigroup via directed acyclic graphs.
Order, 25(3):177–194, 2008.

[27]
K. Mozhui and K. V. Krishna.
Graphs with permutation-representation number at most three.
arXiv:2307.00301, 2023.

[28]
K. Mozhui and K. V. Krishna.
On the permutation-representation number of bipartite graphs using
neighborhood graphs.
arXiv:2311.13980, 2023.

[29]
S. Olariu.
On sources in comparability graphs, with applications.
Discrete Math., 110(1-3):289–292, 1992.

[30]
M. Rao.
Coloring a graph using split decomposition.
In Graph-theoretic concepts in computer science, volume 3353 of
Lecture Notes in Comput. Sci., pages 129–141. Springer, Berlin, 2004.

[31]
M. Rao.
Solving some NP-complete problems using split decomposition.
Discrete Appl. Math., 156(14):2768–2780, 2008.

[32]
H. Sachs.
On the Berge conjecture concerning perfect graphs.
In Combinatorial Structures and their Applications (Proc.
Calgary Internat. Conf., Calgary, Alta., 1969), pages 377–384.
Gordon and Breach, New York-London-Paris, 1970.

[33]
J. Spinrad.
Recognition of circle graphs.
J. Algorithms, 16(2):264–282, 1994.

[34]
W. T. Trotter.
Combinatorics and partially ordered sets: Dimension theory.
Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins
University Press, Baltimore, MD, 1992.

[35]
W. T. Trotter and J. I. Moore.
Characterization problems for graphs, partially ordered sets,
lattices, and families of sets.
Discrete Math., 16(4):361–381, 1976.

[36]
M. Yannakakis.
The complexity of the partial order dimension problem.
SIAM J. Algebraic Discrete Methods, 3(3):351–358, 1982.


# A Study of the Probability Distribution of the Balls in Bins Process with
Power Law Feedback

Samuel Forbes<EMAIL_ADDRESS>
(August 2023)

###### Abstract

We analyse the balls in bins process with feedback with primary focus on the
power law feedback function $f(\omega)=\eta\omega^{\gamma}\,$, $\eta>0\,$
$\gamma\geq 0\,$. Using the recursive solution to the master equation we find
for power law feedback numerical evidence that the probability mass function
for finite time scales asymptotically with $\omega^{-\gamma}\,$ for
$\gamma>1\,$. We also provide simulations supporting a previous result by
Oliveira (corollary to Theorem 4 in [13]) that the tail of the losers scale as
$\omega^{-(\gamma-1)}\,$ but extending to $N\geq 2$ bins. We thus find
evidence that the balls in bins process with power law feedback produces power
law distributions as is common to many real world phenomena.

###### Acknowledgements

Samuel Forbes would like to thank Stefan Grosskinsky for valuable assistance
with the background probability theory, simulations and comments on the
manuscript, Paul Chleboun for important assistance with the binary tree search
implementation to produce Figure 1 and financial support from EPSRC through
grant EP/L015374/1 when part of this work was studied.

##  1 Introduction

Suppose there are $N\in\mathbb{N}$ bins and that the number of balls in bin
$j\in\\{1,\,2,\dots,N\\}$ at iteration $n=0,\,1,\,2,\dots$ is
$I_{n}(j)\in\mathbb{N}\,$. We shall refer to the bins as agents as this model
may be applied to many types of real world phenomena, examples of which will
be discussed below. Define the set of all agents at iteration $n$ as
$\mathbf{I}_{n}:=\\{I_{n}(1),I_{n}(2),\dots,I_{n}(N)\\}$. Then suppose the
probability that agent $j$ gains one ball at iteration $n$ is

$\mathbb{P}(I_{n+1}(j)=I_{n}(j)+1|\mathbf{I}_{n})=\frac{f(I_{n}(j))}{\sum_{i=1}^{N}f(I_{n}(i))}\,$
(1)

where $f:\mathbb{N}\rightarrow\mathbb{R}_{>0}$ is a continuous positive
feedback function. The balls in bins process with feedback [4, 12], also
called the generalised Pólya urn with feedback [14, 10] is the Markov chain
$\\{\mathbf{I}_{n}\,:\,n\in\mathbb{N}\\}$ which we shall refer to as the
feedback model. We shall focus on the following power law feedback function

$f(\omega)=\eta\omega^{\gamma}\quad\text{ such that }\eta>0\,,\gamma\geq 0\,.$
(2)

A feature of the feedback model is the presence of monopoly where one agent
after a certain time gains every new ball, see Theorem 1.1 in [12]. Monopoly
is something seen in the real world, for example the extreme wealth of the
owner(s) of a company with market domination such as Google. Another example
is the city of London which has a comparatively vast population compared to
other cities in the UK. However the monopoly in real life variables is usually
not as strong as in the feedback model and in reality there is often more than
one extremely sizeable agent.

Another feature of the feedback model that occurs alongside monopoly is a
power law distribution in the tail of the loser (non-monopoly) agents. In
particular for the power law feedback function (2) and $N=2$ agents the tail
of a loser agent scales proportional to $\omega^{-(\gamma-1)}$ which is a
corollary to Theorem 4 in [13]. We provide simulations in Section 4 to support
that this is also true for $N\geq 2$ agents. Many real world phenomena have
power law distributions and this may be due to a feedback mechanism and thus
the feedback model could be applicable to these cases [4, 14, 10, 13]. In fact
the feedback model has been applied directly to US wealth data from 1988-2012
with power law feedback (2) [17]. Both wealth and city size exhibit power laws
in the probability distribution, see for example [18, 17, 7] and [11]
respectively. Both power laws and monopoly are seen in the empirical tail,
defined as one minus the empirical cumulative distribution function, of
simulations111All simulations and numerical solutions in this paper can be
found in [6].  of the feedback model, see Figure 1.

Figure 1: Empirical tail of a single simulation of feedback model with
feedback function $f(\omega)=\omega^{\gamma}$ for
$\gamma=1,\,1.1,\,1.2,\,1.3$, (top left, top right, bottom left, bottom right
respectively), $N=1000$ agents,
$\mathbf{I}_{0}=\mathbf{1}_{N}=\\{1,1,\dots,1\\}$ and at iteration
$n=10^{6},\,10^{7},\,10^{8},\,10^{9}\,$. Black lines in top left are
exponential fits. Black lines for $\gamma>1$ are power laws proportional to
$\omega^{-\beta}$ fitted with the MLE method found in [3] approximating the
discrete values as continuous. Monopoly agents are most obvious for bottom
right with $\gamma=1.3\,.$

We shall now introduce an equivalent form of the feedback model in continuous
time that will allow us to find the probability mass function solution.
Suppose the set of $\mathbf{W}_{t}=\\{W_{t}(1),W_{t}(2),\dots,W_{t}(N)\\}$ is
a continuous time homogeneous Markov chain where agent $j$ has
$W_{t}(j)\in\mathbb{N}$ balls at time $t\in[0,\infty)\,.$ Suppose also
$\mathbf{W}_{0}=\mathbf{I}_{0}\,.$ For convenience let us consider a single
agent and define $W_{t}:=W_{t}(j)\,$. Define
$p_{t}(\omega,\nu):=\mathbb{P}(W_{t}=\nu|W_{0}=\omega)$ as the transition mass
function of $W_{t}$ and $p_{t}(\omega):=\mathbb{P}(W_{t}=\omega)$ as the mass
function of $W_{t}\,.$ Define the rates as
$g(\omega,\nu):=\frac{\mathrm{d}}{\mathrm{d}t}p_{t}(\omega,\nu)\big{|}_{t=0}\,$.
We set the rates as

$g(\omega,\nu)=\begin{cases}f(\omega)&\nu=\omega+1\,,\\\
-f(\omega)&\nu=\omega\,,\\\ 0&\text{otherwise}\end{cases}$ (3)

where $f$ is the feedback function as above.

Define the holding time $H_{\omega}$ as the time until $W_{t}$ jumps up by one
ball. Thus for some time $\tau\in[0,\infty)$

$H_{\omega}:=\inf_{t}\\{W_{\tau+t}=\omega+1:W_{\tau}=\omega\\}\,.$

We note, see e.g. Section 6.9 of [16], the holding time $H_{\omega}$ follows
an exponential distribution with mean $1/|g(\omega,\omega)|=1/f(\omega)$ and
thus $H_{\omega}\sim\text{Exp}(f(\omega))\,.$ We now define the jump times
$t_{0}=0<t_{1}<t_{2}<\dots$ as the cumulative sum of the holding times which
occur when the Markov chain $\mathbf{W}_{t}$ changes to a new state where one
of the agents gains one ball. We note the agents $W_{t}$ within
$\mathbf{W}_{t}$ jump independently of each other. Then by exponential
embedding, see Theorem 2 in [13], it can be shown that we have
$\mathbf{W}_{t_{n}}=\mathbf{I}_{n}\,$ so that $\mathbf{W}_{t}$ is equal to the
feedback model $\mathbf{I}_{n}$ at the jump times $t_{n}$. We shall refer to
the pure birth process, see Chapter xvii@, Section 3 of [5],
$\\{\mathbf{W}_{t}\,:\,t=t_{n}\\}$ as the feedback process.

For $W_{0}=\omega_{0}$ the master equation, see e.g. Section 3 of [9] and
Chapter xvii@, Section 3 of [5] specifically for pure birth processes, for the
time derivative of the probability mass function for an agent in
$\mathbf{W}_{t}$ with the rates (3) is

$\frac{\mathrm{d}}{\mathrm{d}t}p_{t}(\omega)=\begin{cases}-p_{t}(\omega)f(\omega)&\omega=\omega_{0}\\\
p_{t}(\omega-1)f(\omega-1)-p_{t}(\omega)f(\omega)&\omega>\omega_{0}\,.\\\
\end{cases}$ (4)

The master equation has a recursive solution found in [15]. We show in Section
3 that the first term of this solution when applied to power law feedback (2)
with $\gamma>1$ scales asymptotically as $\omega^{-\gamma}\,$ and is a good
approximation under certain parametrisations. We emphasise that our new work
is found in Sections 3 and 4.

##  2 Overview of Some Existing Results

As mentioned in the introduction, interesting properties of the feedback model
are already known. In particular, conditions on the feedback function
$f(\omega)$ leads to monopoly where one agent gains all but a finite number of
balls and fixed rankings where the order of agents from richest to poorest
(most balls to least) becomes fixed after a certain period of time. As these
cases may have broad applications to models of real world phenomena as
discussed in the introduction we reproduce them in this section.

######  Definition 1 (Monopoly).

Monopoly occurs if there exists an agent $j_{m}\in\\{1,2,\dots,N\\}$ and
$n_{m}\in\mathbb{N}$ such that for all $n>n_{m}$ we have
$\mathbb{P}(I_{n+1}(j_{m})=I_{n}(j_{m})+1|\mathbf{I}_{n})=1\,.$

We shall refer to the agent $j_{m}$ as a monopoly agent.

######  Definition 2 (Losers).

We define the random variable L as the number of balls of the $N-1$ ‘loser’
non-monopoly agents once monopoly has occurred.

To be precise for $n_{m}\in\mathbb{N}$ as in Definition 1 then all
$j_{l}\in\\{1,2,\dots,N\\}$ such that $j_{l}\neq j_{m}$ are the loser agents.
Then for all $n>n_{m}$ we have
$\mathbb{P}(I_{n+1}(j_{l})=I_{n}(j_{l})+1|\mathbf{I}_{n})=0$ and thus
$I_{n}(j_{l})=I_{n+1}(j_{l})=I_{j_{l}}<\infty$ and so
$\textbf{L}=\\{I_{j_{l}}\\}\,.$

######  Definition 3 (Fixed Rankings).

Rankings of agents become fixed if there exists an $n_{f}\in\mathbb{N}$ such
that for a particular ordering of the $N$ agents $j_{i}\,,i=1,2,\dots,N\,$

$I_{n}(j_{1})<I_{n}(j_{2})<\dots<I_{n}(j_{N})\quad\forall\,n>n_{f}\,.$

Clearly if monopoly occurs then so will fixed rankings.

######  Theorem 1 (Theorem 1.1 [12]).

In the feedback model we have the following three mutually exclusive cases
irrespective of initial conditions:

  1. 1.

If $\sum_{\omega=1}^{\infty}f(\omega)^{-1}<\infty$ then monopoly occurs.

  2. 2.

If $\sum_{\omega=1}^{\infty}f(\omega)^{-1}=\infty$ but
$\sum_{\omega=1}^{\infty}f(\omega)^{-2}<\infty$ then monopoly does not occur
but there will be fixed rankings.

  3. 3.

If $\sum_{\omega=1}^{\infty}f(\omega)^{-2}=\infty$ there will be no monopoly
and no fixed rankings.

Theorem 1 with $f(\omega)=\eta\omega^{\gamma}$ (2) means that monopoly occurs
with $\gamma>1$, no monopoly but fixed rankings when $1/2<\gamma\leq 1$ and no
monopoly and no fixed rankings for $0\leq\gamma\leq 1/2\,.$ Examples of
feedback functions satisfying the different cases in Theorem 1 are given in
[12, 10]. For a particular class of feedback functions, called valid feedback
functions, satisfying Case 1. of Theorem 1, a Theorem on the tail of the
losers has been found, see Theorem 4 in [13]. In particular the following
corollary, as mentioned in the abstract and introduction, applies this theorem
to the power law feedback function (2).

######  Corollary 1 (Corollary to Theorem 4 in [13]).

Suppose there are $N=2$ agents and $f$ is the power law feedback function (2)
with $\gamma>1$ then there exists an $\alpha>0$ such that222Where for general
functions $g$ and $h\,$, we define $g(x)\simeq h(x)\Leftrightarrow
g(x)/h(x)\rightarrow 1$ as $x\rightarrow\infty\,.$
$\mathbb{P}(L>\omega)\simeq\alpha/\omega^{\gamma-1}\,.$

We shall give evidence in Section 4 through simulations of the feedback
process that Corollary 2 holds also for $N\geq 2$ agents.

We shall now focus on probability mass function solutions to the master
equation (4). We write down two particular solutions applied to power law
feedback (2) for $\gamma=0\,,\,1\,.$

######  Proposition 1 (See Ch.xvii@, Sections 1-3 of [5]).

The solution to the master equation (4) with $W_{0}=\omega_{0}$ for power law
feedback (2) for

  1. 1.

$\gamma=0$ is Poisson with probability mass function

$p_{t}(\omega)=\frac{(\eta
t)^{\omega-\omega_{0}}}{(\omega-\omega_{0})!}e^{-\eta
t}\,,\quad\omega=\omega_{0},\omega_{0}+1,\dots$

Note this is the Poisson process.

  2. 2.

$\gamma=1$ is negative binomial with probability mass function

$p_{t}(\omega)={\omega-1\choose\omega-\omega_{0}}(1-e^{-\eta
t})^{\omega-\omega_{0}}e^{-\eta\omega_{0}t}\,,\quad\omega=\omega_{0},\omega_{0}+1,\dots$

Note this is the Yule process and for the particular case with $\omega_{0}=1$
gives the geometric distribution which can be approximated by the exponential
distribution, see Figure 4.

###### Proof.

Substitute the probability mass functions into the respective master equation
(4) for power law feedback (2) for $\gamma=0$ and $\gamma=1\,$ . ∎

The following corollary gives a general solution to the master equation (4)
under a mild condition on the feedback function $f\,.$ We provide the proof
for this particular case as it is significantly simpler than to a general case
which applies to a broader class of equations, see Theorem 1 in [15].

######  Corollary 2 (Corollary to Theorem 1 in [15]).

For $W_{0}=\omega_{0}$ and provided $f(\omega)\neq f(i)$ for all
$i=\omega_{0},\,\omega_{0}+1,\dots,\,\omega-1\,,$ the master equation (4) has
the following solution

$p_{t}(\omega)=\sum_{i=\omega_{0}}^{\omega}a_{\omega,i}e^{-f(i)t}\,,\quad\omega\geq\omega_{0}$
(5)

with $a_{\omega_{0},\omega_{0}}=1$ and for $\omega>\omega_{0}$

$\displaystyle a_{\omega,i}$
$\displaystyle=\frac{f(\omega-1)}{f(\omega)-f(i)}a_{\omega-1,i}\,,\quad
i=\omega_{0},\,\omega_{0}+1,\dots,\,\omega-1\,,$ $\displaystyle
a_{\omega,\omega}$
$\displaystyle=-\sum_{i=\omega_{0}}^{\omega-1}a_{\omega,i}\,.$

###### Proof.

The solution for $\omega=\omega_{0}$ to (4) is

$p_{t}(\omega_{0})=e^{-f(\omega_{0})t}$

which agrees with the corollary. Now for $\omega>\omega_{0}$ we have
substituting (5) into the LHS of the master equation (4) that

$\frac{\mathrm{d}}{\mathrm{d}t}p_{t}(\omega)=-\sum_{i=\omega_{0}}^{\omega}a_{\omega,i}f(i)e^{-f(i)t}$

and into the RHS we have with $a_{\omega-1,\omega}:=0$

$p_{t}(\omega-1)f(\omega-1)-p_{t}(\omega)f(\omega)=\sum_{i=\omega_{0}}^{\omega}(f(\omega-1)a_{\omega-1,i}-f(\omega)a_{\gamma,\omega,i})e^{-f(i)t}\,.$

Setting the summands of the LHS and RHS equal to each other we have for
$\omega>\omega_{0}\,$

$\displaystyle-f(i)a_{\omega,i}$
$\displaystyle=f(\omega-1)a_{\omega-1,i}-f(\omega)a_{\omega,i}\Leftrightarrow$
$\displaystyle a_{\omega,i}$
$\displaystyle=\frac{f(\omega-1)}{f(\omega)-f(i)}a_{\omega-1,i}\,,\quad
i=\omega_{0},\,\omega_{0}+1,\dots,\omega-1\,.$

provided $f(\omega)\neq f(i)$ for all
$i=\omega_{0},\,\omega_{0}+1,\dots,\,\omega-1\,.$

As $W_{0}=\omega_{0}$ we have that
$p_{0}(\omega)=\sum_{i=\omega_{0}}^{\omega}a_{\omega,i}=0$ for all
$\omega>\omega_{0}\,.$ This implies
$a_{\omega,\omega}=-\sum_{i=\omega_{0}}^{\omega-1}a_{\gamma,\omega,i}$ for all
$\omega>\omega_{0}\,.$ Finally we also have
$p_{0}(\omega_{0})=a_{\omega_{0},\omega_{0}}=1\,.$

∎

From (5) the probability any agent is finite in infinite time is zero which
agrees with the fact that the feedback process is a pure birth process.

######  Corollary 3.

For all $\omega\in\mathbb{N}$

$p_{\infty}(\omega):=\lim_{t\rightarrow\infty}p_{t}(\omega)=0\,.$ (6)

######  Example.

To illustrate Corollary 2 let us check the sum formula (5) for the power law
feedback (2) with $\gamma=1$ ($f(\omega)=\eta\omega$) has the negative
binomial probability solution found in Proposition 1. The negative binomial
mass function in Proposition 1 can be expanded so that

$\displaystyle p_{t}(\omega)$
$\displaystyle={\omega-1\choose\omega-\omega_{0}}(1-e^{-\eta
t})^{\omega-\omega_{0}}e^{-\omega_{0}\eta t}$
$\displaystyle=\sum_{i=\omega_{0}}^{\omega}{\omega-1\choose\omega-\omega_{0}}{\omega-\omega_{0}\choose
i-\omega_{0}}(-1)^{i-\omega_{0}}e^{-\eta it}\,.$

Taking

$a_{\omega,i}={\omega-1\choose\omega-\omega_{0}}{\omega-\omega_{0}\choose
i-\omega_{0}}(-1)^{i-\omega_{0}}\quad\text{for
}i=\omega_{0},\omega_{0}+1,\dots,\omega$

we shall show that these coefficients follow the rules in Corollary 2. First
we see $a_{1,\omega_{0},\omega_{0}}=1$ and for $\omega>\omega_{0}$ it can be
simply shown that

$a_{\omega,i}=\frac{f(\omega-1)}{f(\omega)-f(i)}a_{\omega-1,i}=\frac{\omega-1}{\omega-i}a_{\omega-1,i}\,,\quad
i=\omega_{0},\,\omega_{0}+1,\dots,\,\omega-1$

Also

$\sum_{i=\omega_{0}}^{\omega}{\omega-1\choose\omega-\omega_{0}}{\omega-\omega_{0}\choose
i-\omega_{0}}(-1)^{j-\omega_{0}}={\omega-1\choose\omega-\omega_{0}}\sum_{i=0}^{\omega-\omega_{0}}{\omega-\omega_{0}\choose
i}(-1)^{i}=(1-1)^{\omega-\omega_{0}}=0$

and thus $a_{\omega,\omega}=-\sum_{i=\omega_{0}}^{\omega-1}a_{\omega,i}\,.$

##  3 Approximating the Probability Mass Function of the Feedback Process with
Power Law Feedback

We first present two further corollaries to Corollary 2.

######  Corollary 4.

For the $a_{\omega,i}$ defined in Corollary 2 we have for
$i=\omega_{0},\,\omega_{0}+1,\,\dots,\,\omega-1$

$a_{\omega,i}=\frac{f(i)}{f(\omega)}\left(\prod_{j=i+1}^{\omega}\frac{1}{1-f(i)/f(j)}\right)a_{i,i}\,.$

###### Proof.

$\displaystyle a_{\omega,i}$
$\displaystyle=\frac{f(\omega-1)}{f(\omega)-f(i)}a_{\omega-1,i}$
$\displaystyle=\frac{f(\omega-1)}{f(\omega)-f(i)}\frac{f(\omega-2)}{f(\omega-1)-f(i)}a_{\omega-2,i}$
$\displaystyle\vdots$ $\displaystyle=\frac{f(\omega-1)f(\omega-2)\dots
f(i)}{(f(\omega)-f(i))(f(\omega-1)-f(i))\dots(f(i+1)-f(i))}a_{i,i}$
$\displaystyle=\left(\frac{f(i)}{f(\omega)}\right)\frac{f(i+1)\dots
f(\omega-1)}{(f(i+1)-f(i))\dots(f(\omega-1)-f(i))}\left(\frac{1}{1-(f(i)/f(\omega)}\right)a_{i,i}$
$\displaystyle=\frac{f(i)}{f(\omega)}\left(\prod_{j=i+1}^{\omega}\frac{1}{1-f(i)/f(j)}\right)a_{i,i}\,.$

∎

We note that there does not seem to be any obvious general representation of
the $a_{i,i}\,.$ With the $a_{\omega,i}$ defined in Corollary 2 and under the
same mild condition on $f$ we have that

######  Corollary 5.

For $W_{0}=\omega_{0}$ and $\omega>\omega_{0}$ the master equation (4) has
solution

$p_{t}(\omega)=e^{-f(\omega_{0})t}\left(\prod_{j=\omega_{0}+1}^{\omega}\frac{1}{1-f(\omega_{0})/f(j)}\right)f(\omega_{0})/f(\omega)+\sum_{i=\omega_{0}+1}^{\omega}a_{\omega,i}e^{-f(i)t}\,.$
(7)

###### Proof.

For $\omega>\omega_{0}$ we can write (5) as

$p_{t}(\omega)=a_{\omega,\omega_{0}}e^{-f(\omega_{0})t}+\sum_{i=\omega_{0}+1}^{\omega}a_{\omega,i}e^{-f(i)t}\,.$

Now as $a_{\omega_{0},\omega_{0}}=1$ from Corollary 4 we have

$a_{\omega,\omega_{0}}=\frac{f(\omega_{0})}{f(\omega)}\left(\prod_{j=\omega_{0}+1}^{\omega}\frac{1}{1-f(\omega_{0})/f(j)}\right)\,.$

∎

We find from simulations that for $\omega_{0}=1\,$, applied to the power law
feedback function (2) with $\gamma>1\,$, and large enough $t\,,$ the first
term of (7) (equivalently of (5))

$\hat{p}_{t}(\omega)=e^{-\eta\omega_{0}^{\gamma}t}\left(\prod_{j=\omega_{0}+1}^{\omega}\frac{1}{1-(\omega_{0}/j)^{\gamma}}\right)(\omega_{0}/\omega)^{\gamma}\,.$
(8)

is a good approximation to $p_{t}(\omega)$ (5), see Figures 3 and 4. We note
that (8) can be embedded into a regularly varying function, see the Appendix,
and so is dominated asymptotically333If we say a function $f(\omega)$ is
asymptotically dominated by $\omega^{-\gamma}$ or asymptotically scales with
$\omega^{-\gamma}$ we mean $f(\omega)$ is regularly varying with index
$-\gamma\,,$ see the Appendix. by $\omega^{-\gamma}\,.$ For $\omega_{0}>1$ the
estimate (8) generally fails to be a good approximation but $p_{t}(\omega)$
still seems to asymptotically scale as $\omega^{-\gamma}$ for $\gamma>1\,$,
see Figure 3. This indicates that the factor $1/f(\omega)$ seen in Corollary
4, at least for power law feedback (2), plays a dominant role asymptotically
in (5).

Figure 2: Numerical solution of the probability mass function sum formula
solution (5) for $\omega_{0}=1\,$, for power law feedback (2) with $\eta=1$
and $\gamma=1.4$ for $t=1.0$ to $t=5.0$ in $0.5$ increments up to $\omega=300$
(for greater $\omega$ the simulation breaks down due to the magnitudes within
the summands). Black dashed lines are the approximations (8) for $t\geq
2.5\,.$ Solid black line proportional to $\omega^{-\gamma}$ for comparison.

Figure 3: Numerical solution of the probability mass function sum formula
solution (5) for $\omega_{0}=2\,$, for power law feedback (2) with $\eta=1$
and $\gamma=1.4$ for $t=1.0$ to $t=5.0$ in $0.5$ increments up to
$\omega=300\,$. Black dashed lines are the approximations (8) for $t\geq
3.5\,$ which we see are not good. Solid black line proportional to
$\omega^{-\gamma}$ for comparison.

Figure 4: Numerical solution of the probability mass function sum formula
solution (5) for $\omega_{0}=1\,$, for power law feedback (2) with $\eta=1$
and $\gamma$ going up in $0.2$ increments from $1$ to $2\,$ up to
$\omega=300\,$. The black dashed line for $\gamma=1$ is an exponential fit
approximating the geometric seen in Proposition 1, while for $\gamma>1$ the
black dashed lines are the approximations (8).

##  4 Approximating the Tail of the Feedback and Loser Process with Power Law
Feedback

The time taken for an agent $W_{t}$ to visit all states
$\omega_{0},\,\omega_{0}+1,\dots$ is the cumulative sum of the holding times
and described by the random variable

$T=\sum_{\omega=\omega_{0}}^{\infty}H_{\omega}\,.$

If $T$ is finite this is called the explosion time and coincides with the
monopoly agent case in Theorem 1, Case 1, (Theorem 1.1 in [12]). We note that
the expected explosion time is444Where linearity of expectation holds as a
consequence of monotone convergence, see for example Section 5.6 of [16].

$\mathbb{E}[T]=\sum_{\omega=\omega_{0}}^{\infty}\mathbb{E}[H_{\omega}]=\sum_{\omega=\omega_{0}}^{\infty}\frac{1}{|g(\omega,\omega)|}=\sum_{\omega=\omega_{0}}^{\infty}\frac{1}{f(\omega)}\,.$
(9)

Using the integral test, see e.g. Theorem 8.23 [1], we can bound the expected
explosion time (9) for the feedback process with power law feedback (2) and
$\gamma>1$ as

$t_{\gamma}:=\frac{1}{\eta\omega_{0}^{\gamma-1}(\gamma-1)}\leq\sum_{\omega=\omega_{0}}^{\infty}\frac{1}{\eta\omega^{\gamma}}\leq\frac{1}{\eta\omega_{0}^{\gamma}}+\frac{1}{\eta\omega_{0}^{\gamma-1}(\gamma-1)}\,$
(10)

where $t_{\gamma}$ is defined as the lower bound of the expected explosion
time. Notice from (10) that larger $\gamma$ gives a smaller expected explosion
time.

As discussed in Section 3.2 of [13] every agent will have a unique explosion
time thus creating an ordering on the times an agent will explode. However as
stated in Remark 2 in [13] one can only relate the feedback process to the
feedback model up to the first explosion time.

Now we would like to make inference on the losers L, see Definition 2, in the
feedback model by comparing to the feedback process. Let us define the loser
process $\\{\mathbf{L}_{t}\,:\,t=t_{n}\\}$, where $t_{n}$ are the jump times,
as a subset of the feedback process that have not exploded up to time $t$ i.e.

$\mathbf{L}_{t}=\\{L_{t}\\}=\\{W_{t}\,:\,W_{t}<\infty\\}\subseteq\mathbf{W}_{t}\,.$

We now propose that $\mathbf{L}_{t}$ is a proxy for $\mathbf{L}$ within some
time interval where an agent has exploded but not all agents have exploded. We
note that for small enough $t$ no agents will have exploded so that
$\mathbf{L}_{t}=\mathbf{W}_{t}$ and for very large $t$ all agents explode so
that $\mathbf{L}_{t}\rightarrow\emptyset$ (the empty set) as
$t\rightarrow\infty\,.$

We can simulate an agent $W_{t}$ of the feedback process and approximate an
agent $L_{t}$ of the loser process as follows:

  1. S.1

Set $t_{0}=0$ and $W_{0}=\omega_{0}$ and set a jump time upper bound
$t_{M}<\infty$ and a number of balls the agent collects upper bound
$\omega_{M}<\infty\,.$

  2. S.2

Choose $H_{\omega_{0}}\sim\text{Exp}(f(\omega_{0}))$ and set
$t_{1}=H_{\omega_{0}}$ and $W_{t_{1}}=\omega_{0}+1\,.$

  3. S.3

Repeat S.2 so that in general $t_{n+1}=t_{n}+H_{\omega_{n}}$ and
$W_{t_{n+1}}=W_{t_{n}}+1=\omega_{0}+(n+1)\,.$

  4. S.4

Stop at jump $n=k$ when either $t_{k}>t_{M}$ or $W_{t_{k}}>\omega_{M}\,.$

  5. S.5

A loser agent $L_{t}$ is approximated as an agent $W_{t}$ that has reached the
time threshold before the ball threshold ($t_{k}>t_{M}$ but
$W_{t_{k}}\leq\omega_{M}\,.$) In other words those agents $W_{t}$ that reach
the ball threshold before the time threshold ($t_{k}\leq t_{M}$ but
$W_{t_{k}}>\omega_{M}$) are assumed to be agents that have exploded by time
$t_{M}$ and are removed.

We can approximate the tail of the feedback process555Where
$\sum_{k=\omega_{0}}^{\omega_{0}-1}p_{t}(k):=0$ and
$\sum_{k=\omega_{0}}^{\omega_{0}-1}\hat{p}_{t}(k):=0\,.$
$\mathbb{P}(W_{t}\geq\omega)=1-\sum_{k=\omega_{0}}^{\omega-1}p_{t}(k)$ using
(8):

$\hat{\mathbb{P}}(W_{t}\geq\omega)=1-\sum_{k=\omega_{0}}^{\omega-1}\hat{p}_{t}(k)\,.$
(11)

From Corollary 6 we can see for finite $\omega$ that
$\lim_{t\rightarrow\infty}\mathbb{P}(W_{t}\geq\omega)=1\,.$ Figure 6 shows the
empirical tail of the aggregate of simulations S.1-S.4 of $W_{t}$ for power
law feedback (2) with $\gamma=2$ and Figure 6 shows it’s approximation (11).
We see a similar structure between the figures however the approximations are
not perfect.

Figure 8 shows the empirical tail of the aggregate of the same simulations in
Figure 6 but with S.5 added at each simulation to remove the explosive agents
and leave $L_{t}\,.$ Figure 8 shows the aggregate of simulations S.1-S.5 for
different $\gamma$ values for power law feedback (2) and plots the empirical
tail of $L_{t}\,.$ Both Figures 8 and 8 gives evidence that the losers scale
as $\omega^{-(\gamma-1)}$ in support of Corollary 2 (Theorem 4 in [13] applied
to the power law feedback function (2)) but for $N\geq 2$ agents.

Figure 5: Empirical tail of aggregate of $10^{4}$ simulations of $W_{t}$,
S.1-S.4, $\omega_{0}=1\,$, for power law feedback function (2) with $\eta=1$
and $\gamma=2\,$ until $t=t_{M}$ or $W_{t}=\omega_{M}=10^{4}\,$. The $t_{M}$
are chosen as $t_{\gamma}/10=0.1$ to $t_{\gamma}=1$ in increments of $0.1\,.$
Higher $t$ pushes the tail monotonically upwards to
$\mathbb{P}(W_{t}\geq\omega)=1\,$.

Figure 6: Plot of predicted tail (11) for $W_{t}\,,\,\omega_{0}=1$ for power
law feedback function (2) with $\eta=1$ and $\gamma=2\,$ and
$t=t_{\gamma}/10=0.1$ to $t=t_{\gamma}=1$ in increments of $0.1\,.$ Higher $t$
pushes the predictions monotonically upwards to
$\hat{\mathbb{P}}(W_{t}\geq\omega)=1\,$. We note there is error in the
prediction (negative $\hat{\mathbb{P}}(W_{t}\geq\omega)$) for small $t\,.$

Figure 7: Plot of empirical tail of $L_{t}\,,\,\omega_{0}=1$ for power law
feedback function (2) with $\eta=1$ and $\gamma=2\,.$ The $L_{t}$ are $W_{t}$
used in Figure 6 but adding step S.5 to exclude the $W_{t}$ that are likely to
have exploded by $t_{M}$ i.e. those that reach $\omega_{M}=10^{4}$ before
$t=t_{M}$ where $t_{M}=t_{\gamma}/10=0.1$ to $t_{\gamma}=1$ in increments of
$0.1\,.$ Higher $t=t_{M}$ pushes
$\hat{\mathbb{P}}(L_{t}\geq\omega)\,$ monotonically upwards to the dashed
black line proportional to $w^{-(\gamma-1)}\,$.

Figure 8: Empirical tail of $L_{t}$ from an aggregate of $10^{4}$ simulations
of S.1-S.5, $\omega_{0}=1\,$, for power law feedback function (2) with
$\eta=1$ and $\gamma$ going up in $0.2$ increments from $1.2$ to $2\,$ run
until $t_{M}=t_{\gamma}=1/(\gamma-1)$ but $W_{t}\leq\omega_{M}=10^{4}\,$. The
black dashed lines are proportional to $w^{-(\gamma-1)}\,$.

##  5 Conclusion

The form of the recursive mass function solution (5) to the master equation
for the feedback process is not particularly tractable. However the first term
(8) is analytical and for finite time and for the power law feedback function
(2) with $\gamma>1$ is a regularly varying sequence asymptotically dominated
by $\omega^{-\gamma}\propto 1/f(\omega)\,.$ We showed numerically in Section 3
that this first term provides a good approximation under certain
parametrisations. We also provided simulations in Section 4 suggesting the
tail of the losers scale as $\omega^{-(\gamma-1)}$ for general $N\geq 2$
agents. This gives partial evidence that the corollary to Theorem 4 in
Oliveira [13], stated in Section 2, holds for power law feedback and $N\geq 2$
agents. As power law distributions appear in many real world phenomena with
possible feedback mechanisms we believe these are interesting results.

## References

  * Apostol [1974] Apostol, T. M. (1974).  Mathematical Analysis.  Pearson, 2nd edition.
  * Bingham et al. [1989] Bingham, N. H., Goldie, C. M., Teugels, J. L., and Teugels, J. (1989).  Regular variation.  Number 27. Cambridge university press.
  * Clauset et al. [2009] Clauset, A., Shalizi, C. R., and Newman, M. E. (2009).  Power-law distributions in empirical data.  SIAM review, 51(4):661–703.
  * Drinea et al. [2002] Drinea, E., Frieze, A., and Mitzenmacher, M. (2002).  Balls and bins models with feedback.  In SODA, volume 2, pages 308–315.
  * Feller [1967] Feller, W. (1967).  An introduction to probability theory and its applications, Volume 1.  John Wiley & Sons, 3rd edition.
  * Forbes [2023] Forbes, S. (2023).  GitHub simulations code.  https://github.com/saf92/Urn-balls-in-bins-model.
  * Forbes and Grosskinsky [2022] Forbes, S. and Grosskinsky, S. (2022).  A study of UK household wealth through empirical analysis and a non-linear Kesten process.  Plos one, 17(8):e0272864.
  * Galambos and Seneta [1973] Galambos, J. and Seneta, E. (1973).  Regularly varying sequences.  Proceedings of the American Mathematical Society, 41(1):110–116.
  * Gardiner et al. [1985] Gardiner, C. W. et al. (1985).  Handbook of stochastic methods, volume 3.  springer Berlin.
  * Gottfried and Grosskinsky [2023] Gottfried, T. and Grosskinsky, S. (2023).  Asymptotics of generalized Pólya urns with non-linear feedback.  arXiv preprint arXiv:2303.01210.
  * Mori et al. [2020] Mori, T., Smith, T. E., and Hsu, W.-T. (2020).  Common power laws for cities and spatial fractal structures.  Proceedings of the National Academy of Sciences, 117(12):6469–6475.
  * Oliveira [2008] Oliveira, R. (2008).  Balls-in-bins processes with feedback and Brownian motion.  Combinatorics, Probability and Computing, 17(1):87–110.
  * Oliveira [2009] Oliveira, R. I. (2009).  The onset of dominance in balls-in-bins processes with feedback.  Random Structures & Algorithms, 34(4):454–477.
  * Pemantle [2007] Pemantle, R. (2007).  A survey of random processes with reinforcement.
  * Severo [1969] Severo, N. C. (1969).  A recursion theorem on solving differential-difference equations and applications to some stochastic processes.  Journal of Applied Probability, 6(3):673–681.
  * Stirzaker and Grimmett [1992] Stirzaker, D. and Grimmett, G. (1992).  Probability and random processes.
  * Vallejos et al. [2018] Vallejos, H. A., Nutaro, J. J., and Perumalla, K. S. (2018).  An agent-based model of the observed distribution of wealth in the United States.  Journal of Economic Interaction and Coordination, 13:641–656.
  * Vermeulen [2018] Vermeulen, P. (2018).  How fat is the top tail of the wealth distribution?  Review of Income and Wealth, 64(2):357–387.

## Appendix: Regularly Varying Functions and Sequences

For a background to regular variation see [2].

######  Definition 4.

A positive, measureable function $f$ defined on $[k,\infty)$ for some $k\geq
0$ is regularly varying if for all $\lambda>0$

$\lim_{x\rightarrow\infty}\frac{f(\lambda x)}{f(x)}=\lambda^{\rho}$

for some index $\rho\in\mathbb{R}\,.$

For a function $l$ satisfying the conditions in Definition 4 with the
particular case of $\rho=0$ so that

$\lim_{x\rightarrow\infty}\frac{l(\lambda x)}{l(x)}=1$

then $l$ is called slowly varying. In particular $l(x):=f(x)/x^{\rho}$ where
$f$ is some regularly varying function with index $\rho$ is a slowly varying
function. Thus any regularly function $f$ can be written as

$f(x)=l(x)x^{\rho}$

where $l$ is a slowly varying function. By the representation theorem we have
for all $\gamma>0$ that $l(x)x^{-\gamma}\rightarrow 0$ as $x\rightarrow\infty$
thus if the index is $\rho=-\gamma<0$ then the regularly varying function
$f(x)=l(x)x^{-\gamma}$ is dominated asymptotically by $x^{-\gamma}\,.$

Now suppose we have a sequence
$\\{\theta(\omega)\,:\,\omega=\omega_{0},\omega_{0}+1,\dots\\}:=\\{\theta(\omega)\\}$
of positive terms.

######  Definition 5 (See [8]).

We call the sequence $\\{\theta(\omega)\\}$ a regularly varying sequence if
there exists a sequence $\\{\alpha(\omega)\\}$ of positive terms such that

  1. 1.

$\theta(\omega)\simeq k\alpha(\omega)\quad\text{some }k>0$

  2. 2.

$\lim_{\omega\rightarrow\infty}\omega(1-\alpha(\omega-1)/\alpha(\omega))=\rho\quad\text{some
index }\rho\in\mathbb{R}$

If $\\{\theta(\omega)\\}$ is a regular varying sequence with index $\rho$ then
it can be embedded into a regularly varying function with index $\rho\,$ [8].
In particular the function $f(x)=\theta(\lfloor x\rfloor)$ for
$x\in[\omega_{0},\infty)$ is a regularly varying function with index $\rho\,$
[8].

Let us show that the sequence $\\{\hat{p}(\omega)\\}$ defined by (8) is a
regularly varying sequence. With

$\alpha(\omega)=\left(\prod_{j=\omega_{0}+1}^{\omega}\frac{1}{1-(\omega_{0}/j)^{\gamma}}\right)\frac{1}{\omega^{\gamma}}$

then $\\{\alpha(\omega)\\}$ is a positive sequence and we see

$\hat{p}(\omega)\simeq
e^{-\eta\omega_{0}^{\gamma}t}\omega_{0}^{\gamma}\alpha(\omega)$

satisfies the first condition of a regularly varying sequence. Now for
$\gamma>1$ we have

$\displaystyle\omega(1-\alpha(\omega-1)/\alpha(\omega))$
$\displaystyle=\omega\left(1-\frac{1/(\omega-1)^{\gamma}}{1/(1-(\omega_{0}/\omega)^{\gamma})\cdot
1/\omega^{\gamma}}\right)$
$\displaystyle=\omega\left(1-\frac{\omega^{\gamma}-\omega_{0}^{\gamma}}{(\omega-1)^{\gamma}}\right)$
$\displaystyle=\omega\left(1-\frac{1}{(1-1/\omega)^{\gamma}}-\frac{\omega_{0}}{(\omega-1)^{\gamma}}\right)$
$\displaystyle=\omega\left(1-(1+\gamma/\omega+\mathcal{O}(1/\omega^{\gamma}))-\frac{\omega_{0}}{(\omega-1)^{\gamma}}\right)$
$\displaystyle=-\gamma+\mathcal{O}(1/\omega^{\gamma-1})$
$\displaystyle\rightarrow-\gamma\quad\text{ as }\omega\rightarrow\infty\,.$

Thus the second condition is also satisfied and so $\\{\hat{p}(\omega)\\}$ is
a regularly varying sequence and thus can be embedded into a regularly varying
function with index $-\gamma\,.$