On the H-property for step-graphons and edge polytopes

Mohamed-Ali Belabbas, Xudong Chen, Tamer Başar

Abstract: Graphons $W$ can be used as stochastic models to sample graphs $G_n$ on $n$ nodes for $n$ arbitrarily large. A graphon $W$ is said to have the $H$-property if $G_n$ admits a decomposition into disjoint cycles with probability one as $n$ goes to infinity. Such a decomposition is known as a Hamiltonian decomposition. In this paper, we provide necessary conditions for the $H$-property to hold. The proof builds upon a hereby established connection between the so-called edge polytope of a finite undirected graph associated with $W$ and the $H$-property. Building on its properties, we provide a purely geometric solution to a random graph problem. More precisely, we assign two natural objects to $W$, which we term concentration vector and skeleton graph, denoted by $x^*$ and $S$ respectively. We then establish two necessary conditions for the $H$-property to hold: (1) the edge-polytope of $S$, denoted by $\mathcal{X}(S)$, is of full rank, and (2) $x^* \in \mathcal{X}(S)$.

Introduction

The study of massive networks often relies on graphons—symmetric measurable functions that serve as limits for sequences of growing graphs. A graphon $W$ can be viewed as a statistical blueprint for sampling a random graph $G_n$ on $n$ nodes. A central question in this field is the H-property: whether a sampled graph $G_n$ admits a Hamiltonian decomposition (a partition into disjoint cycles) with probability one as $n \to \infty$. This property is critical for the structural stability and controllability of large-scale systems like power grids.

This paper bridges random graph theory and discrete geometry by establishing necessary conditions for a "step-graphon" to possess the H-property. The authors demonstrate that the existence of such a decomposition is fundamentally tied to the geometry of a high-dimensional convex shape known as an edge polytope.

Geometric Framework for Step-Graphons

The authors focus on step-graphons, which are piecewise constant functions resembling a grayscale checkerboard. To analyze these structures, the paper introduces three primary geometric objects:

  1. Concentration Vector ($x^*$): A vector representing the relative probability weight or "size" of each step in the graphon.
  2. Skeleton Graph ($S$): A finite graph that captures the non-zero edge probabilities between cells in the graphon.
  3. Edge Polytope ($\mathcal{X}(S)$): A convex polytope constructed from the incidence matrix of the skeleton graph.
Figure 6: (a) A step-graphon $W$ represented as a piecewise constant function. (b) The corresponding skeleton graph $S$ capturing the non-zero interactions.

By mapping the probabilistic problem onto these geometric constructs, the authors transform the search for Hamiltonian decompositions into a geometric membership problem. Specifically, they prove that for the H-property to hold, the concentration vector $x^*$ must reside within the edge polytope of the skeleton graph.

Key Insights: The Role of Odd Cycles

A significant finding of the research is the necessity of odd cycles within the skeleton graph. If the skeleton graph $S$ lacks an odd cycle (i.e., it is bipartite), the edge polytope $\mathcal{X}(S)$ loses a dimension and is no longer "full rank."

Figure 3: (a) An undirected skeleton graph $S$ containing an odd cycle. (b) The directed representation of the same structure.

In the limit of infinite nodes, the probability of the random graph's empirical statistics landing exactly on a lower-dimensional "flat" shape is zero. Thus, the presence of an odd cycle is a topological requirement for the H-property to manifest in the sampled graphs. This leads to a Zero-One Law: for almost all graphons, the probability of a Hamiltonian decomposition converges to either 1 (certainty) or 0 (impossibility).

Results and Necessary Conditions

The paper establishes two formal necessary conditions for a step-graphon to have the H-property:

  1. Full Rank: The edge polytope $\mathcal{X}(S)$ must be of full rank, which requires the skeleton graph $S$ to contain at least one odd cycle.
  2. Membership: The concentration vector $x^*$ must belong to the edge polytope $\mathcal{X}(S)$.

Numerical simulations on synthetic step-graphons validate these conditions. When $x^*$ lies in the interior of a full-rank polytope, the probability of decomposition converges to 1 as $n$ increases. Conversely, if the polytope is not full rank or $x^*$ lies outside it, the probability drops to 0.

Limitations and Future Outlook

While these conditions are necessary, the authors suggest that $x^*$ being in the interior of the polytope may also be sufficient for the H-property. However, the formal proof for sufficiency is more complex and is left for future work. Additionally, while any graphon can be approximated by step-graphons, extending this geometric framework to general continuous graphons remains an open challenge. Boundary cases, where $x^*$ lies exactly on the edge of the polytope, also require further investigation to understand their non-generic behavior.

Summary updated

Abstract

Graphons $W$ can be used as stochastic models to sample graphs $G_n$ on $n$ nodes for $n$ arbitrarily large. A graphon $W$ is said to have the $H$-property if $G_n$ admits a decomposition into disjoint cycles with probability one as $n$ goes to infinity. Such a decomposition is known as a Hamiltonian decomposition. In this paper, we provide necessary conditions for the $H$-property to hold. The proof builds upon a hereby established connection between the so-called edge polytope of a finite undirected graph associated with $W$ and the $H$-property. Building on its properties, we provide a purely geometric solution to a random graph problem. More precisely, we assign two natural objects to $W$, which we term concentration vector and skeleton graph, denoted by $x^*$ and $S$ respectively. We then establish two necessary conditions for the $H$-property to hold: (1) the edge-polytope of $S$, denoted by $\mathcal{X}(S)$, is of full rank, and (2) $x^* \in \mathcal{X}(S)$.
BibTeX
@article{belabbas2022h,
  author = {Mohamed-Ali Belabbas and Xudong Chen and Tamer Başar},
  title = {{On the H-property for step-graphons and edge polytopes}},
  journal = {IEEE Control. Syst. Lett.},
  year = {2022},
  doi = {10.1109/lcsys.2021.3133412},
}
Figure