Limits and Regularity of Graph Sequences

Abstract

A limit of a sequence of graphs is an object that encodes approximate combinatorial information of the sequence. [Lovasz et al citation, 2008] defines such a limit for sequences of dense graph. For example, if a dense graph sequence (Gn) converges to a graphon W; then en = e(Gn)/v(Gn)² ϵ [0; 1=2) (the number of edges of Gn relative to its number of nodes) converges to some e; and e is directly computable from W: As a second example, if Mn denotes the size of the maximum cut of Gn; and mn = Mn/v(Gn)2 ϵ [0; 1=2) is this size relative to the number of nodes, then mn converges as n → ∞; and once again this limit is directly computable from W: If (Gn) is any less-than-dense sequence, the limit W is still well-defined, but W = 0; which does not carry any information. To account for this, [Benjamini and Schramm citation] have defined a different kind of limit for sparse graph sequences. However, the limit is non-sensical for any greater-than-sparse sequence. This research attempts to fill the gap, by defining limits for a variety of intermediate degree sequences, those strictly between being sparse and being dense. Given a graph N; does there exist a graph M such that the 1-neighborhoods of every vertex of M are isomorphic to N? When such an M exists, it is called a mosaic of N: Bulitko (1977) proved this question to be algorithmically undecidable. We therefore consider a slightly different question: Given a graph N and assuming it has a mosaic, is that mosaic unique, or if not, what characterizes the collection of all such mosaics? A resolution of this question could have applications to sparse regularity lemmas, analogous to Szemeredi's famous regularity lemma for sparse graphs.