The H-property of Graphon

Graphon has recently been introduced by Lovasz, Sos, etc. to study very large graphs. A graphon can be understood as either the limit object of a convergent sequence of graphs, or, a statistical model from which to sample large random graphs. We take here the latter point of view and address the following problem: What is the probability that a random graph sampled from a graphon has a Hamiltonian decomposition? We have recently observed the following phenomenon: In the asymptotic regime where the size of the random graph goes to infinity, the probability tends to be either 0 or 1, depending on the underlying graphon. In this talk, we establish this “zero-one” property for the class of step-graphons and provide a geometric characterization.