Evolving Shelah-Spencer Graphs

2018/09/21 by Elwes, Richard
#05C80 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1809.08333

Abstract

An evolving Shelah-Spencer process is one by which a random graph grows, with at each time τ∈ \bf N a new node incorporated and attached to each previous node with probability τ^-α, where α∈ (0,1) ∖ \bf Q is fixed. We analyse the graphs that result from this process, including the infinite limit, in comparison to Shelah-Spencer sparse random graphs discussed in [Spencer, J., 2013. The strange logic of random graphs (Vol. 22). Springer Science & Business Media.] and throughout the model-theoretic literature. The first order axiomatisation for classical Shelah-Spencer graphs comprises a 'Generic Extension' axiom and a 'No Dense Subgraphs' axiom. We show that in our context 'Generic Extension' continues to hold. While 'No Dense Subgraphs' fails, a weaker 'Few Rigid Subgraphs' property holds.

Related

• Limits of multiplicative inhomogeneous random graphs and Lévy trees: The continuum graphs
• Growing random graphs with a preferential attachment structure
• On the growth of a superlinear preferential attachment scheme
• Triangle-free Subgraphs at the Triangle-Free Process
• DOP and FCP in generic structures