2.1. General notation

Let ${\mathbb R}$, ${\mathbb R}^+$, ${\mathbb N}$, and ${\mathbb N}^+$ denote respectively the sets of real numbers, nonnegative real numbers, natural integers, and positive integers, respectively. For a and b in ${\mathbb N}$, denote by $[\![a,b]\!]$ the integer interval $[a,b]\cap {\mathbb N}$. We let $a\wedge b$ and $a\vee b$ denote respectively the minimum and the maximum of two numbers $a,b\in{\mathbb R}$.

Given a finite set B, we denote by $\mathscr{M\,}(B)$ the set of probability measures on B having B as exact support. Denote by $\bar B$ the complement of B (within a set of reference that is fixed by the context).

Let $q\in {\mathbb N}^+$. We write any vector $u\in{\mathbb R}^q$ as $u=(u(1),...,u(q))$. We denote by $\preceq$ the coordinate-wise partial ordering on $\mathbb R^q$; that is, for any $u,v\in{\mathbb R}^q$ we write $u\preceq v$ if and only if $u(i) \le v(i)$ for any $i\in[\![ 1,q ]\!]$. For any $i\in [\![ 1,q ]\!]$, let $\textbf{e}_i$ denote the vector in $\mathbb{N}^{q}$ with components $\textbf{e}_i(j)=\delta_{ij},\;j\in [\![ 1,q ]\!]$.

The null vector in $\mathbb{N}^{q}$ is denoted by $\mathbf 0$. The norm of any vector $u \in {\mathbb N}^q$ is denoted by $\parallel u \parallel =\sum\limits_{i=1}^{q} u(i)$. Let A be a finite set. The cardinality of A is denoted by $|A|$. We let $A^*$ denote the free monoid associated to A, i.e. the set of finite words over the alphabet A. The length of a word $w\in A^*$ is denoted by $|w|$. We write any word $w\in A^*$ as $w=w(1)w(2)...w(|w|)$. For any $a\in A$ we denote by $|w|_a$ the number of occurrences of the letter a in the word w. Having set an ordering on A, and denoting by $1,2,...,|A|$ the elements of A in increasing order, we define the commutative image of a word $w\in A$ as the ${\mathbb N}^{|A|}$-valued vector [w] given by $[w]=\left(|w|_1,...,|w|_{|A|}\right)$, i.e. the vector whose ith coordinate is the number of occurrences of the letter i in the word w. Finally, for a word $w\in A^*$ and an ordered list of letters $(a,b,c,...)$ appearing in that order in w, we denote by $w\setminus_{(a,b,c,...)}$ the word of $A^*$ obtained by just deleting the letters $a,b,c,...$ in w.

2.2. Hypergraphs

For easy reference, let us first introduce the basics of hypergraph theory that will be used in this paper. A thorough presentation of the topic can be found e.g. in [Reference Berge4].

• • The finite set V is the set of nodes of $\mathbb H$. We let $q({\mathbb H})$ be the cardinality of V, and say that the hypergraph is of order $q({\mathbb H})$.

• • ${\mathcal H}\,\;:\!=\;\left\{H_1,...,H_{m({\mathbb H})}\right\}$ is a set of subsets of V, called hyperedges of ${\mathbb H}$, such that $\bigcup_{i=1}^{m({\mathbb H})}H_i={V}$.

We then say that the hypergraph is simple (or a Sperner family) if $H_i\subset H_j$ implies $i=j$ for all $i,j \in [\![ 1,m({\mathbb H}) ]\!]$, i.e., no hyperedge is included in another one. Whenever no ambiguity is possible, we often write $q\,\;:\!=\;q({\mathbb H})$, $m\,\;:\!=\;m({\mathbb H})$. A sub-hypergraph of ${\mathbb H}$ is a hypergraph ${\mathbb H}'=(V,{\mathcal H}')$ such that ${\mathcal H}' \subset {\mathcal H}$.

Definition 2. Let $\mathbb H=({V},{\mathcal H})$ be a hypergraph. The rank of $\mathbb H$ is the largest size of a hyperedge, i.e. the integer $r(\mathbb H)=\max_{j\in[\![ {1,m({\mathbb H})}]\!]}|H_j|$. The anti-rank of $\mathbb H$ is defined as $a(\mathbb H)=\min_{j\in[\![ {1,m({\mathbb H})}]\!]}|H_j|$, i.e. the smallest size of a hyperedge. If there exists a constant r such that $r(\mathbb H)= a(\mathbb H)=r$, then $\mathbb H$ is said to be r-uniform. The degree of a node $i\in {V}$ is the number of hyperedges to which i belongs, i.e.

\begin{equation*}d(i)=\sum_{\ell=1}^{m({\mathbb H})}\mathbb {1}_{H_{\ell}}(i).\end{equation*}

If there exists a constant d such that $d(i)=d$ for any i, then $\mathbb H$ is said to be d-regular.

Example 1. Figure 1 represents the hypergraph $\mathbb{H}=({V},{\mathcal H})$ with ${V}=\{1,2,3,4\}$ and ${\mathcal H}=\left\lbrace\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\right\rbrace$. The hypergraph ${\mathbb H}$ is of order 4; it is 3-uniform since all hyperedges are of cardinality 3, and 3-regular because all nodes are of degree 3 (they all belong to exactly 3 hyperedges). As all hyperedges of cardinality 3 appear in ${\mathcal H}$, this hypergraph is said to be complete 3-uniform of order 4.

Figure 1.

Complete 3-uniform hypergraph of order 4.

As is easily seen, any 2-uniform hypergraph is a graph, whose edges are the elements of ${\mathcal H}$, and any simple and connected hypergraph contains no isolated node, i.e. has anti-rank at least 2.

For any set $A \subset {V}$, we denote by

(1) \begin{equation}{\mathcal H}(A) = \left\{H \in {\mathcal H}\;:\; H \cap A\ne \emptyset\right\}\end{equation}

the set of hyperedges that intersect A. With some abuse of notation, for any node $i\in{V}$ we write ${\mathcal H}(i)\,\;:\!=\;{\mathcal H}(\{i\})$.

Throughout this paper, all considered hypergraphs are simple and connected.

3.1. Stochastic matching model on a hypergraph

A (discrete-time, hypergraphical) stochastic matching model is specified by a triple $(\mathbb H,\Phi,\mu)$, such that

• • $\mathbb H=({V},{\mathcal H})$ is a simple and connected hypergraph, termed the matching hypergraph of the model;

• • $\Phi$ is a matching policy, precisely defined in Section 3.3 below;

• • $\mu$ is an element of $\mathscr{M\,}({V})$.

The matching model $(\mathbb H,\Phi,\mu)$ is then defined as follows. At each time point $n\in{\mathbb N}$, the following occurs:

1. 1. An item enters the system. Its class $V_n$ is drawn from the measure $\mu$ on V, independently of everything else. (Thus the sequence of classes of incoming items $\left\{{V_n},\,n\in{\mathbb N}\right\}$ is independent and identically distributed (i.i.d.) with common distribution $\mu$.)

2. 2. The incoming item then faces the following alternative:

3. (i) If there exists in the buffer at least one set of items whose respective set of classes forms, together with $V_n$, a hyperedge of ${\mathcal H}$, then it is the role of the matching policy $\Phi$ to select one of these sets of classes, say $\{i_1,...,i_m\}$. Then the $m+1$ items of respective classes $i_1,...,i_m,V_n$ are matched together and leave the system right away. Defining $H_j\,\;:\!=\;\{i_1,...,i_m,V_n\} \in {\mathcal H}$, we then say that $V_n$ completes a matching of type $H_j$ at time n, and we write $H(n)=H_j$ for the matching performed at n.

4. (ii) Else, the item is stored in the buffer of the system, waiting for a future match, and we write $H(n)=\emptyset$.

Example 3. Consider again the matching hypergraph $\mathbb{H}=({V},{\mathcal H})$ of Figure 1. The dynamic matchings of the realization $\left\{{V_n(\omega)},\,n\in{\mathbb N}\right\}=2,3,4,1,1,2,3,3,4,2,2,...$ is represented in Figure 2.

Figure 2.

The matching model in action, on the matching hypergraph of Figure 1.

3.2. System dynamics

Fix a hypergraphical matching model on a hypergraph ${\mathbb H}$ of order q. Define for all $n\in{\mathbb N}$ the ${\mathbb N}^{q}$-valued random variable $X_n=\left(X_n(1),...,X_n(q)\right),$ where, for each $i \in {V}$, $X_n(i)$ is the number of items of class i in the buffer at time n (taking into account the arrival occurring at time n). The vector $X_n$ is then called class-content of the system at time n. For any subset B of V, define $X_n(B)$ to be the class-content of elements of B:

\begin{equation*}X_n(B)=\sum_{i\in B}X_n(i),\end{equation*}

in such a way that the total number of items in the buffer at time n is given by $\parallel X_n \parallel$. The buffer-content of the system at time n is the word of $V^*$ whose letters are the classes of the items in the buffer, in increasing order of their arrivals. That is,

\begin{equation*}W_n = W_n(1) W_n(2) ..... W_n(|W_n|),\end{equation*}

where for any $\ell$, $W_n(\ell)$ is the class of the $\ell$th oldest item in line. Notice that $X_n$ is nothing but the commutative image of $W_n$, i.e. $X_n=[W_n],\,n\in {\mathbb N}.$

To simply describe the dynamics of the processes $\left\{{X_n},\,n\in{\mathbb N}\right\}$ and $\left\{{W_n},\,n\in{\mathbb N}\right\}$, for any $u\in {\mathbb N}^q$ and $H \in {\mathcal H}$ we define the following elements of $\{0,1\}^q$: $p_u$ is the vector of coordinates $p_u(i)=\mathbb {1}_{\{u(i)>0\}}$, $i\in [\![ 1,q ]\!]$, and $\gamma_H$ is the trace of H, i.e. the vector in $\{0,1\}^q$ defined by $\gamma_H(i) = \mathbb {1}_{H}(i)$ for all $i \in [\![ 1,q ]\!]$. We then set

\begin{equation*}\Gamma(u) = \left\{H \in {\mathcal H}:\, p_u\succeq \gamma_H\right\}.\end{equation*}

In other words, a hyperedge H belongs to $\Gamma(u)$ if and only if $u(i)>0$ for any $i\in H$.

3.3. Matching policies

Formally, an admissible matching policy is a rule of choice, for any $n\in{\mathbb N}$, of the item(s) matched with the incoming item at time $n+1$, in case of a multiple choice, that can be made solely on the basis of the knowledge of the buffer-content $W_n$, on the class $V_{n+1}$ of the incoming item, and possibly on a independent toss. Notice that at all n, $\Gamma\left(X_n+\textbf{e}_{V_{n+1}}\right)=\Gamma\left([W_n]+\textbf{e}_{V_{n+1}}\right)$ represents the (possibly empty) set of all hyperedges in ${\mathcal H}$ that can be completed by the arrival of $V_{n+1}$ in a system having buffer-content $W_n$ at time n. Using queueing-related terminology, all admissible matching policies we consider hereafter are furthermore assumed ‘non-idling’, in the sense that at any n, a match is necessarily performed whenever $\Gamma\left(X_n+\textbf{e}_{V_{n+1}}\right)$ is non-empty.

3.3.1 Matching policies that depend on the arrival times

First come, first matched. In the first come, first matched (fcfm) policy, the chosen match of the incoming item $V_{n+1}$ at time $n+1$ is the hyperedge containing the oldest item in line among all hyperedges that can be completed by $V_{n+1}$. Specifically,

\begin{equation*}W_{n+1}=\left\lbrace \begin{array}{ll}W_nV_{n+1}& \qquad \textrm{if}\;\Gamma\left([W_n]+\textbf{e}_{V_{n+1}}\right)=\emptyset;\\[5pt] W_nV_{n+1}\setminus_{(i,j,...,k)}& \qquad \mbox{else, for }H(n)=\{i,j,...,k\}\in \Gamma\left([W_n]+\textbf{e}_{V_{n+1}}\right),\end{array}\right.\end{equation*}

where, in the case where $\left |\Gamma\left(X_n+\textbf{e}_{V_{n+1}}\right) \right| \ge 2$, i.e. there is more than one possible matching containing $V_{n+1}$ at $n+1$, $H(n)=\{i,j,...,k\}$ is the hyperedge whose first element i appearing in $W_n$ appears first among all elements of $\Gamma\left([W_n]+\textbf{e}_{V_{n+1}}\right).$

Last come, first matched. Likewise, in the last come, first matched (lcfm) policy, the newly arrived item at $n+1$ is matched to form the hyperedge containing the youngest possible element, i.e.

\begin{equation*}W_{n+1}=\left\lbrace \begin{array}{ll}W_nV_{n+1}& \qquad \textrm{if}\;\Gamma\left([W_n]+\textbf{e}_{V_{n+1}}\right)=\emptyset;\\[5pt] W_nV_{n+1}\setminus_{(i,j,...,k)}& \qquad \mbox{else, for }H(n)=\{i,j,...,k\} \in \Gamma\left([W_n]+\textbf{e}_{V_{n+1}}\right),\end{array}\right.\end{equation*}

where $H(n)=\{i,j,...,k\}$ is the hyperedge whose last element k appearing in $W_n$ appears last among all elements of $\Gamma\left([W_n]+\textbf{e}_{V_{n+1}}\right).$

3.3.2 Matching policies that depend only on the class-content

A wide class of natural matching policies can be implemented given the sole knowledge of the class-content upon arrival times. In such cases we have, for all n,

(2) \begin{equation}X_{n+1}=\left\lbrace \begin{array}{ll}X_n+\textbf{e}_{V_{n+1}} & \qquad \textrm{if}\;\Gamma\left(X_n+\textbf{e}_{V_{n+1}}\right)=\emptyset;\\[5pt] X_n+\textbf{e}_{V_{n+1}} - \gamma_{H(n)}& \qquad \mbox{else, for some }H(n)\in \Gamma\left(X_n+\textbf{e}_{V_{n+1}}\right),\end{array}\right.\end{equation}

where the choice of the hyperedge H(n) depends on the matching policy. Several examples are provided below.

Match the longest. The matching policy $\Phi$ is match the longest (denoted by ml) if, for all n, the match realized is that of the hyperedge having the most elements in storage at n. In other words, the chosen hyperedge H(n) in the second case of (2) satisfies

\begin{equation*}H(n) = \mbox{argmax}\left\{X_n(H)\,:\,H \in \Gamma\left(X_n+\textbf{e}_{V_{n+1}}\right)\right\},\end{equation*}

ties being broken uniformly at random (and independently of everything else) among hyperedges.

Remark 1. Observe that ml is a particular case of the class of the ‘max weight’ used in [Reference Nazari and Stolyar20], constrained to be non-idling (i.e. whenever the entering item can be matched, it is matched right away) and with constant rewards and coefficients in Equation (5) therein.

Match the shortest. Analogously, the match the shortest policy (denoted by ${ms})$ corresponds to the choice

\begin{equation*}H(n) = \mbox{argmin}\left\{X_n(H)\,:\,H \in \Gamma\left(X_n+\textbf{e}_{V_{n+1}}\right)\right\},\end{equation*}

ties being broken uniformly at random, as above.

Fixed priority. In the context of fixed priorities, each vertex $i \in {V}$ is assigned a full ordering of the hyperedges and chosen to be matched with the first matchable hyperedge following this order. Formally, to each node i is associated a permutation $\sigma_i$ of the index set $[\![ 1,d(i) ]\!]$, and if we write ${\mathcal H}(i)=\left\{H_{i_1},H_{i_2},...,H_{i_{d(i)}}\right\}$, then at any time n,

(3) \begin{equation}H(n) = H_{i_{\sigma_i(j)}},\mbox{ where }j=\mbox{min}\left\{k\in [\![ 1,d(i) ]\!]\,:\,X_n\left(H_{i_{\sigma_i(k)}}\right)>0\right\}.\end{equation}

Random. For this matching policy, the priority order defined above is not fixed, and is drawn uniformly at random upon each arrival; i.e. for any n, H(n) is defined as in (3), for a permutation $\sigma_i(n)$ that is drawn, independently of everything else, uniformly at random among all permutations of $[\![ 1,d(i) ]\!]$.

It is easily seen that under any admissible policy the sequence $\left\{{W_n},\,n\in{\mathbb N}\right\}$ is a $V^*$-valued Markov chain with respect to the filtration generated by the sequence $\left\{{V_n},\,n\in{\mathbb N}\right\}$. Additionally, in the cases where $\Phi=$ ml, ms, a fixed priority, or a random policy, the sequence $\left\{{X_n},\,n\in{\mathbb N}\right\}$ is an ${\mathbb N}^{|V|}$-valued Markov chain.

3.4. Stability of the matching model

We say that the matching model $(\mathbb H,\Phi,\mu)$ is stable if the Markov chain $\left\{{W_n},\,n\in{\mathbb N}\right\}$ (and thereby $\left\{{X_n},\,n\in{\mathbb N}\right\}$) is positive recurrent. For a given hypergraph $\mathbb H=({V},{\mathcal H})$ and a given matching policy $\Phi$, we define the stability region associated to $\mathbb H$ and $\Phi$ as the set of probability measures on V rendering the model $(\mathbb H,\Phi,\mu)$ stable, i.e.

\begin{equation*}{Stab}(\mathbb H,\Phi)=\left\{\mu \in\mathscr{M\,}({V}):\;(\mathbb H,\Phi,\mu)\mbox{ is stable}\right\}.\end{equation*}

We then say that a hypergraph ${\mathbb H}$ is stabilizable if ${Stab}(\mathbb H,\Phi)$ is non-empty for some matching policy $\Phi$. If not, ${\mathbb H}$ is said to be non-stabilizable.

4.1. General conditions

We start by introducing several ‘universal’ stability conditions. Fix a hypergraph $\mathbb H=({V},{\mathcal H})$ throughout the section.

Definition 5. We say that $I \subset V$ is an independent set of ${\mathbb H}$ if I does not include any hyperedge of ${\mathbb H}$, i.e, for any $H\in {\mathcal H}$, $H\cap \bar I \ne \emptyset$. We also let ${\mathcal I}({\mathbb H})$ be the set of all independent sets of ${\mathbb H}$.

Let us define, for any $\mu\in\mathscr{M\,}(V)$ and any $B\subset V$, the set

(5) \begin{equation}L_\mu(B) = \mbox{argmin} \left\{\mu(j)\,:\,j\in B\right\}, \quad B \subset V.\end{equation}

To clarify the exposition of the following result, we need to introduce the following notion.

• • $v_{_{H}}$ is of degree 1, i.e., H is the only hyperedge to which $v_{_{H}}$ belongs;

• • $L_{\mu}(H)=\{v_{_{H}}\}$, i.e., $v_{_{H}}$ is the only minimum of $\mu$ over the set H.

An independent set $I\in{\mathcal I}({\mathbb H})$ that is not $\mu$-minimal is said to be non-$\mu$-minimal. We let $\mathcal I_\mu({\mathbb H})$ be the set of $\mu$-minimal independent sets of ${\mathbb H}$, and ${\mathcal I^\prime_\mu({\mathbb H})}$ the set of non-$\mu$-minimal independent sets of ${\mathbb H}$, that is, the complement of ${\mathcal I}_\mu({\mathbb H})$ in ${\mathcal I}({\mathbb H})$.

In other words, a $\mu$-minimal independent sets gathers nodes that are the only minimum of $\mu$ over the only hyperedge they belong to. Notice that the collection ${\mathcal I}_\mu({\mathbb H})$ can be empty. This is the case if and only if all nodes are of degree at least 2, or all nodes of degree 1 are not the only minimum of $\mu$ on the single hyperedge they belong to. Observe the following characterization.

Lemma 1. Let ${\mathbb H}=(V,{\mathcal H})$ be a hypergraph, and let ${\mathcal H}=\{H_1,...,H_m\}$. An independent set $I=\{v_1,...,v_p\}$ is $\mu$-minimal if and only if for all n and all $k_1,...,k_m$ such that $k_j\in L_\mu(H_j)$ for all j,

(6) \begin{equation}A_n(I) = \sum_{j=1}^m|H_j\cap I|A_n(k_j).\end{equation}

Proof. First, it is clear that if $I\in{\mathcal I}_\mu({\mathbb H})$, then $m\ge p$ and the mapping

(7) \begin{equation}\varphi:\left\{\begin{array}{ll}\left\{j\in [\![ 1,m ]\!]\,:\,I\cap H_j \ne \emptyset\right\} &\quad\longrightarrow [\![ 1,p ]\!],\\j &\quad\longmapsto i\,:\,L_\mu(H_j)=H_j\cap I = \{v_{i}\}\end{array}\right.\end{equation}

is bijective. Thus we have, almost surely for all n,

\begin{equation*}A_n(I) = \sum_{j=1}^m A_n(v_{\varphi(j)})=\sum_{\substack{j\in[\![ 1,m]\!] :\\H_j\cap I\ne\emptyset}} |H_j\cap I|A_n(v_{\varphi(j)})=\sum_{j=1}^m |H_j\cap I|A_n(k_j).\end{equation*}

Let us now assume that $I\in{\mathcal I}^\prime_\mu({\mathbb H})$. Then the following hold:

• • If some hyperedge $H_j$ is such that $|H_j\cap I|\ge 2$, then upon each arrival of an element of class $k_j$, the right-hand side of (6) increases by $|H_j\cap I|$, while the left-hand side increases by 1 if $k_j \in I$, or by 0 otherwise.

• • If, for some hyperedge $H_j$ intersecting I, there exists $k_j \in L_\mu(H_j) \cap \bar I$, then upon each arrival of a class-$k_j$ item, the right-hand side of (6) increases while the left-hand side does not.

• • Finally, if for all $j\in[\![ 1,m ]\!]$, $|H_j\cap I| \le 1$, and for all j such that $|H_j\cap I| = 1$, $L_\mu(H_j)=\{v_{\varphi(j)}\}$ (again defining $\varphi$ by (7)), then if $\varphi(j)=\varphi(l)$ for some $l\ne j$, upon each arrival of a class-$v_{\varphi(j)}$ item, the right-hand side of (6) increases by 2 while the left-hand side increases by 1.

In all cases, (6) cannot hold for all n, which concludes the proof.

Now define the following set of measures:

\begin{equation*} \mathscr{N\,}_1(\mathbb H) = \left\{\mu\in\mathscr{M\,}({V}):\mbox{{for all }}I\in{\mathcal I}^\prime_\mu({\mathbb H}),\,\mu(I)\;<\sum_{H\in {\mathcal H}}\left|H \cap I\right|\min_{k \in H}\mu(k)\right\}. \end{equation*}

We have the following result.

Proposition 1. For any connected hypergraph $\mathbb H$ and any admissible matching policy $\Phi$,

\begin{equation*}{Stab}({\mathbb H},\Phi) \subset \mathscr{N\,}_1(\mathbb H).\end{equation*}

Proof. Fix ${\mathbb H}=(V,{\mathcal H})$ and an admissible policy $\Phi$. Denote by $H_1,...,H_m$ the hyperedges of ${\mathbb H}$. Suppose that $\mu \in \mathscr{M\,}(V)$ is such that there exists an independent set $I\in {\mathcal I}^\prime_\mu({\mathbb H})$ such that

(8) \begin{equation}\mu(I) > \sum\limits_{H\in{\mathcal H}}\left|H \cap I\right|\min_{k \in H} \mu(k).\end{equation}

For any $i\in[\![ 1,m ]\!]$ and any $k_i\in L_\mu(H_i)$ we have that

\begin{equation*}M_n(H_i) \le \min_{k \in H_i} A_n(k) \le A_n\left(k_i\right),\quad n\ge 0.\end{equation*}

Thus, from the equality in (4), for any $k_1,...,k_m$ such that $k_i\in L_\mu(H_i)$ for all i, we have that

(9) \begin{equation}\frac{X_{n}(I)}{n} \ge \frac{A_{n}(I)}{n} - \sum\limits_{i=1}^{m}\left|H_i \cap I\right| \frac{A_{n}\left(k_i\right)}{n},\quad n\ge 1.\end{equation}

The strong law of large numbers (SLLN) applied to the right-hand side of (9) implies that for any such $k_1,...,k_m$,

\begin{equation*}\limsup_{n} \frac{X_{n}(I)}{n}\ge \mu(I) - \sum\limits_{i=1}^m\left|H_i \cap I\right| \mu\left(k_i\right) = \mu(I) - \sum\limits_{H\in{\mathcal H}}\left|H \cap I\right| \min_{k\in H}\mu\left(k\right)>0,\end{equation*}

so that $X_n(I)$ goes almost surely to infinity, which (as $X_n=[W_n]$ for all n) implies the transience of $\left\{{W_n},\,n\in{\mathbb N}\right\}$.

Assume now that $\mu$ is such that for some independent set $I\in {\mathcal I}^\prime_\mu({\mathbb H})$, equality holds in (8). Then, for any $k_1,...,k_m$ such that $k_j\in L_\mu(H_j)$ for all j, the Markov chain $\left\{{Y_n},\,n\in{\mathbb N}\right\}$ defined as

\begin{equation*}Y_n =A_n(I)\;-\;\sum\limits_{j=1}^m\left|H_j \cap B\right|A_n\left(k_j\right),\quad n\in{\mathbb N},\end{equation*}

is a random walk with drift 0 that is different from the identically null process, in view of Lemma 1. Hence $\left\{{Y_n},\,n\in{\mathbb N}\right\}$ is null recurrent. If the chain $\left\{{W_n},\,n\in{\mathbb N}\right\}$ were positive recurrent, the sequence $\left\{{X_n},\,n\in{\mathbb N}\right\}$ would visit the state $\mathbf 0$ infinitely often, with inter-passage time at $\mathbf 0$ of finite expectation. Thus from (9), the sequence $\left\{{Y_n},\,n\in{\mathbb N}\right\}$ would be positive recurrent, an absurdity. This concludes the proof.

Define the following sets of measures:

\begin{align*} \mathscr {N\,}^{\tiny{+}}_1(\mathbb H)&= \left\{\mu\in\mathscr{M\,}({V}):\, \forall I \in {\mathcal I}({\mathbb H}),\,\mu(I)\;<\sum_{H\in {\mathcal H}}\left|H \cap I\right|\min_{k \in H \cap \bar I}\mu(k)\right\};\\ \mathscr{N\,}_1^{\tiny{++}}({\mathbb H}) &= \left\{\mu\in\mathscr{M\,}({V}):\,\forall B \subset V,\,\mu(B)\;\le \sum_{H\in {\mathcal H}}\left|H \cap B\right|\min_{k \in H}\mu(k)\right\}.\end{align*}

We have the following result.

Corollary 1. For any connected hypergraph $\mathbb H$ and any admissible matching policy $\Phi$,

\begin{equation*}{Stab}({\mathbb H},\Phi) \subset \mathscr{N\,}_1^{\tiny{+}}(\mathbb H)\cap \mathscr{N\,}_1^{\tiny{++}}(\mathbb H).\end{equation*}

Proof. We simply show that $\mathscr{N\,}_1(\mathbb H)$ is included in $\mathscr{N\,}_1^{\scriptsize{+}}(\mathbb H)\cap \mathscr{N\,}_1^{\tiny{++}}(\mathbb H)$. Again set ${\mathcal H}=\{H_1,...,H_m\}$ and fix $\mu \in \mathscr{N\,}_1(\mathbb H)$. To show that $\mu\in\mathscr{N\,}_1^{\tiny{+}}(\mathbb H)$, first observe that for any independent set $I=\{v_1,...,v_p\}\in{\mathcal I}_\mu({\mathbb H})$, for any hyperedge $H_j$ intersecting with I, we have that

\begin{equation*}\min_{k\in H_j}\mu(k) = \mu(v_{\varphi(j)}) < \min_{k\in H_j\cap \bar I}\mu(k).\end{equation*}

Therefore,

\begin{equation*}\mu(I) = \sum_{i=1}^p \mu(v_i) = \sum_{j=1}^m |H_j\cap I| \mu(v_{\varphi(j)}) < \sum_{H \in{\mathcal H}} |H\cap I| \min_{k\in H\cap \bar I}\mu(k),\end{equation*}

whereas if $I\in{\mathcal I}^\prime_\mu({\mathbb H})$, as $\mu\in\mathscr{N\,}_1(\mathbb H)$ we have that

\begin{equation*}\mu(I) < \sum_{H \in{\mathcal H}} |H\cap I| \min_{k\in H}\mu(k) \le \sum_{H \in{\mathcal H}} |H\cap I| \min_{k\in H\cap \bar I}\mu(k),\end{equation*}

and hence $\mu\in \mathscr{N\,}_1^{\tiny{+}}(\mathbb H)$.

It remains to show that $\mu\in \mathscr{N\,}_1^{\tiny{++}}(\mathbb H)$, and for this, we first observe the following:

(10) \begin{equation}\mbox{For all } I \in {\mathcal I}({\mathbb H}),\,\mu(I)\;\le \sum_{H\in {\mathcal H}}\left|H \cap I\right|\min_{k \in H}\mu(k).\end{equation}

To see this, it suffices to observe that for any independent set $I\in{\mathcal I}_\mu({\mathbb H})$, recalling (7),

\begin{equation*}\mu(I) = \sum_{j=1}^m \mu(v_{\varphi(j)})=\sum_{\substack{j\in[\![ 1,m]\!] :\\H_j\cap I\ne\emptyset}} |H_j\cap I|\mu(v_{\varphi(j)})=\sum_{j=1}^m |H_j\cap I|\mu(k_j)=\sum_{H\in {\mathcal H}} |H\cap I|\min_{k\in H}\mu(k);\end{equation*}

hence (10). Now fix B, a subset of V that is not an independent set of ${\mathbb H}$. Then we construct by induction the family of sets $B\,\;:\!=\;B_0 \supset B_1 \supset B_2 \supset ...\supset B_r$, where r is properly defined below, as follows: for any $i\ge 0$, if $B_i$ is not an independent set of ${\mathcal I}({\mathbb H})$, then we take an arbitrary hyperedge $H_{j_i} \in{\mathcal H}$ such that $H_{j_i}\subset B_i$, and set $B_{i+1}=B_i \setminus\{k_i\}$, for an arbitrary $k_i\in L_\mu(H_{j_i})$. Then there exists an integer $r \le |B|-1$ such that $B_r$ is an independent set of ${\mathcal I}({\mathbb H})$, and we stop the construction at this point. Observe that for any $i\in[\![ 0,r-1 ]\!]$,

(11) \begin{equation}\mu(B_{i+1})\;\le \sum_{H\in {\mathcal H}}\left|H \cap B_{i+1}\right|\min_{k \in H}\mu(k) \,\,\Longrightarrow \,\,\mu(B_{i})\;\le \sum_{H\in {\mathcal H}}\left|H \cap B_{i}\right|\min_{k \in H}\mu(k).\end{equation}

To see this, fix i and suppose that the left-hand side of the above holds true. Then we have

(12) \begin{equation}\mu(B_{i}) = \mu(B_{i+1}) +\mu(k_i),\end{equation}

and on the other hand,

(13) \begin{align}\sum_{H\in {\mathcal H}}\left|H \cap B_{i}\right|\min_{k \in H}\mu(k) &= \sum_{H\in \overline{{\mathcal H}(k_i)}}\left|H \cap B_{i}\right|\min_{k \in H}\mu(k) + \sum_{H\in {\mathcal H}(k_i)}\left|H \cap B_{i}\right|\min_{k \in H}\mu(k) \nonumber\\ &= \sum_{H\in \overline{{\mathcal H}(k_i)}}\left|H \cap B_{i+1}\right|\min_{k \in H}\mu(k) + \sum_{H\in {\mathcal H}(k_i)}\left(\left|H \cap B_{i+1}\right|+1\right)\min_{k \in H}\mu(k)\nonumber\nonumber\\ &= \sum_{H\in {\mathcal H}}\left|H \cap B_{i+1}\right|\min_{k \in H}\mu(k) + \sum_{H\in {\mathcal H}(k_i)}\mu(k_H),\end{align}

where for any $H\in{\mathcal H}(k_i)$, $k_H$ is an arbitrary element of $L_\mu(H)$. But $\mu(k_i)$ is less than or equal to the second term of the latter sum, because $\mu(k_i)=\mu(k_{H_i})$, and we assumed that $B_{i+1}$ is less than the first term. This completes the proof of (11) in view of (13). To conclude, as $B_r \in {\mathcal I}({\mathbb H})$ and in view of (10), we have that $\mu(B_r) \le \sum_{H\in {\mathcal H}}\left|H \cap B_{r}\right|\min_{k \in H}\mu(k)$, which implies, by an immediate induction using (11), that $\mu(B) \le \sum_{H\in {\mathcal H}}\left|H \cap B\right|\min_{k \in H}\mu(k)$. This completes the proof.

Remark 2. (Graphical case.) Let us consider the special case where ${\mathbb H}=(V,{\mathcal H})$ is a graph. Then it is shown in Proposition 2 of [Reference Mairesse and Moyal16] that the stability region of the model is included in the set

\begin{equation*}{Ncond}({\mathbb H})=\left\{\mu \in \mathscr{M\,}(V)\,:\;\forall I\in{\mathcal I}({\mathbb H}),\,\mu(I)<\mu({\mathcal E}(I))\right\},\end{equation*}

where for any set $B\subset V$, ${\mathcal E}(B)=\left\{j\in V\,:\,(i,j)\in {\mathcal H}\mbox{ for some }i\in B\right\}.$ It is then easy to check by hand that Ncond$({\mathbb H})$ is included in $\mathscr{N\,}^{++}_1({\mathbb H})$. Indeed, if we let $\mu\in {Ncond}({\mathbb H})$ and $I\in{\mathcal I}({\mathbb H})$ (meaning that I is an independent set of the graph ${\mathbb H}$, in the usual sense), then, for any edge $H\in{\mathcal H}$, $|H\cap I| =1$ if I contains a vertex of the edge H, and 0 otherwise, so we get that

\begin{equation*}\sum_{H\in {\mathcal H}}\left|H \cap I\right|\min_{j \in H \cap \bar I}\mu(j) = \sum_{(i,j)\in {\mathcal H}\,:\,i\in I}\mu(j) \ge \sum_{j\in{\mathcal E}(I)} \mu(j) = \mu({\mathcal E}(I)),\end{equation*}

where the inequality above is an equality whenever each element of ${\mathcal E}(I)$ shares an edge with a single element of I, and is otherwise a strict inequality. Thus $\mu \in \mathscr{N\,}_1^{++}({\mathbb H})$. In fact, it is necessarily the case that ${Ncond}({\mathbb H}) \subset \mathscr{N\,}_1({\mathbb H})$, because if this were not true, there would exist in particular a $\mu\in \overline{\mathscr{N\,}_1({\mathbb H})} \cap {Ncond}({\mathbb H})$, making the system $({\mathbb H},{ml},\mu)$ unstable (in view of Proposition 4.1) despite the fact that $\mu \in {Ncond}({\mathbb H})$, a contradiction to Theorem 2 in [Reference Mairesse and Moyal16]. Observe however that ${Ncond}({\mathbb H}) \ne \mathscr{N\,}_1({\mathbb H})$ in general. To see this, consider the case where ${\mathbb H}$ is the cycle of size 5, $1-2-3-4-5-1$. For a small enough $\epsilon>0$, set

\begin{equation*}\left\{\begin{array}{ll}\mu(1) &=\frac{1}{2}-\frac{3\epsilon}{4};\\[4pt] \mu(2) = \mu(5) &=\frac{1}{4}-\frac{\epsilon}{8};\\[4pt] \mu(3) &=\frac{4\epsilon}{5};\\[4pt] \mu(4) &=\frac{\epsilon}{5}.\end{array}\right.\end{equation*}

It is then easily checked that $\mu\in\mathscr{N\,}_1({\mathbb H})$. However, $\mu\not\in {Ncond}({\mathbb H})$, since the independent set $I=\{1,3\}$ is such that

\begin{equation*}\mu(I)=\frac{1}{2} +\frac{\epsilon}{20} > \frac{1}{2} - \frac{\epsilon}{20} = \mu(\{2,4,5\}) = \mu({\mathcal E}(I)).\end{equation*}

In conclusion, if ${\mathbb H}$ is a graph, the necessary condition ‘$\mu\in {Ncond}({\mathbb H})$’ is stronger than the necessary condition ‘$\mu\in \mathscr{N\,}_1({\mathbb H})$’.

Let us now define the following set of measures:

\begin{equation*} \mathscr{N\,}_2(\mathbb H)= \left\{\mu\in\mathscr{M\,}({V}):\,\quad \forall T \in {\mathcal T}(\mathbb H)\;,\,\mu(T)\;>\frac{1}{r({\mathbb H})}\right\}. \end{equation*}

We also have the following result.

Proposition 2. For any connected hypergraph $\mathbb H$ and any admissible matching policy $\Phi$,

\begin{equation*}{Stab}({\mathbb H},\Phi) \subset \mathscr{N\,}_2(\mathbb H).\end{equation*}

Proof. Suppose that there exists a transversal $T\in{\mathcal T}({\mathbb H})$ such that $\mu(T)\;\le\frac{1}{r({\mathbb H})}$. As each match contains at least one element whose class is an element of T, at any time the overall number of completed matches cannot exceed the number of arrivals of elements whose class belongs to T; in other words $M_n({\mathcal H})\leq A_n(T)$ for all n. Thus, for all n we have that

\begin{equation*} \frac{X_n(V)}{n}\ge \frac{1}{n}\left(A_n(V)-r({\mathbb H})M_n({\mathcal H})\right)\ge \frac{1}{n}\left(A_n(V)-r({\mathbb H})A_n(T)\right). \end{equation*}

Taking n to infinity in the above yields

\begin{equation*} \limsup_n \frac{X_n(V)}{n} \ge 1 - r({\mathbb H})\mu(T), \end{equation*}

and we conclude as in the previous proof.

Remark 3. As an immediate consequence of Proposition 2, if ${\mathbb H}=(V,{\mathcal H})$ is of order q, and such that $\tau({\mathbb H}) \le \frac{q}{r({\mathbb H})}$, then ${Stab}({\mathbb H},\Phi)$ does not contain the uniform measure $\mu_{{u}}=(1/q,...,1/q)$ on V; in other words the model $({\mathbb H},\Phi,\mu_{{u}})$ is unstable for any $\Phi$. Indeed, for any minimal transversal T of ${\mathbb H}$ we have that

\begin{equation*}\mu_{{u}}(T) = \frac{\tau({\mathbb H})}{q} \le \frac{1}{r({\mathbb H})}.\end{equation*}

We now introduce two necessary conditions for stability based on the anti-rank of the considered hypergraph. We first introduce the following sets of measures:

(14) \begin{align} \mathscr{N\,}^{\tiny{+}}_3(\mathbb H) &= \left\{\mu \in \mathscr{M\,}({V}):\;\forall i \in {V},\,\mu(i) \le \frac{1}{a({\mathbb H})}\right\};\end{align}

(15) \begin{align} \mathscr{N\,}^{-}_3(\mathbb H)&= \left\{\mu \in \mathscr{M\,}({V}):\;\forall i \in {V},\,\mu(i) < \frac{1}{a({\mathbb H})}\right\}.\end{align}

We have the following.

Proposition 3. For any connected hypergraph $\mathbb H=({V},{\mathcal H})$ and any admissible policy $\Phi$,

(16) \begin{equation}{Stab}(\mathbb H,\Phi) \subset \mathscr{N\,}^{\tiny{+}}_3(\mathbb H).\end{equation}

If the hypergraph $\mathbb H=({V},{\mathcal H})$ is r-uniform (i.e. $a({\mathbb H})=r({\mathbb H})=r$) we have that

(17) \begin{equation}{Stab}(\mathbb H,\Phi) \subset \mathscr{N\,}^{-}_3(\mathbb H).\end{equation}

In other words, the model $({\mathbb H},\Phi,\mu)$ cannot be stable unless $\mu(i)<1/r$ for any $i\in V$.

Proof. To prove the first statement, we argue again by contradiction. Suppose that $\mu(i_0) > \frac{1}{a({\mathbb H})}$ for some node $i_0$. As the function

\begin{equation*}\begin{cases}{\mathbb R}^+ &\longrightarrow {\mathbb R}^+\\x &\longmapsto \frac{r({\mathbb H})-a({\mathbb H})+x}{xa({\mathbb H})}\end{cases}\end{equation*}

strictly decreases to $\frac{1}{a}$, there exists $x_0 > 0$ such that

(18) \begin{equation}\mu(i_0) > \frac{r({\mathbb H})-a({\mathbb H})+x_0}{x_0a({\mathbb H})}.\end{equation}

Then, applying the inequality in (4) to $B \equiv {V} \setminus \{i_0\}$, we readily obtain that almost surely for all n,

(19) \begin{align}\frac{r({\mathbb H})+x_0}{a({\mathbb H})}A_n\left({V}\setminus\{i_0\}\right)&\ge \frac{r({\mathbb H})+x_0}{a({\mathbb H})}\left(\sum\limits_{H \in {\mathcal H}(i_0)} \left|H -1\right| M_n\left(H\right)+\sum\limits_{H \in \overline{{\mathcal H}(i_0)}} \left|H \right| M_n\left(H\right)\right) \nonumber\\ &\ge \left(r({\mathbb H})+x_0-\frac{r({\mathbb H})+x_0}{a({\mathbb H})}\right)M_n\left({\mathcal H}(i_0)\right) + (r({\mathbb H})+x_0)M_n\left(\overline{{\mathcal H}(i_0)}\right). \end{align}

Likewise, applying the equality of (4) to $\{i_0\}$ and then ${V}\setminus \{i_0\}$ also yields

\begin{multline*}X_n\left({V}\setminus \{i_0\}\right)+\left(x_0 +1 - \frac{r({\mathbb H})+x_0}{a({\mathbb H})}\right)X_{n}(i_0)\\\shoveleft{= A_n\left({V}\setminus \{i_0\}\right)-\sum\limits_{H \in {\mathcal H}(i_0)} \left| H -1\right| M_n\left(H\right)-\sum\limits_{H \in \overline{{\mathcal H}(i_0)}} \left| H\right| M_n\left(H\right)}\\\shoveright{+\left(x_0 +1- \frac{r({\mathbb H})+x_0}{a({\mathbb H})}\right)\left(A_n(i_0)-M_n\left({\mathcal H}(i_0)\right)\right)}\\\shoveleft{> A_n\left({V}\setminus \{i_0\}\right)+\left(x_0 +1- \frac{r({\mathbb H})+x_0}{a({\mathbb H})}\right)A_n(i_0)}\\-\left(r({\mathbb H})+ x_0 - \frac{r({\mathbb H})+x_0}{a({\mathbb H})}\right)M_n({\mathcal H}(i_0)) - (r({\mathbb H})+x_0)M_n\left(\overline{{\mathcal H}(i_0)}\right).\end{multline*}

Combining this with (19) implies that almost surely for all n,

\begin{equation*}X_n\left({V}\right)+\left(x_0 - \frac{r({\mathbb H})+x_0}{a({\mathbb H})}\right)X_{n}(i_0)> \left(1- \frac{r({\mathbb H})+x_0}{a({\mathbb H})}\right)A_n\left({V}\right)+x_0A_n(i_0).\end{equation*}

Therefore we have that

(20) \begin{equation}\limsup_n \frac{1}{n}\left(X_n\left({V}\right)+\left(x_0 - \frac{r({\mathbb H})+x_0}{a({\mathbb H})}\right)X_{n}(i_0)\right) \ge 1- \frac{r({\mathbb H})+x_0}{a({\mathbb H})}+x_0\mu(i_0); \end{equation}

hence the chain $\left\{{W_n},\,n\in{\mathbb N}\right\}$ is transient, since the right-hand side of the above is positive from (18).

It remains to check that in the case where the hypergraph is r-uniform, the model cannot be stable whenever

\begin{equation*}\mu(i_0) \ge \frac{1}{a({\mathbb H})}=\frac{1}{r}\end{equation*}

for some $i_0\in V$. For this, notice that, as $r({\mathbb H})=a({\mathbb H})=r$, a weak inequality holds true in (8) for any $x_0>0$. It then readily follows from (20) that for any $x_0$,

\begin{equation*}\limsup_n \frac{1}{n}\left(X_n\left({V}\right)+\left(x_0 - \frac{r({\mathbb H})+x_0}{a({\mathbb H})}\right)X_{n}(i_0)\right) \ge 0,\end{equation*}

and we conclude, as in the proof of Proposition 1, that the chain $(W_n)$ is at best null recurrent.

5.1. Stars

First recall that, as for any bipartite graph (see Theorem 2 in [Reference Mairesse and Moyal16]), graphical matching models on trees are always unstable. This is true in particular if the matching graph is a ‘star’, i.e. a connected graph in which all vertices but one are of degree 1. The following two results can be seen as generalizations of this fact to hypergraphical models.

Proof. Fix $\Phi$ and $\mu$ in ${Stab} ({\mathbb H},\Phi)$. Let T be a transversal of cardinality 1, i.e. $T=\{i_0\}$, where the vertex $i_0$ belongs to all hyperedges in ${\mathcal H}$. Then from Proposition 3, we have that $\mu(i_0) < 1/a({\mathbb H}) = 1/r$. However, Proposition 2 implies that $\mu(i_0)>1/r({\mathbb H})=1/r,$ an absurdity.

In other words, any uniform hypergraph whose hyperedges all contain the same node $i_0$ cannot make the corresponding system stable. Moreover, we have the following.

• • all hyperedges of ${\mathcal H}(B)$ contain at least one node of degree 1;

• • at least one of these nodes of degree 1 lies outside of B.

Then ${\mathbb H}$ is non-stabilizable.

Proof. Let $k=|{\mathcal H}(B)|$, i.e. the number of hyperedges intersecting B. Denote by $H_{1},...,H_{k}$ these intersecting hyperedges, and for any $l \in[\![ 1,k ]\!]$, denote by $i_l\in V$ a node of degree 1 belonging to $H_{l}$. Observe that the nodes $i_1,...,i_k$ are not necessarily distinct. On the one hand, for any $l\in[\![ 1,k ]\!]$ we have that

\begin{equation*}X_n(i_l)=A_n(i_l)-M_n(H_{l}).\end{equation*}

Thus, applying again the inequality in (4), we get that for all n,

\begin{equation*}A_n(B)\geq \sum\limits_{l=1}^k |H_{l}\cap B| M_n(H_l)=\frac{1}{n}\sum\limits_{l=1}^{k}|H_l\cap B|(A_n(i_l)-X_n(i_l)).\end{equation*}

This entails that if $\mu \in \mathscr{N\,}_1^{\tiny{++}}(\mathbb{H})$,

\begin{equation*}\limsup\limits_{n}\frac{1}{n} \sum\limits_{l=1}^{k}|H_l\cap B|X_n(i_l)\geq\sum\limits_{l=1}^{k}|H_l\cap B|\mu(i_l)-\mu(B) \ge 0.\end{equation*}

If the above inequality is strict, then the chain $\{W_n\}$ is transient. If the inequality is weak, then as above we can stochastically lower-bound the chain by a zero-drift chain $\{\tilde Y_n\}$, defined by

\begin{equation*}\tilde Y_n =\left(A_n(B)\;-\;\sum\limits_{l=1}^{k}|H_l\cap B|A_n(i_l)\right),\quad n\in{\mathbb N},\end{equation*}

which is not identically null, thanks to the assumption that at least one of the nodes $i_l$, $l=1,...,k$, is not an element of B. This concludes the proof.

Example 4. Any hypergraph ${\mathbb H}=(V,{\mathcal H})$ such that there exist two hyperedges $H_1$ and $H_2$ with $H_1 \cap H_2 \ne \emptyset$ and two nodes $i_1 \in H_1 \cap \overline{H_2}$, $i_2 \in H_2 \cap \overline{H_1}$ with $d\left(i_1\right)=d\left(i_2\right)=1$ is non-stabilizable (see Figure 4). To see this, take $B = H_1 \cap H_2$ in Proposition 6.

Figure 4.

Two intersecting hyperedges, each containing an isolated node outside of their intersection, make the system unstable.

5.2. r-partite hypergraphs

We now turn to hypergraphical generalizations of bipartite graphs.

Proof. Applying (4) successively to $V_1$ and $V_2$ readily implies that for all n,

\begin{equation*} X_n(V_1) =A_n(V_1)-M_n({\mathcal H})\ge 0 \quad \mbox{ and }\quad X_n(V_2) = A_n(V_2)-(r-1) M_n({\mathcal H})\geq 0, \end{equation*}

and thus

\begin{equation*}X_n(V_1) \geq A_n(V_1)-\displaystyle\frac{1}{r-1}A_n(V_2).\end{equation*}

Then, the usual SLLN-based argument implies that the model cannot be stable unless $\mu(V_2) \geq (r-1)\mu(V_1)$. But as $\mu(V_1)+\mu(V_2)=1$ we have that $\mu(V_1)\leq\displaystyle\frac{1}{r}$, and hence $\mu \not\in \mathscr{N\,}_2({\mathbb H})$ since $V_1$ is a transversal.

Example 5. The so-called Fano plane is a well-known object in discrete geometry. It is the smallest projective plane, namely, the smallest set of points and lines such that any two points share a line, any two lines intersect at a single point, and on every line lie the same number of points. In the setting of hypergraphs (points being nodes and lines being hyperedges), the Fano plane is thus the smallest uniform hypergraph ${\mathbb H}$ in which each pair of nodes belongs to a single hyperedge, and each pair of hyperedges intersects at a single node. It can be checked that ${\mathbb H}=(V,{\mathcal H})$ is of order 7, for $V=[\![ 1,7 ]\!]$ and e.g.

\begin{equation*}{\mathcal H}=\left\{\{1,2,4\},\{1,5,6\},\{1,3,7\},\{2,3,5\},\{4,5,7\},\{4,3,6\},\{6,2,7\}\right\}.\end{equation*}

Supported by simulations, we conjecture that Fano planes are stabilizable. However, if $\mathbb{H}'=({V},{\mathcal H}')$ is the sub-hypergraph defined by ${\mathcal H}'={\mathcal H}\backslash H$, where H is an arbitrary hyperedge of ${\mathcal H}$, then it is easily seen that $\mathbb{H}'$ is a 3-uniform bipartite hypergraph with $V_1=H$ and $V_2={V}\backslash H$. So we deduce from Proposition 7 that $\mathbb{H}'$ is non-stabilizable. A Fano plane minus the hyperedge $\{4,5,7\}$ is represented in Figure 5.

Figure 5.

The Fano plane minus the hyperedge $\{4,5,7\}$.

We know from Theorem 2 in [Reference Mairesse and Moyal16] that bipartite graphs are not stabilizable. The next result shows that this can be generalized to r-partite hypergraphs (which generalize bipartite graphs—see Remark 5).

Proof. As in the above proof we get that for any $i\ne j$ and any n,

\begin{equation*} X_n(V_j) =A_n(V_j)-M_n({\mathcal H})\ge 0 \quad \mbox{ and }\quad X_n(V_i) =A_n(V_i)-M_n({\mathcal H})\ge 0, \end{equation*}

implying that $X_n(V_i)\ge A_n(V_i)-A_n(V_j)$ and, in turn, that the model cannot be stable unless $\mu(V_i) \le \mu(V_j)$. By symmetry, this implies that $\mu(V_i)=\mu(V_j)$. As the $V_i$ are disjoint, we thus have that $\mu(V_i)=1/r$ for all i. Thus, as any $V_i$ is a transversal of ${\mathbb H}$, $\mu $ is not an element of $\mathscr{N\,}_2({\mathbb H})$.

Definition 8. A hypergraph ${\mathbb H}=(V,{\mathcal H})$ satisfies Hall’s condition if $|V_2| \geq |V_1|$ for any disjoint subsets $V_2$ and $V_1$ of V satisfying $|H\cap V_2|\geq |H\cap V_1|$ for all hyperedges $H\in{\mathcal H}$.

It is well known (see [Reference Hall14] for the particular case of graphs, and the general result in [Reference Haxell15]) that Hall’s condition is necessary and sufficient for the existence of a perfect matching on ${\mathbb H}$, i.e. a spanning sub-hypergraph of ${\mathbb H}$ in which all nodes have degree 1, in the case where the hypergraph is balanced, i.e. it does not contain any odd strong cycle. It is intuitively clear that the construction of stable stochastic matching models on hypergraphs is somewhat reminiscent of that of perfect matchings on a growing hypergraph that replicates the matching hypergraph a large number of times in the long run (in the case of graphs, see the discussion in Section Section 7 of [Reference Moyal and Perry19]). This connection has a simple illustration in the next proposition, which provides a family of probability measures, naturally including the uniform measure on V, that cannot stabilize a matching model on the hypergraph ${\mathbb H}$ unless the latter satisfies Hall’s condition. In what follows we define, for any ${\mathbb H}=(V,{\mathcal H})$ and any measure $\mu\in\mathscr{M\,}(V)$,

(21) \begin{equation}\mu_{\mbox{min}}=\min\left\{\mu(i)\,:\,i\in V\right\}\quad\mbox{ and }\quad\mu_{\mbox{max}}=\max\left\{\mu(i)\,:\,i\in V\right\}.\end{equation}

Proposition 9. For any hypergraph $\mathbb{H}=(V,{\mathcal H})$ that violates Hall’s condition, any matching policy $\Phi$, and any $\mu\in \mathscr{M\,}(V)$ such that

(22) \begin{equation} \frac{\mu_{\mbox{min}}}{\mu_{\mbox{max}}} > \frac{\left\lfloor \frac{q({\mathbb H}) +1}{2}\right\rfloor -1}{\left\lfloor \frac{q({\mathbb H}) +1}{2}\right\rfloor}, \end{equation}

the model $({\mathbb H},\Phi,\mu)$ is unstable. In particular, $({\mathbb H},\Phi,\mu_{{u}})$ is unstable for $\mu_{{u}}$ the uniform distribution on V.

Proof. Fix ${\mathbb H}$, $\Phi$, and a measure $\mu$ satisfying (22). We first show that $\mu$ is monotonic with respect to the counting measure on V, i.e.

(23) \begin{equation}\forall E,F \subset V,\quad |E| < |F| \Longrightarrow \mu(E) < \mu(F).\end{equation}

Let E and F be such that $|E| < |F|$, and let $k = |F|$. Also, let $\alpha$ be a bijection from $[\![ 1,q({\mathbb H}) ]\!]$ to V such that

(24) \begin{equation}\mu_{\mbox{min}}=\mu(\alpha(1)) \le \mu(\alpha(2)) \le ... \le \mu(\alpha(q({\mathbb H})))=\mu_{\mbox{max}};\end{equation}

in other words $\left(\mu(\alpha(1)),\mu(\alpha(2)),...,\mu(\alpha(q({\mathbb H})))\right)$ is an ordered (in increasing order) version of the family $\left\{\mu(i);\, i \in V\right\}$. As $|E|\le k-1$ we clearly have

(25) \begin{equation}\mu(F) - \mu(E) \ge \sum_{i=1}^k \mu(\alpha(i)) - \sum_{i=q-k+2}^q \mu(\alpha(i)).\end{equation}

First, if

\begin{equation*}k \le \left\lfloor \frac{q({\mathbb H}) +1}{2}\right\rfloor,\end{equation*}

then (22) entails that $k\mu_{\mbox{min}} >(k-1) \mu_{\mbox{max}},$ whence

(26) \begin{equation}\sum_{i=1}^k \mu(\alpha(i)) - \sum_{i=q-k+2}^q \mu(\alpha(i)) \ge k \mu_{\mbox{min}} - (k-1)\mu_{\mbox{max}} >0.\end{equation}

If

\begin{equation*}k>\left\lfloor \frac{q({\mathbb H}) +1}{2}\right\rfloor,\end{equation*}

then the index sets $[\![ 1,k ]\!]$ and $[\![ q-k+2, q ]\!]$ intersect precisely on $[\![ q-k+2,k ]\!]$. Thus

(27) \begin{align}\sum_{i=1}^k \mu(\alpha(i)) - \sum_{i=q-k+2}^q \mu(\alpha(i)) &= \sum_{i=1}^{q-k+1} \mu(\alpha(i)) - \sum_{i=k+1}^q \mu(\alpha(i))\nonumber\\&\ge (q-k+1)\mu_{\mbox{min}} - (q-k)\mu_{\mbox{max}} >0, \end{align}

where the last inequality follows, as in (26), from the fact that

\begin{equation*}q-k+1\le \left\lfloor \frac{q({\mathbb H}) +1}{2}\right\rfloor.\end{equation*}

Combining (25) with (26)–(27) concludes the proof of (23) in all cases.

Now fix $V_2$ and $V_1$ such that $|H\cap V_2|\geq |H\cap V_1|$ for any $H\in{\mathcal H}$, and $|V_2|<|V_1|$, which from (23) implies that $\mu(V_2) < \mu(V_1)$. Then, again applying (4) to $V_2$ and $V_1$, we get that

\begin{align*}X_n(V_2)+X_n(V_1)&\ge A_n(V_2)+A_n(V_1)-2\sum\limits_{H\in{\mathcal H}}\left|H \cap V_2\right| M_n(H)\\&\ge A_n(V_2)+A_n(V_1)-2A_n(V_2).\end{align*}

Thus, by the usual argument, the model cannot be stable unless $\mu(V_2)\geq \mu(V_1)$, a contradiction.

5.3. Cycles

• • Every hyperedge of ${\mathcal H}$ consists of r consecutive nodes modulo $q({\mathbb H})$.

• • Any pair of consecutive hyperedges (in an obvious sense) intersects in exactly $\ell$ vertices.

Proof. The partition $V_1, V_2, ..., V_r$ of V defined by

\begin{equation*}V_i=\left\lbrace v_{i+(j-1)r}\;;\,j\in [\![ 1,q/r]\!] \right\rbrace\end{equation*}

satisfies Proposition 8.

Figure 6 shows a 3-uniform 2-cycle of order 12.

Figure 6.

A 3-uniform 2-cycle of order 12.

6.1. Complete 3-uniform hypergraphs

We first consider the case of a complete 3-uniform hypergraph ${\mathbb H}$, an example of which for $q({\mathbb H})=4$ is represented in Figure 1. We show that, in this case, the necessary condition given in Proposition 3 is also sufficient.

Theorem 1. Let ${\mathbb H}=(V,{\mathcal H})$ be a complete 3-uniform hypergraph of order $q({\mathbb H})\ge 4$. Then, for any admissible policy $\Phi$, we have that

\begin{equation*}{Stab}({\mathbb H},\Phi) = \mathscr{N\,}_3^{\tiny{-}}({\mathbb H});\end{equation*}

that is, the model $({\mathbb H},\Phi,\mu)$ is stable if and only if $\mu(i) < 1/3$ for any $i\in V.$

Proof. The necessity of the condition having been shown in Proposition 3, only the sufficiency remains to be proven. Suppose that $\mu(i)<1/3$ for any $i\in V$, and fix $\alpha$ such that $\max_{i\in V} \mu(i) < \alpha <1/3$. Define the planar Markov chain $\left\{{U^{\alpha}_n},\,n\in{\mathbb N}\right\}$ having the following transitions on ${\mathbb N}^2$:

\begin{equation*}\left\{\begin{array}{l@{\quad}l@{\quad}l@{\quad}l} \mbox{First axis:} \quad &P^\alpha_{(x,0),(x+1,0)} &= \alpha,&\,x\in{\mathbb N}^+,\\[5pt] &P^\alpha_{(x,0),(x,1)} &= 1-\alpha,&\,x\in{\mathbb N}^+,\\[5pt] \mbox{Second axis:} \quad &P^\alpha_{(0,y),(0,y+1)} &= \alpha,&\,y\in{\mathbb N}^+,\\[5pt] &P^\alpha_{(0,y),(1,y)} &= 1-\alpha,&\,y\in{\mathbb N}^+,\\[5pt] \mbox{Interior:} \quad & P^\alpha_{(x,y),(x+1,y)} &= \alpha,&\,x,y\in{\mathbb N}^+,\\[5pt] &P^\alpha_{(x,y),(x,y+1)} &= \alpha,&\,x,y\in{\mathbb N}^+,\\[5pt] &P^\alpha_{(x,y),(x-1,y-1)} &= 1- 2\alpha,&\,x,y\in{\mathbb N}^+, \end{array}\right.\end{equation*}

and arbitrary transitions from (0,0) to any element of ${\mathbb N}^2$. (These transitions are represented in Figure 7.)

Figure 7.

Auxiliary Markov chain of the complete 3-uniform hypergraph.

Denote by $\Delta=(\Delta_x,\Delta_y)$, $\Delta'=(\Delta'_x,\Delta'_y)$, and $\Delta''=(\Delta''_x,\Delta''_y)$ the mean (horizontal and vertical) drifts of the chain $\{U^\alpha_n\}$, respectively on the interior, on the first axis, and on the second axis, so that we have the following:

\begin{equation*}\left\{\begin{array}{l@{\quad}l@{\quad}l} \mbox{First axis:} \quad &\Delta'_x=\alpha, \quad &\Delta'_y=1-\alpha;\\[5pt] \mbox{Second axis:} \quad &\Delta''_x=1-\alpha, \quad &\Delta''_y=\alpha;\\[5pt] \mbox{Interior:} \quad & \Delta_x=3\alpha-1, \quad &\Delta_y=3\alpha-1. \end{array}\right.\end{equation*}

Thus, $\Delta_x <0$ and $\Delta_y<0$. Also, we have that

\begin{equation*}\Delta_x\Delta'_y - \Delta_y\Delta'_x = \Delta_x\Delta''_y - \Delta_y\Delta''_x = (3\alpha-1)(1-2\alpha) <0,\end{equation*}

so we can apply [Reference Fayolle, Malyshev and Menshikov12, Theorem 3.3.1(a)] to claim that the Markov chain $\{U^\alpha_n\}$ is positive recurrent. Specifically, it can be checked that, setting

\begin{equation*}u=\frac{1-3\alpha}{2}>0,\end{equation*}

for any w such that

\begin{equation*}{{3\alpha-1}} < w <\frac{(3\alpha - 1)\alpha}{1-\alpha}<0\end{equation*}

we have that

(28) \begin{equation} \begin{cases} 2u \Delta_x + w \Delta_y &< 0,\\ 2u \Delta_y + w \Delta_x &< 0,\\ 2u \Delta'_x + w \Delta'_y &< 0,\\ 2u \Delta''_y + w \Delta_x & < 0. \end{cases} \end{equation}

Second, as $4u^2> w^2$, the quadratic form $Q\;:\;(x,y) \mapsto ux^2 +uy^2+wxy$ is positive definite. Then, in view of Lemma 3.3.3 in [Reference Fayolle, Malyshev and Menshikov12], it follows from (28) that, defining the mapping

\begin{equation*}L^\alpha : \begin{cases} {\mathbb N}^2 &\longrightarrow {\mathbb R}^+ \\ (x,y) &\longmapsto \sqrt{Q(x,y)}=\sqrt{ux^2 +uy^2+wxy}, \end{cases}\end{equation*}

we have that for some compact set $\mathcal K^\alpha\subset {\mathbb N}^2$, for any $(x,y) \in \overline{\left(\mathcal K^\alpha\right)}$,

(29) \begin{equation} {\mathbb E}\left[L^\alpha\left(U^\alpha_{n+1}\right) - L^\alpha(U^\alpha_n) \mid U^\alpha_n = (x,y)\right] <0. \end{equation}

Now, as ${\mathbb H}$ is complete 3-uniform, the states of the Markov chain $\left\{{X_n},\,n\in{\mathbb N}\right\}$ have at most two nonzero coordinates; in other words, its state space is

\begin{equation*}\mathcal E = \Bigl\{\textbf{x}=(x_1,...,x_q) \in{\mathbb N}^q \,:\, x_ix_jx_k=0 \mbox{ for any distinct }i,j,k \in [\![ 1,q ]\!]\Bigl\}.\end{equation*}

Define the mapping

\begin{equation*}L: \left\{\begin{array}{l@{\quad}l} \mathcal E &\longrightarrow {\mathbb R}^+\\ \textbf{x} &\longmapsto \left\{\begin{array}{ll} 0 & \quad\mbox{ if } \textbf{x}=\mathbf 0,\\ L^\alpha((x,0)) &\quad \mbox{ if $\textbf{x}=x.\textbf{e}_i$, for some $x>0$, $i\in V$},\\ L^\alpha((x,y)) &\quad \mbox{ if $\textbf{x}=x.\textbf{e}_i+y.\textbf{e}_j$, for some $x,y>0$, $i\ne j$,} \end{array}\right. \end{array}\right.\end{equation*}

where the above definition is unambiguous because $L^\alpha$ is a symmetric form on ${\mathbb N}^2$. Also define the compact set

\begin{equation*}\mathcal K = \left\{\textbf{x} \,\;:\!=\;x.\textbf{e}_i+y.\textbf{e}_j\in \mathcal E\,:\, (x,y) \in\mathcal K^\alpha\right\}.\end{equation*}

Then, first, if $\textbf{x}\in\bar{\mathcal K}\cap \mathcal E$ is such that $\textbf{x}=x.\textbf{e}_i+ y.\textbf{e}_j$ for some $x,y>0$ and $i,j \in V$, $i\ne j$, we get that

\begin{multline*} {\mathbb E}\left[{L\left(X_{n+1}\right) - L(X_n) \mid X_n = \textbf{x}}\right] \\ \shoveleft{=(1-\mu(i)-\mu(j))\left(L\left(\textbf{x}-\textbf{e}_i-\textbf{e}_j\right)-L(\textbf{x})\right)}\\ \shoveright{+ \mu(i) \left(L\left(\textbf{x}+\textbf{e}_i\right)-L(\textbf{x})\right) + \mu(j) \left(L\left(\textbf{x}+\textbf{e}_j\right) - L(\textbf{x})\right)}\\ \shoveleft{=(1-\mu(i)-\mu(j))\left(L^\alpha\left(x-1,y-1\right)-L^\alpha(x,y)\right) }\\ \shoveright{+ \mu(i) \left(L^\alpha\left(x+1,y\right)-L^\alpha(x,y)\right)+ \mu(j) \left(L^\alpha\left(x,y+1\right) - L^\alpha(x,y)\right)}\\ \shoveleft{{ < (1-2\alpha)}\left(L^\alpha\left(x-1,y-1\right)-L^\alpha(x,y)\right) }\\ \shoveright{+ \alpha \left(L^\alpha\left(x+1,y\right)-L^\alpha(x,y)\right)+ \alpha \left(L^\alpha\left(x,y+1\right) - L^\alpha(x,y)\right)}\\ = {\mathbb E}\left[L^\alpha\left(U^\alpha_{n+1}\right) - L^\alpha(U^\alpha_n) \mid U^\alpha_n = (x,y)\right], \end{multline*}

where, in the inequality above, we used the facts that $L^\alpha$ is nondecreasing in its first and second variables, and that $L^\alpha\left(x-1,y-1\right){<}\, L^\alpha(x,y)$. Likewise, if $\textbf{x}\in \bar{\mathcal K} \cap \mathcal E$ is such that $\textbf{x}=x.\textbf{e}_i$ for some $x>0$ and $i\in V$, we have that

\begin{align*} & {\mathbb E}\left[{L\left(X_{n+1}\right) - L(X_n) \mid X_n = \textbf{x}}\right] \nonumber\\ & \qquad=\sum_{j\ne i}\mu(j)\left(L\left(\textbf{x}+\textbf{e}_j\right)-L(\textbf{x})\right)+ \mu(i) \left(L\left(\textbf{x}+\textbf{e}_i\right)-L(\textbf{x})\right)\nonumber\\ &\qquad=(1-\mu(i))\left(L^\alpha\left(x,1\right)-L^\alpha(x,0)\right)+ \mu(i) \left(L^\alpha\left(x+1,0\right)-L^\alpha(x,0)\right)\nonumber\\ &{ \qquad\quad< (1-\alpha)}\left(L^\alpha\left(x,1\right)-L^\alpha(x,0)\right)+ \alpha \left(L^\alpha\left(x+1,0\right)-L^\alpha(x,0)\right)\nonumber\\ &\qquad= {\mathbb E}\left[{ L^\alpha\left(U^\alpha_{n+1}\right) - L^\alpha(U^\alpha_n) \mid U^\alpha_n = (x,0)}\right], \end{align*}

remarking that $L^\alpha(x,1) { < }\, L^\alpha(x,0)$. Recalling that $X_n=[W_n]$ for all n, using (29) in both cases, we conclude using the Lyapunov–Foster theorem (see e.g. [Reference Brémaud6, Section 5.1]) that the chain $\left\{{W_n},\,n\in{\mathbb N}\right\}$ is positive recurrent.

The complete 3-uniform k-partite hypergraphs generalize the complete k-partite graphs introduced in [17, p. 4], also called separable graphs in [Reference Mairesse and Moyal16] and [Reference Moyal and Perry19], or blow-ups of the complete graph of order k in some other references. Roughly speaking, a complete 3-uniform k-partite hypergraph is a version of the complete 3-uniform graph of order k, in which the k nodes are replicated several times, each of the k sets of replicas forming an independent set $I_i$, such that all replicas of the same set do not share any hyperedge with each other, but all share hyperedges of size 3 with all other pairs of replicas belonging to two different other sets of replicas. Observe that in the particular case where all the sets $I_1,...,I_k$ are of cardinality 1 (i.e. there are no replicas), the complete 3-uniform k-partite hypergraph is just the complete 3-uniform hypergraph of order k. We can then easily generalize the latter result.

Proof. Macroscopically (i.e., if we do not distinguish between items of classes that belong to the same independent set in the partition $I_1,...,I_k$), the system has the same behavior as the complete 3-uniform hypergraph. Specifically, let q be the order of the hypergraph $\tilde{\mathbb H}$, and define the mapping

\begin{equation*}\Psi:\left\{\begin{array}{ll}{\mathbb N}^q &\quad\longrightarrow {\mathbb N}^k\\\tilde{\textbf{x}}=(\tilde x_1,...,\tilde x_q) &\quad \longmapsto \textbf{x}=(x_1,...,x_k):\,\forall i\in[\![ 1,k ]\!], x_i = \sum_{j\in [\![ 1,q ]\!];\,j\in I_i} \tilde x_i.\end{array}\right.\end{equation*}

In words, $\Psi$ maps the detailed class-content of the model onto a class-content where one puts together all the elements of classes belonging to the same independent set of the partition $I_1,...,I_k$. Take L to be the Lyapunov function introduced in the previous proof. Fix an admissible policy $\tilde\Phi$ and a probability measure $\tilde\mu\in\mathscr{M\,}(\tilde V)$, and let $\left\{{\tilde X_n},\,n\in{\mathbb N}\right\}$ be the class-content process of the model $(\tilde{\mathbb H},\tilde\Phi,\tilde\mu)$. On the other hand, let $\left\{{X_n},\,n\in{\mathbb N}\right\}$ be the class-content process of the model $({\mathbb H},\Phi,\mu)$ defined on ${\mathbb H}=(V,{\mathcal H})$, the complete 3-uniform hypergraph of order k, for an arbitrary matching policy $\Phi$ and a probability measure $\mu\in\mathscr{M\,}(V)$ such that $\mu(i)=\tilde\mu(I_i)$ for any $i\in[\![ 1,k ]\!]$. Then it is easily seen that $\left\{{\tilde X_n},\,n\in{\mathbb N}\right\}$ and $\left\{{X_n},\,n\in{\mathbb N}\right\}$ are connected by the following relation: for all n and all $\tilde{\textbf{x}}\in{\mathbb N}^{q}$,

\begin{equation*}{\mathbb E}\left[{L\circ\Psi\left(\tilde{X}_{n+1}\right) - L\circ\Psi(\tilde{X}_{n}) \mid \tilde{X}_{n} = \tilde{\textbf{x}}}\right] = {\mathbb E}\left[{L\left(X_{n+1}\right) - L(X_n) \mid X_n = \Psi(\tilde{\textbf{x}})}\right],\end{equation*}

and the argument in the proof of Theorem 1 shows that the Markov chain $\left\{{\tilde X_n},\,n\in{\mathbb N}\right\}$ is positive recurrent whenever $\tilde\mu(i)<1/3$, that is, $\mu(I_i)<1/3$, for all $i\in[\![ 1,k ]\!]$. This concludes the proof.

6.2. Incomplete 3-uniform hypergraphs

As is shown in Theorem 1, complete 3-uniform hypergraphs are stabilizable for a large class of measures. We show below that incomplete hypergraphs can also be stabilizable.

Theorem 2. Let $\mathbb H=({V},{\mathcal H})$ be a complete 3-uniform hypergraph of order $q \ge 5$, and let ${\mathbb H}'=({V},{\mathcal H}')$ be the $(3\textrm{-uniform})$ sub-hypergraph of ${\mathbb H}$ obtained by setting ${\mathcal H}'={\mathcal H}\backslash {\mathcal J}$, where ${\mathcal J}$ is a subset of ${\mathcal H}$ containing disjoint hyperedges. Let J be the union of the elements of ${\mathcal J}.$ Then the model $({\mathbb H}',{ml},\mu)$ is stable for any $\mu$ in

\begin{equation*}\mathscr{S\,}({\mathbb H}')=\biggl\{\mu\in\mathscr{M\,}(V)\;:\;\left(\max\limits_{i\in J} \lambda_i(\mu)\vee \max\limits_{i\in \bar J} \nu_i(\mu)\right)<0\biggl\}\,\cap\,\mathscr{N\,}_2(\mathbb H')\, \cap\mathscr{N\,}^{{-}}_3(\mathbb H'),\end{equation*}

where the $\lambda_i(\mu)\;:\;i\in J$ and $\nu_{i}(\mu)\;:\;i\in \bar J$ are defined respectively by (31) and (32).

Proof. Fix $\Phi={ml}$, and let $\mu\in {\mathscr{S\,}({\mathbb H}')}$. For such ${\mathbb H}'$ the study of $\left\{{Y_n},\,n\in{\mathbb N}\right\}$ does not boil down to that of a planar Markov chain. Instead, we study the embedded chain $\left\{{Y_n},\,n\in{\mathbb N}\right\}=\left\{{X_{4n}},\,n\in{\mathbb N}\right\}$, and consider the following quadratic Lyapunov function:

\begin{equation*}Q\;:\;\left\{\begin{array}{l@{\quad}l}{\mathbb N}^q &\longrightarrow {\mathbb R}^+\\\textbf{x} &\longmapsto \sum_{i=1}^{q} (x_i)^2.\end{array}\right.\end{equation*}

Fix $n\in{\mathbb N}$. We have the following alternatives given the value of the embedded chain $\{Y_n\}$ at time n:

1. (i) First, for any $i\in \overline{J}$ and any integer $x_i\geq{2}$, the chain $\left\{{Y_n},\,n\in{\mathbb N}\right\}$ makes the following transitions from the state $Y_n=x_i.\textbf{e}_i$:

   (30) \begin{equation} Y_{n+1}=\left\{\begin{array}{l@{\quad}l} Y_n+4\textbf{e}_i &\mbox{ w.p. }\mu(i)^4;\\ Y_n+3\textbf{e}_i+\textbf{e}_j &\mbox{ w.p. }4\mu(i)^3\mu(j);\\ Y_n+2\textbf{e}_i+2\textbf{e}_j &\mbox{ w.p. }6\mu(i)^2\mu(j)^2;\\ Y_n+\textbf{e}_i+3\textbf{e}_j &\mbox{ w.p. }4\mu(i)\mu(j)^3;\\ Y_n+4\textbf{e}_j &\mbox{ w.p. }\mu(j)^4;\\ Y_n+\textbf{e}_i &\mbox{ w.p. }12\mu(i)^2\mu(j)\mu(k);\\ Y_n+\textbf{e}_j &\mbox{ w.p. }12\mu(i)\mu(j)^2\mu(k);\\ Y_n-2\textbf{e}_i &\mbox{ w.p. }10\mu(j)^2\mu(k)\mu(\ell)\\ & \mbox{ ({the input has 2 \textit{j}, 1 \textit{k}, and 1 $\ell$, but does not end in \textit{jj}});}\\ Y_n-\textbf{e}_i+2\textbf{e}_j &\mbox{ w.p. }2\mu(k)\mu(\ell)\mu(j)^2\\ & \mbox{ ({the input has 2 \textit{j}, 1 \textit{k}, and 1 $\ell$, and ends in \textit{jj}});}\\ Y_n-2\textbf{e}_i &\mbox{ w.p. }6\mu(j)^2\mu(k)^2;\\ Y_n-\textbf{e}_i+2\textbf{e}_j &\mbox{ w.p. }4\mu(j)^3\mu(k);\\ Y_n+\textbf{e}_j &\mbox{ w.p. }24\mu(i)\mu(j)\mu(k)\mu(\ell);\\ Y_n-2\textbf{e}_i &\mbox{ w.p. }24\mu(j)\mu(k)\mu(\ell)\mu(m).\\ \end{array}\right. \end{equation}
   From this, we deduce using simple algebra that
   \begin{equation*}\Delta_i\,\;:\!=\;{\mathbb E}\left[{Q\left(Y_{n+1}\right) - Q\left(Y_n\right) | Y_n = x_i.\textbf{e}_i}\right]=\lambda_i(\mu)x_i+\beta_i(\mu),\end{equation*}
   for some bounded $\beta_i(\mu)$ and for
   (31) \begin{multline}\lambda_i(\mu)=\;8\mu^4(i) + 24\mu^3(i)\sum_{j\ne i} \mu(j) + 24\mu^2(i)\sum_{j\ne i} \mu^2(j)\\ + 8\mu(i)\sum_{j\ne i} \mu^3(j)+24\mu^2(i) \sum_{\substack{j,k\ne i}} \mu(j)\mu(k)-44\sum_{\substack{j,k,\ell\ne i}} \mu^2(j)\mu(k)\mu(\ell)\\-24\sum_{\substack{j,k\ne i}} \mu^2(j)\mu^2(k)-8\sum_{\substack{j,k\ne i}}\mu(j)\mu^3(k)-96\sum_{\substack{j,k,\ell,m\ne i}} \mu(j)\mu(k)\mu(\ell)\mu(m).\end{multline}
   Consequently, as the above is negative, there exists $a_1^{*}$ such that $\Delta_i <0$ whenever $x_i \ge a_1^{*}$.

2. (ii) For any $i\in J$ and any integer $x_{i}\geq{2}$, the transitions of $\left\{{Y_n},\,n\in{\mathbb N}\right\}$ from the state $x_{i}.\textbf{e}_i$ can be retrieved in a similar fashion to (30). It follows that

   \begin{equation*}\Delta'_{\!\!i}={\mathbb E}\left[{Q\left(Y_{n+1}\right) - Q\left(Y_n\right) | Y_n = x_{i}.\textbf{e}_{i}}\right]=\nu_{i}(\mu)x_{i}+\beta'_{i}(\mu)\end{equation*}
   for some bounded $\beta'_{\!\!i}(\mu)$, and setting $H=\{i,j,k\}$ as the only element of ${\mathcal J}$ such that $i\in H$, we obtain that
   (32) \begin{align}\nu_i(\mu) &= 8\mu^4(i) + 24\mu^3(i)\sum_{\ell\in{V}\backslash\{i\}} \mu(\ell) + 24\mu^2(i)\sum_{\ell\in{V}\backslash \{i\}} \mu^2(\ell) + 8\mu(i)\sum_{\ell\in{V}\backslash\{i\}} \mu^3(\ell) \nonumber\\ & -8 \sum_{\substack{\ell\in \overline{H}}} \mu(j) \mu^3(\ell)-4 \sum_{\substack{\ell\in\overline{H}:\\\textrm{ends with }kk}} \mu(j)\mu^2(k)\mu(\ell)-20\sum_{\substack{\ell\in\overline{H}:\\\textrm{otherwise}}} \mu(j)\mu^2(k) \mu(\ell)\nonumber\\ &-48 \mu(j)\mu(k) \sum_{\substack{\ell\in\overline{H}}} \mu^2(\ell)-4 \sum_{\substack{\ell\in\overline{H}:\\\textrm{ends with }\ell\ell}} \mu(j)\mu^2(\ell)\mu(m)-40 \sum_{\substack{\ell\in\overline{H}:\\\textrm{otherwise}}} \mu(j)\mu^2(\ell)\mu(m) \nonumber\\ &+ 48 \mu^2(i)\mu(j)\mu(k)-8 \mu(j)\mu(k)\sum_{\substack{\ell,m\in\overline{H}:\\\textrm{ends with }jk}} \mu(\ell)\mu(m)-80 \mu(j)\mu(k)\sum_{\substack{\ell,m\in\overline{H}:\\\textrm{otherwise}}} \mu(\ell)\mu(m)\nonumber\\ &-96 \sum_{\substack{\ell,m\in\overline{H}}} \mu(j)\mu(\ell)\mu(m)\mu(p)+24 \mu^2(i)\sum_{\substack{\ell\in\overline{H}}} \mu(j)\mu(\ell)+24 \mu^2(i)\sum_{\substack{\ell,m\in\overline{H}}} \mu(\ell)\mu(m)\nonumber\\ &-24\sum_{\substack{\ell\in\overline{H}}} \mu^2(j)\mu^2(\ell)-4\sum_{\substack{\ell\in\overline{H}:\\\textrm{ends with }jj}} \mu^2(j)\mu(\ell)\mu(m)-40\sum_{\substack{\ell\in\overline{H}:\\\textrm{otherwise}}} \mu^2(j)\mu(\ell)\mu(m)\nonumber\\ &-8\sum_{\substack{\ell\in\overline{H}}} \mu^3(j)\mu(\ell)+24\mu(i)\sum_{\substack{j,k\in H}}\mu(j)\mu^2(k)-8\sum_{\substack{\ell,m\in\overline{H}}} \mu^3(\ell)\mu(m)\nonumber\\ &-24\sum_{\substack{\ell,m\in\overline{H}}} \mu^2(\ell)\mu^2(m)\;\;\;-4\sum_{\substack{\ell,m,p\in\overline{H}:\\ \textrm{ends with }\ell\ell}} \mu^2(\ell)\mu(m)\mu(p)\nonumber\\ &-40\sum_{\substack{\ell,m,p\in\overline{H}:\\\textrm{otherwise}}} \mu^2(\ell)\mu(m)\mu(p)-96\sum_{\substack{\ell,m,p,s\in\overline{H}}} \mu(\ell)\mu(m)\mu(p)\mu(s).\end{align}
   Thus, there exists $a_{2}^{*}$ such that $\Delta'_{\!\!i} <0$ whenever $x_{i} \ge a_{2}^{*}$.

3. (iii) For any $i\ne j$ such that $\{i,j\}$ is not included in a hyperedge of the family $\mathcal J$, for any integers $x_{i},x_{j}>0$, we obtain that

   \begin{equation*}\Delta_{ij}\,\;:\!=\;{\mathbb E}\left[{Q\left(X_{n+1}\right) - Q\left(X_n\right) | X_n = x_{i}.\textbf{e}_i+x_{j}.\textbf{e}_j}\right]=\lambda_{ij}(\mu)x_{i}+\lambda_{ji}(\mu)x_{j}+\beta_{ij}(\mu),\end{equation*}
   for a bounded $\beta_{ij}(\mu)$ and for
   (33) \begin{equation}\lambda_{ij}(\mu)=2\Big(\mu(i)-\sum\limits_{\ell \in {V}\backslash \{i,j\}}\mu(\ell)\Big)\textrm{ and }\lambda_{ji}(\mu)=2\Big(\mu(j)-\sum\limits_{\ell \in {V}\backslash \{i,j\}}\mu(\ell)\Big).\end{equation}
   Now observe that ${V}\backslash \{i,j\}\in\mathcal{T}({\mathbb H})$, so
   \begin{equation*}\sum\limits_{\ell \in {V}\backslash \{i,j\}}\mu(\ell)>\displaystyle\frac{1}{3};\end{equation*}
   then $\lambda_{ij}(\mu)<0$ and $\lambda_{ji}(\mu)<0$. Thus, there exists $a_{3}^{*}$ such that $\Delta_{ij}<0$ whenever ${x_{i} \vee x_{j}} \ge a_{3}^{*}$.

4. (iv) For any i,j such that $i\ne j$ and $\{i,j\}\subset H$ for some $H\in \mathcal J$, for any integers $x_{i},x_{j}>0,$ we obtain that

   \begin{equation*}\Delta'_{\!\!ij} \,\;:\!=\;{\mathbb E}\left[{Q\left(X_{n+1}\right) - Q\left(X_n\right) | X_n = x_{i}.\textbf{e}_{i}+x_{j}.\textbf{e}_{j}}\right] = \nu_{ij}(\mu)x_i + \nu_{ji}(\mu)x_j +\beta'_{\!\!ij}(\mu)\end{equation*}
   for a bounded $\beta'_{\!\!ij}(\mu)$ and
   (34) \begin{equation}\nu_{ij}(\mu)=2\Big(\mu(i)-\sum\limits_{\ell \in \overline{H}}\mu(\ell)\Big)\textrm{ and }\nu_{ji}(\mu)=2\Big(\mu(j)-\sum\limits_{\ell \in \overline{H}}\mu(\ell)\Big).\end{equation}
   As $\overline{H}\in\mathcal{T}({\mathbb H})$, we have
   \begin{equation*}\sum\limits_{\ell \in\overline{H}}\mu(\ell)>\displaystyle\frac{1}{3};\end{equation*}
   then $\nu_{ij}(\mu)<0$ and $\nu_{ji}(\mu)<0$.

   Again, there exists $a_{4}^{*}$ such that $\Delta'_{\!\!ij}<0$ whenever ${x_{i} \vee x_{j}} \ge a_{4}^{*}$.

5. (v) We finally consider the case where $X_n=x_i.\textbf{e}_{i}+x_j.\textbf{e}_{j}+x_k.\textbf{e}_{k}$ for $H=\{i,j,k\}$, for some $H\in{\mathcal J}$ and integers $x_i$, $x_j$, and $x_k$ such that $x_i,x_j \geq x_k>0$. We have

   \begin{align*} \Delta_H &\,\;:\!=\;{\mathbb E}\left[{Q\left(X_{n+1}\right) - Q\left(X_n\right) | X_n = x_{i}.\textbf{e}_i+x_{j}.\textbf{e}_j+x_{k}.\textbf{e}_k}\right]\\ & =\alpha_{i}(\mu)x_{i}+\alpha_{j}(\mu)x_{j}+\alpha_{k}(\mu)x_k+\beta_H(\mu), \end{align*}
   for a bounded $\beta_H(\mu)$ and for
   (35) \begin{equation} \alpha_{i}(\mu)=2\Big(\mu(i)-\sum\limits_{\ell \in \overline{H}}\mu(\ell)\Big),\;\alpha_{j}(\mu)=2\Big(\mu(j)-\sum\limits_{\ell \in \overline{H}}\mu(\ell)\Big)\textrm{ and } \alpha_{k}(\mu)=2\mu(k). \end{equation}
   As $\overline{H}\in\mathcal{T}({\mathbb H})$, we have $\alpha_{i}(\mu)<0$ and $\alpha_{j}(\mu)<0$. From this, we deduce as above the existence of an integer $a_5^{*}$ such that $\Delta_H<0$ whenever $x_i\vee x_j \ge a_5^{*}$.

To conclude, if we let $\mathcal{K}$ be the finite set

\begin{equation*}{\mathcal K=\left\lbrace \textbf{x}\in{\mathcal E}\;:\;x_i\le \max\Big(a_1^*,...,a_5^*,2\Big);\; i\in V \right\rbrace,}\end{equation*}

then it follows from the above arguments that for any $\textbf{x}\in{\mathcal E}\cap\bar{\mathcal K}$ and any $n\in{\mathbb N}$,

\begin{equation*}{\mathbb E}\left[{Q\left(Y_{n+1}\right) - Q\left(Y_{n}\right) | Y_n=\textbf{x}}\right]<0.\end{equation*}

We deduce from the Lyapunov–Foster theorem (see [Reference Brémaud6, Section 5.1]) that the chain $\left\{{Y_n},\,n\in{\mathbb N}\right\}$ is positive recurrent. This is the case in turn for the chain $\left\{{X_n},\,n\in{\mathbb N}\right\}$.

In the following examples, we show how stability can be established for various incomplete 3-uniform hypergraphs using Theorem 2.

Corollary 3. Consider an incomplete 3-uniform hypergraph $\mathbb{H}'$ satisfying the assumptions of Theorem 2. Recall (21), and define the sets

\begin{equation*}\mathscr A({\mathbb H}')\,\;:\!=\;\biggl\{\mu\in\mathscr{M\,}(V)\,:\, \displaystyle\frac{\mu_{\mbox{max}}}{\mu_{\mbox{min}}}<\left(\frac{2q^4-9q^3+12q^2-13q+12}{6q^2+10q+24}\right)^{1/4}\biggl\}\,\end{equation*}

and

\begin{equation*}\mathscr{S\,}_1({\mathbb H}')\,\;:\!=\;\mathscr A({\mathbb H}')\,\cap\,\mathscr{N\,}_2(\mathbb H')\, \cap\mathscr{N\,}^{{-}}_3(\mathbb H'). \end{equation*}

Then the model $(\mathbb{H}',{ml},\mu)$ is stable for any $\mu\in\mathscr{S\,}_1({\mathbb H}').$

Proof. Recalling (31) and (32), simple algebra shows that

\begin{equation*}\mathscr A({\mathbb H}') \subset \biggl\{\mu\in\mathscr{M\,}(V):\left(\max\limits_{i\in J} \lambda_i(\mu)\vee \max\limits_{i\in \bar J} \nu_i(\mu)\right)<0\biggl\};\end{equation*}

thus $\mathscr{S\,}_1({\mathbb H}')\subset \mathscr{S\,}({\mathbb H}')$.

Example 6. Observe that for any such ${\mathbb H}'=(V,{\mathcal H}')$ satisfying the assumptions of Theorem 2, the model $(\mathbb{H}',{ml},\mu_{{u}})$ is stable for $\mu_{{u}}$ the uniform distribution on V. Indeed, we have $\mu_{{u}}\in\mathscr{S\,}_1({\mathbb H}')$. To see this, first observe that

\begin{equation*}\frac{2q^4-9q^3+12q^2-13q+12}{6q^2+10q+24}>1.\end{equation*}

Moreover, it is immediate that $\mu_{{u}}\in\mathscr{N\,}_3^-({\mathbb H}')$. It remains to show that $\mu_{{u}}\in\mathscr{N\,}_2({\mathbb H}')$. We proceed in three steps. First, for $q=5$ the only incomplete 3-uniform hypergraph in the sense of Theorem 2 is the complete hypergraph on $[\![ 1,5 ]\!]$ minus one hyperedge, say $\{1,2,3\}$. It is then easily seen that $\{4,5\}$ is the only minimal transversal of ${\mathbb H}'$. So $\tau({\mathbb H}')=2$, so that for all $T'\in\mathcal T({\mathbb H}')$, $\mu_{{u}}(T')\ge 2/5> 1/3,$ showing that $\mu_{{u}} \in \mathscr{N\,}_2({\mathbb H}')$.

Now, if $q=6$ there are two incomplete 3-uniform hypergraphs in the sense of Theorem 2: the complete 3-uniform hypergraph on $[\![ 1,6 ]\!]$ minus one hyperedge, say $\{1,2,3\}$, and the complete 3-uniform hypergraph on $[\![ 1,6 ]\!]$ minus two disjoint hyperedges, say $\{1,2,3\}$ and $\{4,5,6\}$. In both cases, $\{4,5,6\}$ is a minimal transversal of ${\mathbb H}'$, so $\tau({\mathbb H}')=3$, and thus $\mu_{{u}}(T')\ge 3/6 > 1/3$ for all $T'\in\mathcal T({\mathbb H})$, proving again that $\mu_{{u}} \in \mathscr{N\,}_2({\mathbb H}')$.

We now address the case where $q>6$. First observe that

(36) \begin{equation} q-2-\left\lfloor \frac{q}{3}\right\rfloor > \frac{q}{3}. \end{equation}

Then let $p=|\mathcal J|$ (using the notation of Theorem 2), and let $\mathcal J=\{H_1,...,H_p\}$. It is easily seen that a transversal of ${\mathbb H}$ can be constructed from any minimal transversal of ${\mathbb H}'$, by induction, as follows:

• • Take a minimal transversal T ^′ of ${\mathbb H}'$, and set ${\mathcal H}_0\,\;:\!=\;{\mathcal H}'$ and $T_0\,\;:\!=\;T'$.

• • For any $i=1,...,p$, set ${\mathcal H}_i = {\mathcal H}_{i-1} \cup \{H_i\}$, and let $T_i$ be a transversal of $(V,{\mathcal H}_i)$ of minimal size among those including $T_{i-1}$. (${T_{i}}$ necessarily exists since $T_{i-1}\cup \{H_i\}$ is a transversal of $(V,{\mathcal H}_{i})$, as easily seen by induction.)

• • We obtain ${\mathcal H}={\mathcal H}_p$ by construction, and $T\,\;:\!=\;T_p$ is a transversal of ${\mathbb H}$.

We claim that

(37) \begin{equation} |T| \le |T'|+p. \end{equation}

To see this, observe that for any $i=1,...,p$ we have the following alternative: either $H_i \cap T_{i-1} = \emptyset$, in which case we can take $T_i $ of the form $T_{i-1}\cup \{k\}$ for any $k\in H_i$, or $H_i \cap T_{i-1} \ne \emptyset$, in which case $T_i = T_{i-1}$. In all cases we have that $|T_i| \le |T_{i-1}| + 1$, and (37) follows by induction. Observing that $|T| \ge \tau(H)=q-2$ and that, as the $H_i$ are disjoint, $p\le \lfloor \frac{q}{3}\rfloor$, and using (36) and (37), we finally obtain that

\begin{equation*}\mu_{{u}}(T') = \frac{|T'|}{q} \ge \frac{|T|-p}{q} >\frac{1}{3}.\end{equation*}

Hence, once again, $\mu_{{u}} \in \mathscr{N\,}_2({\mathbb H}')$.

To conclude, $\mu_{{u}}$ is in all cases an element of $\mathscr{S\,}_1({\mathbb H}')$, implying that the model $(\mathbb{H}',{ml},\mu_{{u}})$ is stable for all such ${\mathbb H}'$.