Random Meta-Structure: A Random Graph Model Based on Abstract Binary Relations

This paper proposes the random meta-structure, an extension of the meta-structure framework in the direction of randomization, whose basic construction is inspired by the Erdős–Rényi random graph model. Starting from a meta-structure L = (V, E) and taking an arbitrary symmetric binary relation R as a rule-based constraint, the random meta-structure connects a pair of vertices satisfying R with probability p, and leaves them disconnected otherwise; it is denoted by G(V, p, R). This construction can be viewed either as a randomization of the meta-structure, or as an abstraction of the classical random graph model: it replaces the global connection rule with a local connection rule defined by an arbitrary binary relation. When R is the complete relation, the model reduces to the classical ER random graph. The basic statistics of the random meta-structure are derived, including expected degree, degree distribution, expected number of isolated vertices, and subgraph counts. The critical condition for the emergence of a giant component is then analyzed. For skeleton graphs that satisfy bounded degree and expansion, strict conclusions are obtained directly from spectral percolation theory. For skeleton graphs that do not satisfy these conditions, the model can serve as a mathematical probe, rapidly yielding heuristic estimates of the giant component threshold via parameters such as average degree or spectral radius, thus providing initial predictions for problems that lack an exact theory. The application of the model is illustrated across different mathematical structures through examples including random subgroups of Cayley graphs, coprime graphs, and twin prime graphs.