Graphs are the subject of many questions in combinatorics. For example, the following question by Erdös was settled only recently: How many 5-cycles can there be in a graph without 3-cycles? This paper addresses a similar problem: How dense are the k-cycles in a graph with n vertices? More precisely: What is the ratio d_k of the number of k-cycles to the number of vertices of a graph? The answer is explicitly described in the first two cases of triangles (k=3) and squares (k=4) for r-regular finite graphs.

This forms part of an attack on the problem of which random graphs are limits of finite graphs. A random graph is a probability measure on the set of connected graphs G with a root whose vertices have a bounded number of neighbors. Incidentally, the main question is equivalent to computing the moments of the probability distribution of eigenvalues of the transition matrix of a simple walk on a random graph. Any finite unrooted graph gives rise to a random graph by choosing a root randomly. Thus we can get random graphs as limits of finite graphs. The open question is: Which random graphs arise this way? The only known necessary condition is that it be unimodular. If a random graph G is the limit of finite graphs G_n, then d_k(G_n) must tend to d_k(G). Thus the results of this paper settle the first two nontrivial cases (k=3,4).

Section 2 describes the main results. The pairs (d₃(G),d₄(G)), for r-regular simple graphs G, form a subset of the Euclidean plane. It is determined that these are precisely the points with rational coordinates in a polygon with +2 vertices. Moreover, the graphs corresponding to the extreme points of this convex polygon are constructed. The proof method finds its most natural home in unimodular random graphs, and Section 3 generalizes the main results to this setting.