  Consider the twin problems of estimating the connection probability matrix of
an inhomogeneous random graph and the graphon of a W-random graph. We establish
the minimax estimation rates with respect to the cut metric for classes of
block constant matrices and step function graphons. Surprisingly, our results
imply that, from the minimax point of view, the raw data, that is, the
adjacency matrix of the observed graph, is already optimal and more involved
procedures cannot improve the convergence rates for this metric. This
phenomenon contrasts with optimal rates of convergence with respect to other
classical distances for graphons such as the l 1 or l 2 metrics.
