1 Introduction↩︎

In this paper, a graphon \(W\) is a measurable function \(W: [0,1]^2 \to [0,1]\). The graphon \(W\) is said to be symmetric if \(W(s,t) = W(t,s)\) for almost all \((s,t)\in [0,1]^2\). We do not require that \(W\) be symmetric. We treat graphon as a stochastic model and investigate its hamiltonicity. Specifically, we sample a directed graph \(\vec{G}_n \sim W\) from a graphon \(W\) on \(n\) nodes via the following two-step procedure:

1. Sample \(t_1, \ldots, t_n \sim \text{Uni}[0,1]\) independently, where \(\text{Uni}[0,1]\) is the uniform distribution over the interval \([0,1]\). We call \(t_i\) the coordinate of node \(v_i\).

2. For each pair of distinct nodes \(v_i\) and \(v_j\), place independently a directed edge from \(v_i\) to \(v_j\) with probability \(W(t_i, t_j)\) and a directed edge from \(v_j\) to \(v_i\) with probability \(W(t_j, t_i)\).

A digraph \(\vec{G}\) is said to have a node-wise Hamiltonian decomposition if it contains a subgraph \(\vec{H}\), with the same node set as \(\vec{G}\), such that \(\vec{H}\) is a node-wise disjoint union of directed cycles of \(\vec{G}\). If, further, \(\vec{H}\) is a cycle (so it visits every node of \(\vec{G}\)), then \(\vec{H}\) is said to be a Hamiltonian cycle of \(\vec{G}\). We evaluate the probability that \(\vec{G}_n \sim W\) has a Hamiltonian decomposition or cycle as \(n\to\infty\). A precise problem formulation will be given shortly.

Our interest in Hamiltonian decomposition is rooted in structural system theory, which deals with the problem of understanding what type of network topology can sustain a desired system property. To elaborate, consider a network of \(n\) mobile agents whose communication topology is described by a digraph \(G\), where the nodes represent the agents and the edges indicate the information flows. More specifically, a directed edge from \(v_j\) to \(v_i\) indicates that agent \(x_i\) can access the state information of agent \(x_j\), so the dynamics of \(x_i\) are allowed to depend on the state of \(x_j\). Said in other words, if the dynamics of the network system obey the differential equation \(\dot{x}_i = f_i(x(t))\), for all \(i = 1,\ldots, n\), with each \(f_i\) a differentiable function, then \(\partial f_i(x)/\partial x_j \neq 0\) only if there is an edge from \(v_j\) to \(v_i\) in \(G\). We call such dynamics compatible with \(G\). The central question of the structural system theory is then the following: Given the digraph \(G\) and given a desired system property (e.g., asymptotic stability with respect to the origin), is there a dynamical system \(\dot{x} = f(x)\) such that it is compatible with \(G\) and satisfies the property? This framework can be extended to controlled system \(\dot{x} = f(x, u)\), taking into account the constraint that for each control input \(u_j\), there may be only few agents \(x_i\) under its direct influence, i.e., \(\partial f_i(x)/\partial u_j \neq 0\).

It has been shown that existence of a Hamiltonian decomposition is essential for a network topology to sustain controllability [1] and stability [2], two of the fundamental properties of a dynamical control system. When a multi-agent system operates in an uncertain and/or adversarial environment, its network topology becomes a random object. We use a graphon \(W\) to represent the environment uncertainty and the random digraph \(\vec{G}_n \sim W\) to represent the network topology, so the probability that an ordered pair of agents establishes an oriented communication link depends on their respective positions. The knowledge about how likely the network topology of a large-scale multi-agent system can have a Hamiltonian decomposition is critical for a network manager to understand whether the environment is in favor of or against them, to evaluate the risk-to-reward ratio, and to decide whether the system shall be deployed.

We start by introducing the class of step-graphons:

We illustrate the definition of step-graphon in Figure [sfig1:stepgraphon].

We show in this paper that the (strong) \(H\)-property is essentially a zero-one property for the class of step-graphons. Specifically, we show that for almost all step-graphons \(W\), the limit on the left hand side of ?? or ?? is either zero or one. We present in the next section necessary and sufficient conditions for a graphon \(W\) to have the (strong) \(H\)-property.

The Main Theorem of this paper, which we present in Subsection 2.2, strengthens and generalizes the results of our earlier work [3], [4], in which we addressed only the \(H\)-property for the class of symmetric step-graphons. Specifically, given a symmetric step-graphon \(W\), we sample an undirected graph \(G_n\sim W\) by placing an undirected edge between any two distinct nodes \(v_i\) and \(v_j\) with probability \(W(t_i, t_j)\). We then obtain from \(G_n\) a directed graph \(\vec{G}_n^\mathsf{s}\) by replacing every undirected edge with a pair of oppositely oriented edges—we call such digraph symmetric. The step-graphon \(W\) is said to have the \(H\)-property if \(\vec{G}_n^\mathsf{s}\sim W\) has a Hamiltonian decomposition asymptotically almost surely (a.a.s.). We introduced in [3] a set of conditions that are necessary for \(W\) to have the \(H\)-property. Then, in [4], we showed that the same set of conditions is essentially sufficient. More specifically, we showed that if \(W\) satisfies the conditions, then a.a.s. \(\vec{G}^\mathsf{s}_n\) has a Hamiltonian decomposition which comprises mostly the \(2\)-cycles. The main result of this paper, when specialized to symmetric step-graphons, implies that \(\vec{G}^\mathsf{s}_n\sim W\) has a Hamiltonian cycle a.a.s.. The residual case where the probability that \(\vec{G}_n^\mathsf{s}\sim W\) has a Hamiltonian decomposition converges to neither zero nor one has been investigated in [5].

At the end of this section, we gather a few key notations and terminologies used throughout the paper.

In this paper, we consider both directed and undirected graphs. We will put an arrow on top of the letter (e.g., \(\vec{G}\)) to indicate that the graph it refers to is directed. All graphs considered in the paper do not have multiple edges, but can have self-loops. For a graph \(\vec{G}\), let \(V(\vec{G})\) and \(E(\vec{G})\) be its node set and edge set, respectively. We use \(v_iv_j\) to denote a directed edge from \(v_i\) to \(v_j\), and use \((v_i,v_j)\) to denote an undirected edge between \(v_i\) and \(v_j\). A digraph \(\vec{G}\) is said to be strongly connected if for any two distinct nodes \(v_i\) and \(v_j\), there exist a path from \(v_i\) to \(v_j\) and a path from \(v_j\) to \(v_i\).

Let \(\mathbb{R}_{>0}\) (resp., \(\mathbb{R}_{\geq 0}\)) be the set of positive (resp., nonnegative) real numbers. Let \(\mathbb{N}\) (resp., \(\mathbb{N}_0\)) be the set of positive (resp., nonnegative) integers.

Let \(\mathbf{1}\) be the vector of all ones, and \(e_i\) be the \(i\)th column of the identity matrix. Their dimension will be clear in the context. The support of a vector \(x\), denoted by \(\operatorname{supp}(x)\), is the set of indices \(i\) such that \(x_i\neq 0\). Similarly, the support of a matrix \(A = [a_{ij}]\), denoted by \(\operatorname{supp}(A)\), is the set of indices \(ij\) such that \(a_{ij} \neq 0\). We will relate the support of a vector (resp., square matrix) to the node (resp., edge) set of a digraph. Specifically, for a vector \(x\in \mathbb{R}^n\) and for a digraph \(\vec{G}\) on \(n\) nodes, we can treat \(\operatorname{supp}(x)\) as a subset of \(V(\vec{G})\) where \(v_i \in \operatorname{supp}(x)\) if and only if \(x_i \neq 0\). Similarly, we treat \(\operatorname{supp}(A)\) as a subset of \(E(\vec{G})\) where \(v_iv_j\in E(\vec{G})\) if and only if \(a_{ij} \neq 0\). For a subgraph \(\vec{G}'\) of \(\vec{G}\), we let \(x|_{\vec{G}'}\) be the sub-vector of \(x\) obtained by deleting any entry \(x_i\) such that \(v_i\notin \vec{G}'\).

2 Main Result↩︎

In this section, we identify the key objects associated with a step-graphon that matter for the (strong) \(H\)-property, and formulate a set of conditions about these objects for deciding whether a step-graphon has the (strong) \(H\)-property—this is the Main Theorem of the paper. We then illustrate and numerically validate the result. Toward the end, we provide a sketch of proof of the Main Theorem, highlighting the ideas and techniques that will be used to establish the result.

2.1 Key objects↩︎

In this subsection, we introduce four key objects that are essential to deciding whether a step-graphon has the (strong) \(H\)-property. We start by introducing the definitions of concentration vector and of skeleton graph, which were introduced in [3], [4] for symmetric graphons but can be naturally extended to the general case here:

Next, we have

Note that the concentration vector \(x^*\) and the skeleton graph \(\vec{S}\) depend only on (and also, uniquely determine) the support of \(W\).

The next two objects are derived from the skeleton graph \(\vec{S}\), which are the node-cycle incidence matrix \(Z\) and the node-flow cone \(\mathsf{X}\), i.e., the convex cone spanned by the column vectors of \(Z\). We elaborate more on its name after the definition. These two objects will serve as the counterparts of the node-edge incidence matrix and of the edge-polytope that matter for the special case where we sample symmetric digraphs from symmetric graphons.

To this end, we label the cycles of \(\vec{S}\) as \(\vec{C}_1,\ldots, \vec{C}_k\). A self-loop is a cycle of length \(1\).

In [3], [4], it was shown that the rank of the node-edge incidence matrix is a deciding factor for determining the \(H\)-property of a symmetric graphon. We will see soon the same holds for the case here. We define the co-rank of \(Z\) as \[\operatorname{co-rank}(Z) := m - \operatorname{rank}(Z),\] so \(Z\) has full row rank if and only if \(\operatorname{co-rank}(Z) = 0\). It is known [6] that the node-edge incidence matrix of an undirected graph has full row rank if and only if every connected component of the graph has an odd cycle. Similarly, the rank of the node-cycle incidence matrix can also be related to some relevant property of \(\vec{S}\) (more precisely, the bipartite graph associated with \(\vec{S}\)). Since this graphical condition plays an important role in the analysis, we introduce it below.

We associate to the digraph \(\vec{S}\) an undirected bipartite graph \(B_{\vec{S}}\) with \(2m\) nodes: The node set \(V(B_{\vec{S}})\) is a disjoint union of two subsets \[V'(B_{\vec{S}}) = \{u'_1,\ldots, u'_m\} \quad and \quad V''(B_{\vec{S}}) = \{u''_1,\ldots, u''_m\}.\] The edge set \(E(B_{\vec{S}})\) is such that \[(u'_i, u''_j)\in E(B_{\vec{S}}) \quad \Longleftrightarrow \quad u_iu_j\in E(\vec{S}).\] The correspondence between \(\vec{S}\) and \(B_{\vec{S}}\) is illustrated in Figure 2.

Let \(\vec{S}_1, \ldots, \vec{S}_q\) be the strongly connected components (SCCs) of \(\vec{S}\). We recall that they satisfy the following three (defining) conditions: (1) Every subgraph \(\vec{S}_p\), for \(p = 1,\ldots, q\), is strongly connected; (2) The node sets \(V(\vec{S}_1), \ldots, V(\vec{S}_q)\) form a partition of \(V(\vec{S})\); (3) If \(\vec{S}'\) is any other strongly connected subgraph of \(\vec{S}\), then \(\vec{S}'\) is contained in some \(\vec{S}_p\), for \(p = 1,\ldots, q\).

The following result can be obtained from [7], which provides an explicit formula for the co-rank of \(Z\):

To illustrate, consider the skeleton graph \(\vec{S}\) in Figure [sfig:bipar1]. To obtain the co-rank of \(Z\), one way is to use the brute-force approach, i.e., we find all the cycles of \(\vec{S}\), construct the node-cycle incidence matrix \(Z\), and compute its co-rank. In this case, \(\vec{S}\) has \(4\) cycles: \[\label{eq:cyclesofexampleS} \vec{C}_1 = u_4u_4, \quad \vec{C}_2 = u_3u_4u_3, \quad \vec{C}_3 = u_1 u_2 u_3 u_4 u_1, \quad and \quad \vec{C}_4 = u_2u_3u_2.\tag{1}\] Thus, \[\label{eq:defmatrixZ} Z = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix}, \quad so\operatorname{co-rank}(Z) = 0.\tag{2}\] Another approach is to appeal to Lemma 1: In this case, \(\vec{S}\) is strongly connected and the associated bipartite graph, shown in Figure [sfig:bipar2], is connected, so \(\operatorname{co-rank}(Z) = 0\).

Finally, we introduce the following object:

It is clear that \(\dim \mathsf{X}= \operatorname{rank}(Z)\).

The convex cone \(\mathsf{X}\) has close relations with flows. To elaborate, recall that a flow \(f\) on \(\vec{S}\) is a map \(f:E(\vec{S}) \to \mathbb{R}_{\geq 0}\) satisfying the following balance condition at every node \(u_i\): \[\label{eq:balancecondition} \sum_{u_k: u_ku_i\in E(\vec{S})} f(u_ku_i) = \sum_{u_j: u_iu_j\in E(\vec{S})} f(u_iu_j) =: y_i(f).\tag{3}\] It is not hard to see that \(\mathsf{X}\) is the set of vectors \(y(f):= (y_1(f),\ldots, y_m(f))\) for all flows \(f\).

2.2 Necessary and sufficient conditions for (strong) \(H\)-property↩︎

In this subsection, we state an essentially necessary and sufficient condition for a step-graphon \(W\) to have the (strong) \(H\)-property. Let \(\sigma\) be a partition for \(W\), and \(x^*\), \(S\), \(Z\), and \(\mathsf{X}\) be the associated concentration vector, skeleton graph, node-cycle incidence matrix, and node-flow cone, respectively. We now introduce the following conditions:

Condition \(A\):

\(\operatorname{co-rank}(Z) = 0\).

Condition \(B\):

\(x^*\in \operatorname{int}\mathsf{X}\), where \(\operatorname{int}\mathsf{X}\) stands for the relative interior of \(\mathsf{X}\).

Condition \(B'\):

\(x^*\in \mathsf{X}\).

Condition \(C\):

\(\vec{S}\) is strongly connected.

These four conditions, though stated with respect to a specific \(\sigma\), are in fact invariant under the choice of a partition. Precisely, we have

Note that for item 1, the hypothesis that both \(\vec{S}\) and \(\vec{S}'\) have at least two nodes is necessary, ruling out the special case where \(W\) is the zero function. To wit, if \(W = 0\) and if the partition \(\sigma\) is chosen such that \(\sigma = (0,1)\), then the associated skeleton graph \(\vec{S}\) comprises a single node \(u\) without self-loop. By default, \(\vec{S}\) is strongly connected. However, any other partition \(\sigma'\) for \(W\) gives rise to a skeleton graph \(\vec{S}'\) such that \(\vec{S}\) has multiple nodes but without any edge.

We provide a proof of the above Proposition 1 in Appendix 7. With the result, we can now have the following definition:

With the above definition, we can now state the main result of the paper:

As mentioned earlier, the Main Theorem extends the results of [3], [4]. We substantiate our claim in Appendix 8, where we specialize the Main Theorem to step-graphons with symmetric support.

2.3 Illustration and numerical validation↩︎

To illustrate the Main Theorem, we consider the four step-graphons in Figure 3. Over their respective support, \(W_a\) takes value \(0.2\) while \(W_b\), \(W_c\), and \(W_d\) take value \(1\). We let the partitions for the four step-graphons be \[\begin{align} \sigma_a & = \frac{1}{16}(0,1,4,9,16), & \sigma_b = \frac{1}{8}(0,1,3,6,8), \\ \sigma_c & = \frac{1}{20}(0,5,10,16,20), &\sigma_d = \frac{1}{8}(0,1,3,6,8). \end{align}\] The step-graphons in (a), (b), (c) share the same skeleton graph \(\vec{S}\) as shown in (e), which is the same as the one in Figure [sfig2:stepgraphon]. The skeleton graph \(\vec{S}'\) associated with the step-graphon in (d) is shown in (f), which can be obtained from \(\vec{S}\) by removing the self-loop \(u_4u_4\).

The skeleton graph \(\vec{S}\) has \(4\) cycles \(\vec{C}_1,\ldots, \vec{C}_4\) as shown in 1 . The node-cycle incidence matrix \(Z\) has full row rank as argued in 2 . The digraph \(\vec{S}'\), being a subgraph of \(\vec{S}\), has only three cycles \(\vec{C}_2, \vec{C}_3, \vec{C}_4\). Its node-cycle incidence matrix \(Z'\) is given by \[\label{eq:defmatrixZ39} Z' := \begin{bmatrix} 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \end{bmatrix}, \quad so \operatorname{co-rank}(Z') = 1.\tag{4}\]

We state without a proof that any three column vectors of \(Z\) form a facet-defining hyperplane of the cone \(\mathsf{X}\). For each \(i = 1,\ldots,4\), we let \(L_i\) be the subspace spanned by the \(z_j\)’s, for \(j\neq i\). Let \(g_i\in \mathbb{R}^4\) be the normal vector perpendicular to \(L_i\) of unit length such that \(g_i^\top z_i > 0\). Then, it is not hard to obtain that \[g_1 = \frac{1}{2}(-1,1,-1,1), \quad g_2 = \frac{1}{\sqrt{2}}(0,-1,1,0), \quad g_3 = (1,0,0,0), \quad g_4 = \frac{1}{\sqrt{2}}(-1,1,0,0).\] Then, using the half-space representation, we can write \[\mathsf{X}= \{y\in \mathbb{R}^4 \mid g_i^\top y \geq 0, \quad for alli = 1,\ldots, 4\}.\]

We numerically validate the necessity and sufficiency of Conditions \(A\), \(B\) (or \(B'\)) for the step-graphon \(W_\star\), for \(\star = a,b,c,d\) to have the \(H\)-property. For each case (a)—(d) and for each \(n = \{10, 50, 100, 500, 1000, 2000, 5000\}\), we sample \(20,000\) random graphs \(\vec{G}_n \sim W\) and plot the empirical probability \(p(n)\) that \(\vec{G}_n\) has a Hamiltonian decomposition, i.e., \[p(n):= \frac{number of\vec{G}_n\sim Whas a Hamiltonian decomposition}{20,000}.\]

The concentration vector is \(x^*_a = \frac{1}{16}(1,3,5,7)\). It belongs to the relative interior of \(\mathsf{X}\) as we can express \(x^*_a\) as a positive combination of the \(z_j\)’s (the column vectors of \(Z\) given in 2 ): \[x^*_a = \frac{1}{4} z_1 + \frac{1}{8} z_2 + \frac{1}{16} z_3 + \frac{1}{8} z_4.\] Also, the matrix \(Z\) has full row rank. Thus, \(W_a\) satisfies Conditions \(A\) and \(B\). We see from the simulation that the empirical probability \(p(n)\) converges to \(1\).

The concentration vector is \(x^*_b = \frac{1}{8}(1,2,3,2)\). It belongs to the boundary of \(\mathsf{X}\), i.e., \(x^*_b \in \mathsf{X}- \operatorname{int}\mathsf{X}\). To wit, we note that \(x^*_b\) is in the facet-defining hyperplane \(L_1\) spanned by \(z_2\), \(z_3\), and \(z_4\): \[x^*_b = \frac{1}{8} (z_2 + z_3 + z_4).\] Thus, \(W_b\) satisfies Conditions \(A\) and \(B'\), but not \(B\). We see from the simulation that the empirical probability \(p(n)\) converges to neither \(1\) nor \(0\). In fact, using the same arguments as in [5], we can show that the probability converges to \(0.5\), as demonstrated in the figure as well.

The concentration vector is \(x^*_c = \frac{1}{20}(5,5,6,4)\). Since \(g_1^\top x^*_c < 0\), \(x^*_c\) does not belong to \(\mathsf{X}\). Thus, \(W_c\) satisfies Condition \(A\) but not \(B'\). We see from the simulation that the empirical probability \(p(n)\) converges to \(0\).

The concentration vector is \(x^*_d = \frac{1}{8}(1,2,3,2)\), same as the one in Case (b). As argued above, we can write \(x^*_d\) as a positive combination of \(z_2\), \(z_3\), and \(z_4\), which are the three column vectors in \(Z'\). Thus, \(x^*_d\in \operatorname{int}\mathsf{X}'\). Also, as shown in 4 , \(Z'\) does not have full row rank. Thus, \(W_d\) satisfies Condition \(B\) but not \(A\). We see from the simulation that the empirical probability \(p(n)\) converges to \(0\).

2.4 Sketch of proof for the Main Theorem↩︎

We start by introducing two objects, which will be relevant to both necessity and sufficiency of Conditions \(A\), \(B\)/\(B'\) (and \(C\)) for the (strong) \(H\)-property.

For an \(\vec{S}\)-partite graph \(\vec{G}\), we let \[y(\vec{G}) := (y_1, \ldots, y_m) \quad withy_i:= |\pi^{-1}(u_i)|, \quad for alli = 1,\ldots, m.\] Further, for a given vector \(y \in \mathbb{N}^m_0\), we let \(\vec{K}_y(\vec{S})\) (or simply \(\vec{K}_y\)) be the complete \(\vec{S}\)-partite graph, with \(y(\vec{K}_y) = y\).

The relevance of \(\vec{S}\)-partite graphs is apparent. Any random graph \(\vec{G}_n\) sampled from \(W\) is \(\vec{S}\)-partite, where the homomorphism \(\pi: \vec{G}_n \to \vec{S}\) is naturally the one that sends each node \(v_j\in \vec{G}_n\), with coordinate \(t_j\in [\sigma_{i-1}, \sigma_i)\), to \(u_i\). It is also clear from the sampling procedure (more specifically, step \(S1\)) that \(y(G_n)\) is a multinomial random variable with \(n\) trials, \(m\) events, and \(x^*_i\)’s the event probabilities. Let \[\label{eq:defxGn} x(\vec{G}_n) := \frac{1}{n}y(\vec{G}_n).\tag{5}\] We call \(x(\vec{G}_n)\) the empirical concentration vector. It follows directly from the law of large numbers that \[\label{eq:empiricalx} x(G_n) \to x^*{\em a.a.s.}.\tag{6}\]

Next, for a square matrix \(A = [a_{ij}] \in \mathbb{R}^{m\times m}\), let \(\operatorname{supp}(A)\) be the support of \(A\), i.e., it is the set of indices \(ij\) such that \(a_{ij} \neq 0\). One can also identify the index \(ij\) with a directed edge \(u_iu_j\) of a digraph \(\vec{S}\) on \(m\) nodes. We have the following definition:

It is clear from the definition that \(\mathsf{A}\) is a convex cone. Its relation to flows is as follows: Let \(f: E(\vec{S})\to \mathbb{R}_{\geq 0}\) be a flow, and let \(A(f) = [a_{ij}(f)]\) be such that \[a_{ij}(f) := \begin{cases} f(u_iu_j) & ifu_i u_j \in E(\vec{S}), \\ 0 & otherwise. \end{cases}\] The balance condition 3 of \(f\) guarantees that ?? is satisfied, so \(A(f)\in \mathsf{A}\). It turns out that \(\mathsf{A}\) is the set of \(A(f)\) for all flows \(f\) on \(\vec{S}\). In particular, the two sets \(\mathsf{X}\) and \(\mathsf{A}\) relate to each other in the following way: \[\label{eq:relationya} \mathsf{X}= \mathsf{A}\mathbf{1}= \{A\mathbf{1}\mid A \in \mathsf{A}\}.\tag{7}\]

Our use of the edge-flow cone is through the Hamiltonian decompositions of \(\vec{S}\)-partite graphs. Specifically, if \(\vec{G}\) is an \(\vec{S}\)-partite graph and if \(\vec{G}\) has a Hamiltonian decomposition \(\vec{H}\), then \(\vec{H}\) induces an integer valued flow \(f_{\vec{H}}\) on \(\vec{S}\) in the way such that \(f_{\vec{H}}(u_iu_j)\) records the total number of edges used in \(\vec{H}\) from the nodes in \(\pi^{-1}(u_i)\) to the nodes in \(\pi^{-1}(u_j)\). Consider, for example, the digraph \(\vec{G}_{n}\) in Figure [sfig2:samplegraph], with \(n = 10\). It has a Hamiltonian decomposition \(\vec{H}\) highlighted in blue. Then, the corresponding \(A\)-matrix is given by \[A(f_{\vec{H}}) = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 1 & 0 & 2 \\ 1 & 0 & 1 & 2 \end{bmatrix}.\] It follows from the construction that \[\label{eq:ymustinx} y(\vec{G}) = A(f_{\vec{H}}) \mathbf{1}\in \mathsf{X}.\tag{8}\] See Lemma 3 for a proof.

With the \(\vec{S}\)-partite graphs and the edge-flow cone introduced above, we now sketch the proof of the Main Theorem:

2.4.1 On necessity of Conditions \(A\), \(B'\), and \(C\)↩︎

As argued above, if \(\vec{G}_n\sim W\) has a Hamiltonian decomposition, then \(y(\vec{G}_n)\in \mathsf{X}\). Thus, to establish the necessity of Conditions \(A\) and \(B'\) for the \(H\)-property (more precisely, to establish ?? ), it suffices to show that \[\neg A \, (\operatorname{co-rank}(Z) > 0)or\neg B' \, (x^*\notin \mathsf{X}) \quad \Longrightarrow \quad y(\vec{G}_n)\notin \mathsf{X} {\em a.a.s.}.\] The proof that \[\neg B' \quad \Longrightarrow \quad y(\vec{G}_n) \notin \mathsf{X} {\em a.a.s.}\] is straightforward, following directly from 6 . The proof that \[\neg A \quad \Longrightarrow \quad y(\vec{G}_n) \notin \mathsf{X} {\em a.a.s.}\] uses the following arguments: Let \(\Delta^{m-1}\) be the standard simplex in \(\mathbb{R}^m\) and \(\overline{\mathsf{X}}:= \mathsf{X}\cap \Delta^{m-1}\). It is not hard to see that \(y(G_n) \in \mathsf{X}\) if and only if \(x(G_n)\in \overline{\mathsf{X}}\), where we recall that \(x(G_n)\) is the empirical concentration vector 5 . Note that if \(\operatorname{co-rank}(Z) \geq 1\), then \(\dim \overline{\mathsf{X}}< \dim \Delta^{m-1} = m - 1\). Appealing to the central limit theorem, we have that the random variable \(\omega(G_n) = \sqrt{n}(x(G_n) - x^*) + x^*\) converges in distribution to the Gaussian random variable \(\omega^*\) whose support is known to be the entire hyperplane that contains \(\Delta^{m-1}\). As a consequence, it holds that \(x(G_n)\notin \overline{\mathsf{X}}\) a.a.s..

The necessity of Condition \(C\) (\(\vec{S}\) is strongly connected) for the strong \(H\)-property follows from the fact if \(\vec{H}\) is a Hamiltonian cycle of \(\vec{G}_n\), then \(\pi(\vec{H})\) is a closed walk of \(\vec{S}\). It is an immediate consequence of 6 that \(\pi(\vec{H})\) visits every node of \(\vec{S}\) a.a.s., and hence, \(\vec{S}\) must be strongly connected.

A complete proof of the necessity part will be presented in Section 3.

2.4.2 On sufficiency of Conditions \(A\), \(B\), and \(C\)↩︎

We introduce a subset \(\mathsf{X}_0\) of \(\mathsf{X}\), which comprises all integer-valued \(y\in \mathsf{X}\) such that \(\|y\|_1\) is sufficiently large and \(y/\|y\|_1\) is sufficiently close to \(x^*\). A precise definition of \(\mathsf{X}_0\) will be given at the beginning of Section 5. The two conditions \(A\) and \(B\), together with 6 , guarantee that \(y(G_n)\in \mathsf{X}_0\) a.a.s.. The major task is then to show that \[\begin{gather} \label{eq:task1} x(G_n) \in \mathsf{X}_0(and\vec{S}is strongly connected) \quad \Longrightarrow \quad \\ G_nhas a Hamiltonian decomposition (cycle) {\em a.a.s.}. \end{gather}\tag{9}\] To accomplish the task, we take a two-step approach:

We show that if \(y\in \mathsf{X}_0\) (and if \(\vec{S}\) is strongly connected), then the complete \(\vec{S}\)-partite graph \(\vec{K}_y\) has a Hamiltonian decomposition (cycle). The proof builds upon the following facts:

1. The first fact is a strengthened version [8] of the equality \(\mathsf{X}= \mathsf{A}\mathbf{1}\), which states that if \(y \in \mathsf{X}\) is integer valued, then there exists an integer-valued \(A\in \mathsf{A}\) such that \(A\mathbf{1}= y\).

2. We then express the matrix \(\mathsf{A}\), obtained from above, as an integer combination of the adjacency matrices \(A_j\) associated with the cycles \(\vec{C}_j\) of \(\vec{S}\), i.e., we write \(A = \sum_{j = 1}^k c_j A_j\) for \(c_j \in \mathbb{N}_0\) (and \(c_j\in \mathbb{N}\) in the case \(y\in \mathsf{X}_0\)). We show that \(\vec{K}_y\) has a Hamiltonian decomposition, which contains \(c_j\) cycles that are isomorphic to \(\vec{C}_j\) under the map \(\pi: \vec{K}_y \to \vec{S}\).

3. If, further, \(\vec{S}\) is strongly connected, then the cycles of the Hamiltonian decomposition exhibited above can be used to form a desired Hamiltonian cycle. The proof relies on the use of the induction hypothesis on the number of cycles in \(\vec{S}\) and the (directed) ear decomposition of \(\vec{S}\).

Complete arguments for this step will be presented in Section 5.

Let \(\vec{H}_y\) be the Hamiltonian decomposition (cycle) of \(\vec{K}_y\) obtained in Step 1. We show that \(\vec{G}_n\) contains \(\vec{H}_{y(\vec{G}_n)}\) as a subgraph a.a.s.. Precisely, let \(\psi_y: \vec{H}_y \to \vec{K}_y\) be the embedding. Composing \(\psi_y\) with \(\pi\), we obtain the map \(\pi\cdot \psi_y: \vec{H}_y \to \vec{S}\). We show that a.a.s. there exists an embedding \(\phi: \vec{H}_{y(\vec{G}_n)} \to \vec{G}_n\) such that \(\phi\) is compatible with \(\psi_{y(\vec{G}_n)}\), i.e., \(\pi\cdot \phi = \pi\cdot \psi_{y(\vec{G}_n)}\). The proof relies on the use of the Blow-up Lemma [9]. Roughly speaking, the lemma states that if an undirected graph \(H\) has its degree bounded above by a constant and if it can be embedded into a complete \(S\)-partite graph \(K_y\), where \(S\) is an undirected graph without self-loop, then the graph \(H\) can be embedded into any \(S\)-partite graph \(G\), with \(y(G) = y\), as long as \(G\) satisfies some regularity condition. To enable its use, we take the following steps:

1. In Section 4, we show that if the step-graphon \(W\) has a nonzero diagonal block (i.e., \(\vec{S}\) has a self-loop) and satisfies Condition \(\star\), for \(\star = A, B, C\), then there is a step-graphon \(W'\) such that \(W'\leq W\) (i.e., \(W'(s,t)\leq W(s,t)\) for all \((s,t)\in [0,1]^2\)), \(W'\) satisfies Condition \(\star\) and, moreover, \(W'\) is “loop free”, i.e., the associated skeleton graph does not have any self-loop. This fact, combined with the monotonicity of the (strong) \(H\)-property, allow us to consider only the class of loop-free step-graphons for establishing the sufficiency of Conditions \(A\), \(B\), and \(C\).

2. In Section 6. we introduce an auxiliary symmetric step-graphon \(W^{\mathsf{s}}\), which is derived from \(W\), together with an auxiliary sampling procedure that allows us to draw undirected random graphs \(G_n\) from \(W^{\mathsf{s}}\). The graphon \(W^{\mathsf{s}}\) and the sampling procedure are defined in a way such that the probability that \(\vec{H}_{y(\vec{G}_n)}\) is embeddable into \(\vec{G}_n\) is bounded above by the probability that \(H_{y(G_n)}\) is embeddable into \(G_n\), where \(H_{y(G_n)}\) is the undirected counterpart of \(\vec{H}_{y(\vec{G}_n)}\).

We then complete the proof by showing that a.a.s. the random graph \(G_n\) satisfies the aforementioned regularity condition. Thanks to the Blow-up lemma, \(H_{y(G_n)}\) can be embedded into \(G_n\) a.a.s..

3 On Necessity of Conditions \(A\), \(B'\), and \(C\)↩︎

In this section, we establish (i ) the necessity of Conditions \(A\) (i.e., \(\operatorname{co-rank}Z = 0\)) and \(B'\) (i.e., \(x^*\in \mathsf{X}\)) for the \(H\)-property, and (ii ) the necessity of Condition \(C\) (i.e., \(\vec{S}\) is strongly connected) for the strong \(H\)-property. The arguments for proving part (i ) are similar to those used in [3], which dealt with symmetric step-graphons. For completeness of the presentation, we include the proofs of the relevant lemmas (but omit those for lemmas with exactly the same statements).

Recall that \(\mathsf{A}\) is the edge-flow cone introduced in Definition 9. For each cycle \(\vec{C}_j = u_{j_1}u_{j_2}\cdots u_{j_d}u_{j_1}\) of \(\vec{S}\). We let \(A_j\) be the adjacency matrix associated with \(\vec{C}_j\): \[\label{eq:defAj} A_j := \sum_{i = 1}^{d} e_{j_i}e_{j_{i + 1}}^\top,\tag{10}\] where \(j_{d + 1}\) is identified with \(j_1\). It is clear that \(A_j \in \mathsf{A}\) and that \[\label{eq:relationbetweenzandA} z_j = A_j \mathbf{1}.\tag{11}\] We have the following result:

The next result establishes the necessity of \(y(\vec{G}_n)\in \mathsf{X}\) for an \(\vec{S}\)-partite graph to have a Hamiltonian decomposition:

With Lemma 3 above, we establish the necessity of Condition \(B'\).

Next, given \(\vec{G}_n \sim W\), we define \[\label{eq:defomegan} \omega(\vec{G}_n):= \sqrt{n}(x(\vec{G}_n) - x^*) + x^*.\tag{13}\] The following result is known [3]:

With Lemmas 3 and 4, we establish the necessity of Condition \(A\):

Finally, we establish the necessity of Condition \(C\):

4 Pre-processing: Removal of self-loops↩︎

Let \(W\) be a step-graphon and \(\sigma = (\sigma_0, \ldots, \sigma_{m-1}, \sigma_*)\) be a partition for \(W\), with \(\sigma_0 = 0\) and \(\sigma_* = 1\). Let \(\vec{S}\) be the associated skeleton graph, and \(\vec{S}_1,\ldots, \vec{S}_q\) be the SCCs of \(\vec{S}\). Suppose that the skeleton graph \(\vec{S}\) associated with \(W\) has a self-loop, say, on node \(u_m\). Without loss of generality, we assume that \(u_m\in V(\vec{S}_q)\) and the partition \(\sigma\) is fine enough such that \(\vec{S}_q\) has at least two nodes.

We introduce a new step-graphon \(W'\) as follows. First, let \[\label{eq:defsigmam} \sigma_m:= \frac{1}{2}(\sigma_{m-1} + 1).\tag{19}\] Then, we set \[\label{eq:defW39} W'(s,t) := \begin{cases} 0 & if(s,t)\in [\sigma_{m-1}, \sigma_m)^2 \cup [\sigma_m,1]^2,\\ W(s,t) & otherwise. \end{cases}\tag{20}\] In words, \(W'\) is obtained from \(W\) by first subdividing the block \(R_{mm} = [\sigma_{m-1},1]^2\) into four sub-blocks: \[\begin{align} R_{mm, 11} &:= [\sigma_{m-1},\sigma_m)^2, \quad & R_{mm,12} & := [\sigma_{m-1},\sigma_m) \times [\sigma_m, 1], \\ R_{mm,21}&:= [\sigma_m,1] \times [\sigma_{m-1},\sigma_m), & R_{mm, 22} &:= [\sigma_m, 1]^2. \end{align}\] and then, setting the value of \(W(s,t)\) to \(0\) if \((s,t)\in R_{mm,11} \cup R_{mm,22}\) while keeping \(W(s,t)\) unchanged otherwise. See Figure 4 for illustration.

The goal of this section is to show that \(W'\) inherits any Condition \(\star\), for \(\star = A, B, C\), satisfied by \(W\). Precisely, we have

Let \(\sigma':= (\sigma_0,\ldots,\sigma_{m-1}, \sigma_m, \sigma_*)\). It is clear that \(\sigma'\) is a partition for \(W'\). Let \(x'^*\), \(\vec{S}'\), \(Z'\), and \(\mathsf{X}'\) be the concentration vector, the skeleton graph, the node-cycle incidence matrix, and the node-flow cone of \(W'\) for \(\sigma'\), respectively. With slight abuse of terminology, we say that \(\vec{S}'\) is obtained from \(\vec{S}\) by performing the surgery on node \(u_m\). It is clear that \(\vec{S}'\) has one less self-loop than \(\vec{S}\) does.

If \(W'\) still has a nonzero diagonal block (equivalently, \(\vec{S}'\) has a self-loop), then we perform the surgery again for \(W'\) (resp., \(\vec{S}'\)) on the corresponding block (resp. node). Iterating this procedure until we obtain a graphon which admits a partition such that its associated skeleton graph does not have any self-loop. We introduce the following definition:

The following result is then a corollary of Theorem 2:

The remainder of the section is devoted to the proof of Theorem 2. We deal with the three conditions in the order of \(C\), \(A\), and \(B\) in three subsections.

4.1 Proof for Condition \(C\)↩︎

In this subsection, we show that \[\vec{S}is strongly connected (with at least 2 nodes) \quad \Longrightarrow \quad \vec{S}'is strongly connected.\]

First, note that by 20 , the digraph \(\vec{S}'\) can be obtained from \(\vec{S}\) by first adding a new node \(u_{m+1}\) and the following set of new edges: \[\label{eq:defe0fors39} E_{m+1} := \{u_iu_{m+1} \mid u_iu_m \in E(\vec{S})\} \cup \{u_{m+1}u_j \mid u_mu_j \in E(\vec{S})\},\tag{21}\] and then deleting the self-loop \(u_m u_m\). Precisely, \[\label{eq:vefors39} V(\vec{S}') = V(\vec{S}) \cup \{u_{m+1}\} \quad and \quad E(\vec{S}') = E(\vec{S}) \cup E_{m+1} - \{u_m u_m\}.\tag{22}\]

We now show that for any two distinct nodes \(u_i, u_j\in V(\vec{S}')\), there is a walk from \(u_i\) to \(u_j\). Consider the following three cases:

Case 1: \(u_i\neq u_{m+1}\) and \(u_j\neq u_{m+1}\). Since \(\vec{S}\) is strongly connected, there is a path \(\vec{P}\) from \(u_i\) to \(u_j\) in \(\vec{S}\). By 21 and 22 , \(\vec{P}\) is also a path of \(\vec{S}'\).

Case 2: \(u_i = u_{m+1}\). Let \(u_{i_1}\cdots u_{i_\ell}\), with \(u_{i_1} = u_m\) and \(u_{i_\ell} = u_j\), be a walk of \(\vec{S}\) from \(u_m\) to \(u_j\). In the case \(u_j = u_m\), the walk is closed—such a closed walk exists because \(\vec{S}\) is strongly connected and has \(m \geq 2\) nodes. Since \(u_mu_{i_2}\in E(\vec{S})\), by 21 we have that \(u_{m+1}u_{i_2}\in E(\vec{S}')\) and, hence, \(u_{m+1}u_{i_2}\cdots u_{i_\ell}\) is a walk from \(u_{m+1}\) to \(u_j\).

Case 3: \(u_j = u_{m+1}\). Similarly, if \(u_{j_1}\cdots u_{j_\ell}\) is a walk of \(\vec{S}\), with \(u_{j_1} = u_i\) and \(u_{j_\ell} = u_m\), then \(u_{j_1}\cdots u_{j_{\ell-1}}u_{m+1}\) is a walk of \(\vec{S}'\) from \(u_i\) to \(u_{m+1}\). 0◻

4.2 Proof for Condition \(A\)↩︎

In this subsection, we show that \[\operatorname{co-rank}(Z) = 0 \quad \Longrightarrow \quad \operatorname{co-rank}(Z') = 0.\]

Recall that \(\vec{S}_1,\ldots, \vec{S}_q\) are the SCCs of \(\vec{S}\). Let \(\vec{S}'_p := \vec{S}_p\), for \(p = 1,\ldots, q-1\), and \(\vec{S}'_q\) be obtained from \(\vec{S}_q\) by performing the surgery on the node \(u_m\). Then, it should be clear from 21 and 22 that \(\vec{S}'_1,\ldots, \vec{S}'_q\) are the SCCs of \(\vec{S}'\).

Also, recall that we use the notation \(B_{\vec{S}}\) to denote the bipartite graph associated with \(\vec{S}\). For \(B_{\vec{S}'}\), it follows from 21 and 22 that \[V'(B_{\vec{S}'}) = V'(B_{\vec{S}}) \cup \{u'_{m+1}\}, \quad V''(B_{\vec{S}'}) = V''(B_{\vec{S}}) \cup \{u''_{m+1}\},\] and \[\begin{gather} \label{eq:defebs} E(B_{\vec{S}'}) = E(B_{\vec{S}}) \cup \{(u'_i, u''_{m+1}) \mid (u'_i, u''_m)\in E(B_{\vec{S}}) \} \\ \cup \{(u'_{m+1}, u''_i)\mid (u'_m, u''_i)\in E(B_{\vec{S}}) \} - \{(u'_m,u''_m)\}. \end{gather}\tag{23}\] See Figure 4 for illustration.

Since \(\operatorname{co-rank}(Z) = 0\), it follows from Lemma 1 that every bipartite graph \(B_{\vec{S}_p}\), for \(p = 1,\ldots, q\), is connected. Using the same lemma, we have that \(\operatorname{co-rank}(Z') = 0\) if and only if \(B_{\vec{S}'_p}\) is connected for all \(p = 1,\ldots, q\). Since \(\vec{S}'_p = \vec{S}_p\) for \(p = 1,\ldots, q - 1\), it suffices to show that \(B_{\vec{S}'_q}\) is connected. We establish this fact by proving the following lemma:

4.3 Proof for Condition \(B\)↩︎

In this subsection, we show that \[x^*\in \operatorname{int}\mathsf{X}\quad \Longrightarrow \quad x'^* \in \operatorname{int}\mathsf{X}'.\]

We start by relating the cycles of \(\vec{S}'\) to those of \(\vec{S}\). Label the cycles of \(\vec{S}\) in a way such that the first \(\ell\) cycles \(\vec{C}_1,\ldots, \vec{C}_\ell\), for some \(\ell \leq k\), contain the node \(u_m\) and that \(\vec{C}_1 = u_mu_m\) is the self-loop.

The self-loop \(\vec{C}_1\) induces the \(2\)-cycle \(\vec{C}'_1 := u_m u_{m+1} u_m\) of \(\vec{S}'\). Each cycle \(\vec{C}_p\), for \(2 \leq p \leq \ell\), induces four different cycles of \(\vec{S}'\) as follows: \(\vec{C}_{p, 1} := \vec{C}_p\) and \(\vec{C}_{p, 2}\), \(\vec{C}_{p, 3}\), \(\vec{C}_{p, 4}\) are obtained from \(\vec{C}_p\) by substituting the node \(u_m\) with \(u_{m+1}\), \(u_mu_{m+1}\), \(u_{m+1}u_m\), respectively. Thus, the set of cycles of \(\vec{S}'\) is given by \[\{\vec{C}'_1\} \cup \{\vec{C}_{p, i} \mid 2\leq p\leq \elland1\leq i \leq 4\} \cup \{\vec{C}_q \mid \ell + 1 \leq q \leq k\}.\]

To illustrate, consider the digraph \(\vec{S}\) in Figure [sfig1:ss39] and the corresponding digraph \(\vec{S}'\) in Figure [sfig2:ss39]. The digraph \(\vec{S}\) has \(4\) cycles as exhibited in 1 . The first three cycles contain the node \(u_4\). The self-loop \(\vec{C}_1\) induces the \(2\)-cycle \(\vec{C}'_1 = u_4u_5u_4\) in \(\vec{S}'\). The cycle \(\vec{C}_2\) induces four cycles of \(\vec{S}'\): \[\vec{C}_{2,1} = u_3u_4u_3, \quad \vec{C}_{2,2} = u_3u_5u_3, \quad \vec{C}_{2,3} = u_3u_4u_5u_3, \quad and \quad \vec{C}_{2,4} = u_3u_5u_4u_3.\] Similarly, the four cycles of \(\vec{S}'\) induced by \(\vec{C}_3\) are \[\vec{C}_{3,1} = u_1u_2u_3u_4u_1, \, \vec{C}_{3,2} = u_1u_2u_3u_5u_1, \, \vec{C}_{3,3} = u_1u_2u_3u_4u_5u_1,and\vec{C}_{3,4} = u_1u_2u_3u_5u_4u_1.\] Thus, the digraph \(\vec{S}'\) has ten cycles \(\vec{C}'_1\), \(\vec{C}_{2,1},\ldots, \vec{C}_{2,4}\), \(\vec{C}_{3,1},\ldots, \vec{C}_{3,4}\), and \(\vec{C}_4\).

Let \(z'_1\), \(z'_{p, i}\), and \(z'_q\) be the node-cycle incidence vectors of \(\vec{S}'\) corresponding to \(\vec{C}'_1\), \(\vec{C}_{p, i}\), and \(\vec{C}_q\), respectively. To relate these vectors to the \(z_j\)’s, we first augment each \(z_j\) by adding a zero entry at the end. Precisely, we define \[\hat{z}_j := \begin{bmatrix} z_j \\ 0 \end{bmatrix} \in \mathbb{R}^{m+1}, \quad for allj = 1,\ldots, k.\] Then, we have that \[\label{eq:relatez39toz} \left\{ \begin{align} & z'_1 = e_m + e_{m+1}, & \\ & z'_{p, 1} = \hat{z}_p, \quad z'_{p, 2} = \hat{z}_p - e_m + e_{m+1}, \quad z'_{p, 3} = z'_{p, 4} = \hat{z}_p + e_{m+1}, & for2\leq p\leq \ell, \\ & z'_q = \hat{z}_q, & for\ell + 1 \leq q \leq k. \end{align} \right.\tag{24}\] Note that \[z'_{p, 3} = z'_{p, 4} = \frac{1}{2} (z'_1 + z'_{p, 1} + z'_{p, 2}).\] which implies that \(z'_{p, 3}\) and \(z'_{p'_4}\) are not extremal generators of \(\mathsf{X}'\).

It now suffices to show that \(x'^*\) can be expressed as a positive combination of \(z'_1\), \(z'_{p, 1}\)’s, \(z'_{p, 2}\)’s, and \(z'_q\)’s. First, by 19 , we have that \[x'^* = (x^*_1, \cdots, x^*_{m-1}, x^*_m/2, x^*_m/2).\] Let \(\hat{x}^* := (x^*; 0)\). Then, we can express \(x'^*\) as \[\label{eq:defxprimestar} x'^* = \hat{x}^* + \frac{x^*_m}{2} (e_{m + 1} - e_m).\tag{25}\] Since \(x^*\in \operatorname{int}\mathsf{X}\), there exist positive coefficients \(c_j\)’s such that \(x^* = \sum_{j = 1}^k c_j z_j\). It follows from the definitions of \(\hat{z}_j\) and of \(\hat{x}^*\) that \[\label{eq:xhatzhat} \hat{x}^* = \sum_{j = 1}^k c_j \hat{z}_j.\tag{26}\] Since \(\vec{C}_1,\ldots, \vec{C}_\ell\) are the cycles of \(\vec{S}\) that contain \(u_m\), \[\label{eq:sumforxm} x^*_m = \sum_{j = 1}^\ell c_j.\tag{27}\] We define positive coefficients as follows: \[\label{eq:defc39} \begin{cases} c'_1 := c_1/2, & \\ c'_{p, i} := c_p/2 & \quad for2\leq p \leq \elland1 \leq i \leq 2, \\ c'_q := c_q & \quad for\ell + 1 \leq q \leq k. \end{cases}\tag{28}\] Then, following 25 , we have that \[\begin{align} x'^* & = \hat{x}^* + \frac{x^*_m}{2} (e_{m + 1} - e_m) \\ & = \sum_{j = 1}^k c_j \hat{z}_j + \frac{x^*_m}{2} (e_{m + 1} - e_m) \\ & = \sum_{q = \ell + 1}^k c'_q \hat{z}_q + \sum_{p = 2}^\ell \left [\sum_{i = 1}^2 c'_{p, i} \right ] \hat{z}_p + c_1 e_m + \frac{x^*_m}{2} (e_{m + 1} - e_m) \\ & = \sum_{q = \ell + 1}^k c'_q z'_q + \sum_{p = 2}^\ell \sum_{i = 1}^2 c'_{p, i} z'_{p, i} + c_1 e_m + \frac{1}{2}\left [x^*_m - \sum_{j = 2}^\ell c_j \right ](e_{m+1} - e_m) \\ & = \sum_{q = \ell + 1}^k c'_q z'_q + \sum_{p = 2}^\ell \sum_{i = 1}^2 c'_{p, i} z'_{p, i} + \frac{1}{2} c_1 (e_{m + 1} + e_m) \\ & = \sum_{q = \ell + 1}^k c'_q z'_q + \sum_{p = 2}^\ell \sum_{i = 1}^2 c'_{p, i} z'_{p, i} + c'_1 z'_1, \end{align}\] where the second equality follows from 26 , the third equality follows from 28 , the fourth equality follows from  24 and 28 , the fifth equality follows from 27 , and the last equality follows from 24 and 28 . This completes the proof. 0◻

5 Hamiltonicity of complete \(\vec{S}\)-partite graphs↩︎

Recall that \(\vec{K}_y\) is the complete \(\vec{S}\)-partite graph, with \(y_i = |\pi^{-1}(u_i)|\), for all \(i = 1,\ldots, m\). In this section, we investigate when \(\vec{K}_y\) can have a Hamiltonian decomposition (cycle).

In the sequel, we assume that \(\vec{S}\) does not have a self-loop and that Condition \(B\) (\(x^*\in \operatorname{int}\mathsf{X}\)) is satisfied. Let \(\mathsf{U}\) be an open neighborhood of \(x^*\) in \(\mathsf{X}\). Then, there is a continuous function \(\gamma: \mathsf{U}\to \mathbb{R}_{>0}^k\) such that \[\label{eq:defphi} x = Z \gamma(x) \quad for allx\in \mathsf{U}.\tag{29}\] Let \[\gamma_0:= \frac{1}{2}\min_{j = 1}^k \gamma_j(x^*).\] Shrink \(\mathsf{U}\) if necessary so that \[\label{eq:defepsilon} \gamma_j(y) > \gamma_0, \quad for allj= 1,\ldots, kand for ally \in \mathsf{U}.\tag{30}\] We now introduce the following subset of \(\mathsf{X}\): \[\label{eq:defY0} \mathsf{X}_0 := \{y\in \mathsf{X}\cap \mathbb{N}^m\mid \|y\|_1 \geq 1/\gamma_0 \quad and \quad y/\|y\|_1 \in \mathsf{U}\}.\tag{31}\] In words, \(\mathsf{X}_0\) collects all integer-valued \(y\in \mathsf{X}\) such that \(\|y\|_1\) is sufficiently large and \(y/\|y\|_1\) is sufficiently close to \(x^*\). The main result of this section is as follows:

By Lemma 3, if \(\vec{K}_y\) has a Hamiltonian decomposition, then \(y\in \mathsf{X}\). Combining this fact with item 1 of the above theorem, we have that \(y\in \mathsf{X}\cap \mathbb{N}_0^m\) is both necessary and sufficient for \(\vec{K}_y\) to have a Hamiltonian decomposition.

We establish the two items of Theorem 4 in two subsections.

5.1 Proof of item 1↩︎

We start by decomposing \(y\in \mathsf{X}\) into an integer combination of the node-cycle incidence vectors \(z_j\). This is feasible as we show in the following lemma:

Using the decomposition ?? , we exhibit a desired Hamiltonian decomposition of \(\vec{K}_y\) in the following lemma:

5.2 Proof of item 2↩︎

Under the assumption that \(\vec{S}\) is strongly connected and \(y\in \mathsf{X}_0\), the two lemmas we established in the previous subsection can be strengthened.

We first have the following result, which is a strengthened version of Lemma 6:

We now show that whenever \(\vec{S}\) is strongly connected and \(y\) can be expressed as ?? , with \(c_1,\ldots, c_k\) positive integers, the digraph \(\vec{K}_y\) has a Hamiltonian cycle.

6 On Sufficiency of Conditions of \(A\), \(B\), and \(C\)↩︎

In this section, we show that if a step-graphon \(W\) satisfies Conditions \(A\), \(B\) (and \(C\)), then \(W\) has the (strong) \(H\)-property.

The condition that a graph has a Hamiltonian decomposition (cycle) is monotone with respect to edge addition. Specifically, if \(\vec{G}\) and \(\vec{G}'\) are two graphs on the same node set, with \(E(\vec{G}) \supseteq E(\vec{G}')\), then \[\begin{gather} G'has a Hamiltonian decomposition (cycle) \\ \Longrightarrow \quad G has a Hamiltonian decomposition (cycle). \end{gather}\] This monotonicity is carried over to graphons. Specifically if \(W'\) and \(W\) are two graphons, with \(W' \leq W\), then \[\begin{gather} \mathbf{P}(\vec{G}_n\sim W'has a Hamiltonian decomposition (cycle)) \\ \leq \mathbf{P}(\vec{G}_n\sim Whas a Hamiltonian decomposition (cycle)) \end{gather}\] which implies that \[W'has the (strong)H-property \quad \Longrightarrow \quad Whas the (strong) H-property.\] Thus, by Corollary 3, we can assume that \(W\) is loop free.

By Theorem 4, for any \(y\in \mathsf{X}_0\), \(\vec{K}_y\) has a Hamiltonian decomposition. If, further, \(\vec{S}\) is strongly connected, then \(\vec{K}_y\) has a Hamiltonian cycle. Denote the Hamiltonian decomposition (cycle) by \(\vec{H}_y\). We show below that if \(W\) satisfies Conditions \(A\) and \(B\), then \(\vec{H}_y\) can be embedded into \(\vec{G}_n \sim W\) a.a.s.. We make the statement precise below.

To this end, let \(\psi_y\) be the embedding (i.e., a one-to-one graph homomorphism) of \(\vec{H}_y\) into \(\vec{K}_y\): \[\label{eq:embeddingphi42} \psi_y: \vec{H}_y \to \vec{K}_y.\tag{39}\] Composing \(\psi_y\) with \(\pi\), we obtain the graph homomorphism \(\pi\cdot \psi_y: \vec{H}_y \to \vec{S}\), which assigns to each node of \(\vec{H}_y\) a node of \(\vec{S}\). We introduce the following definition:

We denote by \(\vec{\mathcal{H}}\) the set of all \(\vec{S}\)-partite graphs \(\vec{G}\) such that \(y(\vec{G})\in \mathsf{X}_0\) and that \(\vec{G}\) admits an embedding \(\phi: \vec{H}_{y(\vec{G})} \to \vec{G}\), compatible with \(\psi_{y(\vec{G})}\). We now state the main result of the section:

We take a two-step approach to establish the result: In Subsection 6.1, we associate to \(W\) a symmetric step-graphon \(W^\mathsf{s}\) and use it to sample undirected random graph \(G_n\sim W^\mathsf{s}\). The two random graphs \(G_n\) and \(\vec{G}_n\) relate to each other in the way that the probability of the event that \(\vec{G}_n\in \vec{\mathcal{H}}\) is bounded from below by the probability of the event that \(H_{y(G_n)}\) is embeddable into \(G_n\), where \(H_y\) is the undirected counterpart of \(\vec{H}_y\). This step allows for the use of the Blow-up Lemma, which we do in Subsection 6.2.

6.1 Reduction by symmetrization↩︎

Let \(\sigma = (\sigma_0,\ldots,\sigma_m)\) be a partition for \(W\). Recall that \(p_{ij}\) is the value of \(W\) over \(R_{ij} = [\sigma_{i-1}, \sigma_i)\times [\sigma_{j-1}, \sigma_j)\). We define a symmetric step-graphon \(W^{\mathsf{s}}\) as follows: \[\label{eq:defhatw} W^{\mathsf{s}}(s,t) := \begin{cases} \max\{p_{ij}, p_{ji}\} & ifp_{ij} p_{ji} = 0 \\ p_{ij} p_{ji} & otherwise, \end{cases} \quad for(s, t)\in R_{ij}and for1\leq i, j \leq m.\tag{40}\] We use \(q_{ij}\) to denote the value of \(W^{\mathsf{s}}\) over \(R_{ij}\) (and \(R_{ji}\)). See Figure 7 for illustration.

To the step-graphon \(W^{\mathsf{s}}\) with partition \(\sigma\), there corresponds the undirected graph \(S\) on \(m\) nodes defined as follows: We still use \(u_1,\ldots, u_m\) to denote the nodes of \(S\). A pair \((u_i,u_j)\) is an edge of \(S\) if \(q_{ij} > 0\). It follows from 40 that \((u_i,u_j)\) is an edge of \(S\) if and only if \(\vec{S}\) contains either \(u_iu_j\) or \(u_ju_i\), or both. Since \(\vec{S}\) does not have any self loop (as \(W\) is loop free), neither does \(S\).

We use \(W^{\mathsf{s}}\) to sample an undirected graph \(G_n\) on \(n\) nodes as follows: First, follow step \(S1\) to obtain the coordinates \(t_i\)’s of the \(n\) nodes. Then,

1. For each pair of two distinct nodes \(v_i\) and \(v_j\), place an undirected edge \((v_i,v_j)\) with probability \(W^{\mathsf{s}}(t_i, t_j)\).

We next introduce the set of \(S\)-partite graphs:

Similarly, for a given \(S\)-partite graph \(G\), we let \(y(G) := (y_1(G),\ldots, y_m(G))\), with \(y_i := |\pi^{-1}(u_i)|\) for all \(i = 1,\ldots, m\). Given a vector \(y\in \mathbb{N}^m_0\), we use \(K_y\) to denote the complete \(S\)-partite graph, with \(y(K_y) = y\).

It is clear from the sampling procedure (more specifically, step \(S'2\)) that \(G_n\sim W^{\mathsf{s}}\) is \(S\)-partite, with the graph homomorphism \(\pi\) being the one that sends each node \(v_j\in V(G_n)\) to \(u_i\) if \(t_j\in [\sigma_{i-1}, \sigma_i)\). Given the \(\vec{S}\)-partite graph \(\vec{H}_y\) introduced right above 39 , we let \(H_y\) be the \(S\)-partite graph obtained from \(\vec{H}_y\) by ignoring the orientations of its edges, i.e., \[\begin{align} V(H_y) & = V(\vec{H}_y), \\ E(H_y) & = \{(v_i,v_j) \mid \vec{H}_ycontains at least one of the two edgesv_iv_jandv_jv_i\}. \end{align}\] Note that if \(\vec{H}_y\) is a cycle and if it has more than two nodes, then \(H_y\) is an (undirected) cycle. If \(\vec{H}_y\) is a node-wise disjoint union of cycles, then \(H_y\) is a node-wise disjoint union of cycles and edges, where the edges correspond to the \(2\)-cycles in \(\vec{H}_y\).

For any \(y\in \mathsf{X}_0\), the embedding \(\psi_y\) given in 39 induces the embedding of \(H_y\) into \(K_y\), which sends the edges \((v_i, v_j)\) of \(H_y\) to \((\psi_y(v_i), \psi_y(v_j))\). With slight abuse of notation, we still use \(\psi_y: H_y \to K_y\) to denote the induced embedding.

Let \(\mathcal{H}\) be the set of all \(S\)-partite graphs \(G\) such that \(y(G) \in \mathsf{X}_0\) and that there exists an embedding \(\phi: H_{y(G)}\to G\) which is compatible with \(\psi_{y(G)}\), i.e., \(\pi \cdot \phi = \pi\cdot \psi_{y(G)}\).

The main result of the subsection is the following:

We establish below Proposition 6. Given an \(S\)-partite graph \(G\), we perform the following operation on its edge set to obtain an \(\vec{S}\)-partite digraph:

1. For each edge \((v_i,v_j)\) of \(G\), we consider the following three cases:

   Case 1: If \(u_iu_j\in \vec{S}\) and \(u_ju_i\notin \vec{S}\), then replace \((v_i,v_j)\) with \(v_iv_j\);

   Case 2: If \(u_ju_i\in \vec{S}\) and \(u_iu_j\notin \vec{S}\), then replace \((v_i,v_j)\) with \(v_jv_i\);

   Case 3: If \(u_iu_j, u_ju_i\in \vec{S}\), then replace \((v_i,v_j)\) with two edges \(v_iv_j\) and \(v_jv_i\).

We denote by \(\vec{G}^{\mathsf{s}}\) the resulting digraph.

Note that an embedding \(\phi: H_y \to G\), with \(y(G) = y\), does not necessarily induce an embedding \(\phi: \vec{H}_y \to \vec{G}^{\mathsf{s}}\); indeed, there may exist an edge \(v_iv_j\) of \(\vec{H}_y\) such that \(\phi(v_i)\phi(v_j)\) is not an edge of \(\vec{G}^\mathsf{s}\) (even though \((\phi(v_i), \phi(v_j))\) is an edge of \(G\)). See Figure 8 for illustration.

The following lemma shows that the induced embedding always exists if \(\phi\) is compatible with \(\psi_y\):

With slight abuse of notation, we denote by \(\vec{G}^{\mathsf{s}}_n\sim W^{\mathsf{s}}\) the random digraph on \(n\) nodes obtained by following the steps \(S1\), \(S'2\), and \(S'3\). An immediate consequence of Lemma 10 is then the following:

The following lemma relates the event \(\vec{G}^\mathsf{s}_n \sim W^\mathsf{s}\in \mathcal{H}\) to the event \(\vec{G}_n\sim W\in \mathcal{H}\), and completes the proof of Proposition 6.

6.2 On the use of the Blow-up Lemma↩︎

Let \(\mathsf{U}\) be the open neighborhood of \(x^*\) in \(\mathsf{X}\), which is introduced at the beginning of Section 5. Since \(x^*\in \operatorname{int}\mathsf{X}\) and since \(x(G_n)\) converges to \(x^*\) a.a.s., it holds that \(y(G_n) \in \mathsf{X}_0\) a.a.s.. We show below that \[\label{eq:alsmotsureembddingH} \lim_{n\to\infty} \mathbf{P}(G_n \sim W^{\mathsf{s}} \in \mathcal{H}\mid y(G_n) \in \mathsf{X}_0) = 1.\tag{43}\] In words, we show that if \(y(G_n)\in \mathsf{X}_0\), then a.a.s. there exists an embedding \(\phi: H_{y(G_n)} \to G_n\), compatible with \(\psi_{y(G_n)}: H_{y(G_n)}\to K_{y(G_n)}\). Note that if 43 holds, then by Proposition 6, we have that \[\lim_{n\to\infty}\mathbf{P}(\vec{G}_n \sim W \in\vec{H}) = 1,\] i.e., Theorem 5 holds, which will then complete the proof of ?? and ?? .

The proof of 43 relies on the use of the Blow-up lemma, which we recall below. Let \(G\) be an arbitrary undirected graph. For two disjoint subsets \(X\) and \(Y\) of \(V(G)\), we let \(e(X,Y)\) be the number of edges between \(X\) and \(Y\). We need the following definition:

We extend the above definition to the \(S\)-partite graphs:

For an arbitrary graph \(H\), we let \(\Delta(H)\) be the degree of \(H\) (i.e., the maximum of the degrees of its nodes). We reproduce below the Blow-up lemma [9]:

We now return to the proof of 43 . For any \(y\in \mathsf{X}_0\), we let \(H_y\) be given as in the previous subsection. As argued earlier, \(H_y\) is either a cycle or a node-wise disjoint union of cycles and possibly edges. Thus, \[\Delta(H_y) \leq 2, \quad for ally\in \mathsf{X}_0.\] Also, it has been shown (as a consequence of Theorem 4) that there is an embedding \(\psi_y: H_y\to K_{y}\) for all \(y\in \mathsf{X}_0\). Let \[\label{eq:defdelta} \delta := \frac{1}{2} \min \{q_{ij} \mid (u_i,u_j) \in E(S)\}.\tag{44}\] and \(\epsilon := \epsilon(\delta, 2, m) > 0\) be given as in the statement of Lemma 13. It remains to show that a.a.s. \(G_n\sim W^\mathsf{s}\) is \((\epsilon,\delta)\)-super-regular.

The proof of the proposition uses standard arguments in random graph theory. For completeness of presentation, we include it in Appendix 9. 0◻

7 Proof of Proposition 1↩︎

We say that \(\sigma'\) is a refinement of \(\sigma\) if \(\sigma'\) contains \(\sigma\) as a subsequence. Furthermore, \(\sigma'\) is a one-step refinement of \(\sigma\) if \(\sigma'\) contains one more element than \(\sigma\) does. It is clear that any refinement can be obtained by iterating one-step refinements. Note that for any two arbitrary partitions \(\sigma\) and \(\sigma'\), there exists a partition \(\sigma''\) as a refinement of both \(\sigma\) and \(\sigma'\). The arguments above then imply that to establish Proposition 1, it suffices to prove for the case where \(\sigma'\) is a one-step refinement of \(\sigma\).

Let \(\sigma = (\sigma_0,\ldots, \sigma_{m-1}, \sigma_*)\), with \(\sigma_0 = 0\) and \(\sigma_* = 1\). We assume, without loss of generality, that \(\sigma'\) is obtained from \(\sigma\) by inserting an element \(\sigma_m\) between \(\sigma_{m-1}\) and \(\sigma_*\): \[\sigma' = (\sigma_0,\ldots, \sigma_{m-1},\sigma_m, \sigma_*).\] Then, the following hold for \(x'^*\), \(\vec{S}'\), and \(B_{\vec{S}'}\):

1. Let \(\hat{x}^* := (x^*; 0) \in \mathbb{R}^{m+1}\). Then, \[\label{eq:defbeta} x'^* = \hat{x}^* + (1 - \sigma_m) (e_{m + 1} - e_m).\tag{45}\]

2. The skeleton graph \(\vec{S}'\) can be obtained from \(\vec{S}\) by adding the new node \(u_{m+1}\), as a “copy” of \(u_m\), and new edges incident to \(u_{m+1}\), i.e., \[V(\vec{S}') = V(\vec{S}) \cup \{u_{m+1}\},\] and \[\begin{gather} \label{eq:edgesetfors39refine} E(\vec{S}') = E(\vec{S}) \cup \{u_i u_{m+1} \mid u_iu_m\in E(\vec{S})\} \cup \{u_{m+1} u_j \mid u_mu_j \in E(\vec{S})\} \\ \cup \{u_{m+1}u_{m+1}ifu_mu_m\in E(\vec{S}) \}. \end{gather}\tag{46}\] With slight abuse of terminology, we call any such digraph \(\vec{S}'\), obtained from \(\vec{S}\) via the above operation, a one-step refinement on node \(u_m\).

3. Correspondingly, the bipartite graph \(B_{\vec{S}'}\) is given by \[V'(B_{\vec{S}'}) = V'(B_{\vec{S}}) \cup \{u'_{m+1}\}, \quad V''(B_{\vec{S}'}) = V''(B_{\vec{S}}) \cup \{u''_{m+1}\}\] and \[\begin{gather} \label{eq:edgesetforbs39refine} E(B_{\vec{S}'}) = E(B_{\vec{S}}) \cup \{(u'_i, u''_{m+1}) \mid (u'_i,u''_m)\in E(B_{\vec{S}})\} \\ \cup \{(u'_{m+1}, u''_j) \mid (u'_m, u''_j) \in E(B_{\vec{S}})\} \\ \cup \{(u'_{m+1}, u''_{m+1})if(u'_m, u''_m) \in E(B_{\vec{S}}) \}. \end{gather}\tag{47}\]

We now establish the three items of the proposition:

7.1 Proof of item 1↩︎

Consider the graph homomorphism \(\theta: \vec{S}' \to \vec{S}\) defined by \[\theta(u_i):= \begin{cases} u_i & if1\leq i \leq m \\ u_{m} & ifi = m + 1 \end{cases}\] In words, \(\theta\) identifies the node \(u_{m+1}\) with \(u_m\). It follows directly from 46 that \[u_i u_j \in E(\vec{S}') \quad \Longleftrightarrow \quad \theta(u_i)\theta(u_j) \in E(\vec{S}).\] Thus, \[\label{eq:walksofss39} \vec{P}'=u_{i_1}\cdots u_{i_\ell}is a walk of\vec{S}' \quad \Longleftrightarrow \quad \theta(\vec{P}'):=\theta(u_{i_1})\cdots \theta(u_{i_\ell})is a walk of\vec{S}.\tag{48}\]

Let \(u_i\) and \(u_j\) be two distinct nodes of \(\vec{S}\). We pick nodes \(u_{i'}\in \theta^{-1}(u_i)\) and \(u_{j'}\in \theta^{-1}(u_j)\). Since \(\vec{S}'\) is strongly connected, there is a path \(\vec{P}'\) of \(\vec{S}'\) from \(u_{i'}\) to \(u_{j'}\). By 48 , we have that \(\theta(\vec{P}')\) is a walk of \(\vec{S}\) from \(u_i\) to \(u_j\).

Let \(u_{i'}\) and \(u_{j'}\) be two distinct nodes of \(\vec{S}'\). We first consider the case where \(u_i := \theta(u_{i'})\) and \(u_j := \theta(u_{j'})\) are two distinct nodes. In this case, there is a path \(\vec{P} = u_{i_1}\cdots u_{i_\ell}\), with \(u_{i_1} = u_i\) and \(u_{i_\ell} = u_j\), of \(\vec{S}\) from \(u_i\) to \(u_j\). We pick nodes \(u_{i'_j}\in \theta^{-1}(u_{i_j})\), for \(j = 2,\ldots, \ell-1\). Then, by 48 , \(u_{i'} u_{i'_2} \cdots u_{i'_{\ell - 1}}u_{j'}\) is a path of \(\vec{S}'\) from \(u_{i'}\) to \(u_{j'}\). We now assume that \(u_i = u_j\). Since \(\vec{S}\) has at least \(2\) nodes (\(m \geq 2\)), there exists a node \(u_k\) of \(\vec{S}\) such that \(u_k \neq u_i\). Let \(\vec{P}_{1} = u_{i_1} \cdots u_{i_{\ell_1}}\) (resp., \(\vec{P}_{2} = u_{i_{\ell_1}} u_{i_{\ell_1 + 1}}\cdots u_{i_{\ell}}\)) be a path of \(\vec{S}\) from \(u_i\) to \(u_k\) (resp., from \(u_k\) to \(u_i\)), where \(u_{i_1} = u_{i_\ell} = u_i\) and \(u_{i_{\ell_1}} = u_k\). Concatenating \(\vec{P}_1\) and \(\vec{P}_2\), we obtain a closed walk. Pick nodes \(u_{i'_j}\in \theta^{-1}(u_{i_j})\), for \(j = 2,\ldots, \ell-1\). Using again 48 , we conclude that \(u_{i'}u_{i'_2} \cdots u_{i'_{\ell - 1}} u_{j'}\) is a walk of \(\vec{S}'\) from \(u_{i'}\) to \(u_{j'}\). 0◻

7.2 Proof of item 2↩︎

Let \(\vec{S}_1,\ldots, \vec{S}_q\) be the SCCs of \(\vec{S}\), and \(\vec{S}'_1,\ldots, \vec{S}'_{q'}\) be the SCCs of \(\vec{S}'\). Without loss of generality, we assume that \(u_m\in V(\vec{S}_q)\). By Lemma 1, it suffices to show that \[\label{eq:reducetoconnectBitem2} B_{\vec{S}_1},\ldots, B_{\vec{S}_q}are connected \quad \Longleftrightarrow \quad B_{\vec{S}'_1},\ldots, B_{\vec{S}'_{q'}}are connected.\tag{49}\]

If \(\vec{S}_q\) comprises the single node \(u_m\) without self-loop, then \(\vec{S}'\) has \((q + 1)\) SCCs \(\vec{S}'_1,\ldots, \vec{S}'_{q+1}\), where \(\vec{S}'_p := \vec{S}_p\), for \(p = 1,\ldots, q\), and \(\vec{S}'_{q+1}\) comprises the single node \(u_{m+1}\) without self-loop. It follows that the bipartite graph \(B_{\vec{S}_q}\) has two nodes \(u'_m\) and \(u''_m\), without the edge \((u'_m,u''_m)\), so \(B_{\vec{S}_q}\) is disconnected. The same applies to \(B_{\vec{S}'_{q+1}}\). Then, by Lemma 1, \(\operatorname{co-rank}(Z)\geq 1\) and \(\operatorname{co-rank}(Z')\geq 2\).

To prove item 2, we must assume either \(\operatorname{co-rank}(Z) = 0\) or \(\operatorname{co-rank}(Z') = 0\) and establish the other. By the above arguments, either \(\vec{S}_q\) has at least two nodes, or, \(\vec{S}_q\) comprises the single node \(u_m\) with self-loop. It follows that \(\vec{S}'\) has \(q\) SCCs \(\vec{S}'_1,\ldots, \vec{S}'_q\), where \(\vec{S}'_p := \vec{S}_p\) for all \(p = 1,\ldots, q-1\), and \(\vec{S}'_q\) is a one-step refinement of \(\vec{S}_q\) on \(u_m\). Thus, to prove 49 , it now suffices to establish the following result:

7.3 Proof of item 3↩︎

We consider two cases: (1) \(u_m\) does not have a self-loop and (2) \(u_m\) has a self-loop.

7.3.1 Case 1: \(u_m\) does not have a self-loop↩︎

Let \(\vec{C}_1, \ldots, \vec{C}_\ell\), for \(\ell \leq k\), be the cycles of \(\vec{S}\) that contain \(u_m\). Every such cycle \(\vec{C}_p\), for \(1 \leq p \leq \ell\), induces two different cycles in \(\vec{S}'\): one is \(\vec{C}_{p, 1}:= \vec{C}_{p}\) and the other is obtained by replacing the node \(u_m\) in \(\vec{C}_p\) with \(u_{m+1}\). We denote it by \(C_{p, 2}\). The set of cycles of \(\vec{S}'\) is thus given by \[\{\vec{C}_{p, i} \mid 1 \leq p \leq \elland1\leq i \leq 2\} \cup \{\vec{C}_q \mid \ell + 1 \leq q\leq k\}.\] Let \(z'_{p, i}\) and \(z'_q\) be the node-cycle incidence vectors of \(\vec{S}'\) corresponding to \(\vec{C}_{p, i}\) and \(\vec{C}_q\). Then, \[\label{eq:defz39forcase1} z'_{p, 1} = \hat{z}_p, \quad z'_{p, 2} = \hat{z}_p - e_m + e_{m+1}, \quad andz'_q = \hat{z}_q,\tag{51}\] where we recall that \(\hat{z}_j= (z_j; 0)\).

We write \(x^* = \sum_{j= 1}^k c_j z_j\) with \(c_j \geq 0\). Since \(\vec{C}_1,\ldots, \vec{C}_\ell\) are the cycles that contain \(u_m\), we have that \[\label{eq:sumcp} \sum_{p = 1}^\ell c_p = x^*_{m} = (1 - \sigma_{m-1}).\tag{52}\] Now, let \[\label{eq:defc39forcase1} c'_{p, 1} := \frac{\sigma_m - \sigma_{m-1}}{1 - \sigma_{m-1}} c_p, \quad c'_{p, 2} := \frac{1 - \sigma_m}{1 - \sigma_{m-1}} c_p, \quad andc'_q := c_q.\tag{53}\] Note that \(c'_{p, 1} + c'_{p, 2} = c_p\) for all \(1 \leq p \leq \ell\). Then, \[\begin{align} x'^* & = \hat{x}^* + (1 - \sigma_m) (e_{m + 1} - e_m) \notag\\ & = \sum_{j = 1}^k c_j \hat{z}_j + (1 - \sigma_m) (e_{m + 1} - e_m) \notag\\ & = \sum_{p = 1}^\ell \left [ \sum_{i = 1}^2 c'_{p, i} \right ]\hat{z}_{p} + \sum_{q = \ell + 1}^k c'_q \hat{z}_q + (1 - \sigma_m)(e_{m + 1} - e_m) \notag \\ & = \sum_{p = 1}^\ell \sum_{i = 1}^2 c'_{p, i} z'_{p, i} + \sum_{q = \ell + 1}^k c'_q z'_q + \left [ (1 - \sigma_{m}) - \sum_{p = 1}^\ell c'_{p, 2} \right ] (e_{m + 1} - e_m) \notag \\ & = \sum_{p = 1}^\ell \sum_{i = 1}^2 c'_{p, i} z'_{p, i} + \sum_{q = \ell + 1}^k c'_q z'_q + (1 - \sigma_{m}) \left [ 1 - \frac{1}{ 1- \sigma_{m-1}} \sum_{p = 1}^\ell c_p \right ] (e_{m + 1} - e_m) \notag \\ & = \sum_{p = 1}^\ell \sum_{i = 1}^2 c'_{p, i} z'_{p, i} + \sum_{q = \ell + 1}^k c'_q z'_q, \label{eq:positivecombforx39case1} \end{align}\tag{54}\] where the first equality follows from 45 , the fourth equality follows from 51 , the fifth equality follows from 53 , and the last equality follows from 52 . By 54 , \(x'^*\in \mathsf{X}'\). If, further, the coefficients \(c_j\)’s are positive (which holds if \(x^*\in \operatorname{int}\mathsf{X}\)), then by 53 the \(c'_{p, i}\)’s and the \(c'_q\)’s are positive as well and hence, \(x'^*\in \operatorname{int}\mathsf{X}'\).

We write \[x'^* = \sum_{p = 1}^\ell \sum_{i = 1}^2 c'_{p, i} z'_{p, i} + \sum_{q = \ell + 1}^k c'_q z'_q,\] where the \(c'_{p, i}\)’s and the \(c_q\)’s are nonnegative. For \(p = 1,\ldots, \ell\) and for \(q = \ell + 1, \ldots, k\), we define \[\label{eq:defcjforcase1} c_p:= c'_{p, 1} + c'_{p, 2} \quad and \quad c_q:= c'_q.\tag{55}\] Let \(J\in \mathbb{R}^{m\times (m + 1)}\) be defined as follows: \[J := \begin{bmatrix} 1 & & & \\ & \ddots & & \\ & & 1 & 1 \end{bmatrix}.\] It follows from 51 and 45 that \[z_p = J z'_{p, i}, \quad z_q = J z'_q, \quad andx^* = J x'^*.\] Thus, \[\begin{align} x^* & = J x'^* \notag \\ & = \sum_{p = 1}^\ell \sum_{i = 1}^2 c'_{p, i} J z'_{p, i} + \sum_{q = \ell + 1}^k c'_q J z'_q \notag \\ & = \sum_{p = 1}^\ell \left [ \sum_{i = 1}^2 c'_{p, i} \right ] z_{p} + \sum_{q = \ell + 1}^k c'_q z_q \notag \\ & = \sum_{j = 1}^k c_j z_j, \notag \end{align}\] which shows that \(x^*\in \mathsf{X}\). By 55 , if the \(c'_{p, i}\)’s and the \(c'_q\)’s are positive, then so are the \(c_j\)’s, which implies that if \(x'^*\in \operatorname{int}\mathsf{X}'\), then \(x^*\in \operatorname{int}\mathsf{X}\). 0◻

7.3.2 Case 2: \(u_m\) has a self-loop↩︎

We again let \(\vec{C}_1, \ldots, \vec{C}_\ell\), for \(\ell \leq k\), be the cycles of \(\vec{S}\) that contain \(u_m\), with \(\vec{C}_1 = u_m u_m\) the self-loop. The self-loop \(\vec{C}_1\) induces three cycles in \(\vec{S}'\): \[\vec{C}_{1, 1} = u_mu_m, \quad \vec{C}_{1, 2} = u_{m + 1} u_{m + 1}, \quad and \quad \vec{C}_{1, 3} = u_m u_{m + 1} u_m.\] As argued at the beginning of Subsection 4.3, each cycle \(\vec{C}_p\), for \(2\leq p \leq \ell\), induces four different cycles: \(\vec{C}_{p, 1} := \vec{C}_p\) and \(\vec{C}_{p, 2}\), \(\vec{C}_{p, 3}\), \(\vec{C}_{p, 4}\) are obtained by replacing \(u_m \in \vec{C}_p\) with \(u_{m+1}\), \(u_mu_{m+1}\), \(u_{m+1}u_m\), respectively.

Let \(z'_{1,i}\), for \(i = 1,\ldots, 3\), be the node-cycle incidence vectors corresponding to \(\vec{C}_{1,i}\), which are given by \[z'_{1,1} = e_m, \quad z'_{1,2} = e_{m+1}, \quad and \quad z'_{1,3} = e_m + e_{m + 1}.\] Let \(z'_{p,i}\), for \(2\leq p \leq \ell\) and \(1\leq i \leq 4\), be the node-cycle incidence vectors corresponding to \(\vec{C}_{p,i}\), as given in 24 . Note, in particular, that \[\begin{align} z'_{1,3} & = z'_{1,1} + z'_{1,2}, \\ z'_{p,3} & = z'_{p,4} = z'_{p,1} + z'_{1,2} = z'_{p,2} + z'_{1,1}, \quad forp = 2,\ldots, \ell,\\ \end{align}\] which implies that none of the vectors \(z'_{1,3}\), \(z'_{p,3}\), and \(z'_{p,4}\) is an extremal generator of \(\mathsf{X}'\), and can thus be suppressed in the nonnegative (positive) combination of \(x'^*\). The same arguments used in the above case can be used to establish the current case. 0◻

8 On graphons with symmetric support↩︎

Let \(W\) be a step-graphon with symmetric support, i.e., \(W(s, t)\neq 0\) if and only if \(W(t,s) \neq 0\). Let \(\sigma\) be a partition for \(W\) and \(\vec{S}\) be the associated skeleton graph. Note that \(\vec{S}\) is symmetric. Let \(S\) be the undirected graph obtained from \(\vec{S}\) by ignoring the orientations of the self-loops and by replacing every pair of oppositely oriented edges \(\{u_iu_j, u_ju_i\}\), for \(u_i\neq u_j\), with the corresponding undirected edge \((u_i, u_j)\).

We further let \(\mathsf{X}'\) be the convex cone spanned by \(z'_1,\ldots, z'_\ell\). We establish the following result:

An immediate consequence of Lemma 15 is that \(\operatorname{co-rank}(Z) = \operatorname{co-rank}(Z')\). Also note that a symmetric digraph \(\vec{S}\) is strongly connected if and only if \(S\) is connected. The following result is thus a corollary of the Main Theorem specializing to the class of graphons with symmetric support (which include the class of symmetric graphons).

At the end of the section, we relate the above corollary to our earlier work [3], [4], which deal with the \(H\)-property for symmetric graphons. As mentioned in Section 1, the sampling procedure considered in [3], [4] is slightly different from the one considered in this paper. Specifically, in [3], [4], we first sample an undirected graph \(G_n\sim W\), with \(W\) a symmetric graphon, and then obtain the symmetric digraph \(\vec{G}_n^\mathsf{s}\) from \(G_n\) by replacing each undirected edge with a pair of oppositely oriented edges, i.e., we follow steps \(S1\), \(S'2\), and \(S'3\) (see Subsection 6.1), where \(W^\mathsf{s}\) in step \(S'2\) is replaced with \(W\). We denote by \(\vec{G}_n^\mathsf{s}\sim W\) the symmetric digraph obtained in this way. For ease of presentation and to avoid any confusion, we say that the symmetric step-graphon \(W\) has the (strong) \(H^\mathsf{s}\)-property if \(\vec{G}_n^\mathsf{s}\sim W\) has a Hamiltonian decomposition (cycle) a.a.s.. We establish the following result:

9 Proof of Proposition 7↩︎

The proof relies on the use of the Chernoff bound for Binomial random variable, which we recall below:

Now, let \(G_n\sim W^{\mathsf{s}}\). Recall that \(x(G_n) = y(G_n)/n\) is the empirical concentration vector, which converges to \(x^*\) a.a.s.. It follows that a.a.s. \[\label{eq:regular1} x_i(G_n)> \frac{1}{2}\min \{x_i^* \mid i = 1,\ldots, m\} = : \alpha, \quad for alli = 1,\ldots, m.\tag{56}\] For the remainder of the section, we assume that 56 holds. Let \(\mathcal{E}_{n}(u_i, u_j)\) be the event that the pair \((\pi^{-1}(u_i), \pi^{-1}(u_j))\) is \((\epsilon,\delta)\)-super-regular. We have the following result:

Proposition 7 is then an immediate consequence of Lemma 18; indeed, \[\mathbf{P}(G_n \sim W^\mathsf{s} is\epsilon-\delta-super-regular) \geq 1 - \sum_{(u_i,u_j)\in E(S)} \mathbf{P}(\neg\mathcal{E}_n(u_i,u_j)) \xrightarrow{n\to\infty} 1.\] This completes the proof. 0◻

References↩︎