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

GraphonsWcan be used as stochastic models to sample graphsGₙonnnodes fornarbitrarily large. A graphonWis said to have theH-property ifGₙadmits a decomposition into disjoint cycles with probability one asngoes to infinity. Such a decomposition is known as a Hamiltonian decomposition. In this letter, we provide necessary conditions for theH-property to hold. The proof builds upon a hereby established connection between the so-called edge polytope of a finite undirected graph associated withWand theH-property. Building on its properties, we provide a purely geometric solution to a random graph problem. More precisely, we assign two natural objects toW, which we term concentration vector and skeleton graph, denoted byx*andS, respectively. We then establish two necessary conditions for theH-property to hold: (1) the edge-polytope ofS, denoted byX(S), is of maximal rank, and (2)x*belongs toX(S).