Preferential attachment graphs approaching the Rado graph

Let GG' be a finite directed graph containing no isolated nodes, and let ff be a function satisfying f(t)tf(t)\leq t for all tt. Suppose there are constants 0<c1c2<10<c_1\leq c_2<1 such that

c1tf(t)c2tc_1\cdot t\leq f(t)\leq c_2\cdot t

for all sufficiently large tt. In the graph preferential attachment process GPAf(G){\textrm{GPA}_f}(G'), each new vertex attaches according to the degree-proportional rule described in the construction.

Rado graph conjecture. With probability 11, the infinite limit of GPAf(G){\textrm{GPA}_f}(G') is the Rado graph.

The preceding theorem establishes the analogous statement for directed multigraphs when f(t)=Θ(t)f(t)=\Theta(t). This conjecture asserts that the result remains true for graphs, where the process selects endpoints without replacement; the restriction f(t)tf(t)\leq t ensures that this selection is viable.

Sources & referencesView supporting material

Primary source

Richard Elwes, “Preferential Attachment Processes Approaching The Rado Multigraph”, arXiv:1502.05618 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.