On the H-Property for Step-Graphons and Edge Polytopes

Research output: Contribution to journalArticlepeer-review


Graphons W can be used as stochastic models to sample graphs Gn on n nodes for n arbitrarily large. A graphon W is said to have the H-property if Gn 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 letter, 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 X (S), is of maximal rank, and (2) x∗ belongs to X(S).

Original languageEnglish (US)
Pages (from-to)1766-1771
Number of pages6
JournalIEEE Control Systems Letters
StatePublished - 2022


  • Graphon
  • network analysis and control

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Control and Optimization


Dive into the research topics of 'On the H-Property for Step-Graphons and Edge Polytopes'. Together they form a unique fingerprint.

Cite this