TY - JOUR

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

AU - Belabbas, Mohamed Ali

AU - Chen, Xudong

AU - Basar, Tamer

N1 - Publisher Copyright:
© 2017 IEEE.

PY - 2022

Y1 - 2022

N2 - 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).

AB - 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).

KW - Graphon

KW - network analysis and control

UR - http://www.scopus.com/inward/record.url?scp=85121360213&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85121360213&partnerID=8YFLogxK

U2 - 10.1109/LCSYS.2021.3133412

DO - 10.1109/LCSYS.2021.3133412

M3 - Article

AN - SCOPUS:85121360213

SN - 2475-1456

VL - 6

SP - 1766

EP - 1771

JO - IEEE Control Systems Letters

JF - IEEE Control Systems Letters

ER -