Preferential attachment graphs approaching the Rado graph
Preferential attachment graphs approaching the Rado graph
Let be a finite directed graph containing no isolated nodes, and let be a function satisfying for all . Suppose there are constants such that
for all sufficiently large . In the graph preferential attachment process , each new vertex attaches according to the degree-proportional rule described in the construction.
Rado graph conjecture. With probability , the infinite limit of is the Rado graph.
The preceding theorem establishes the analogous statement for directed multigraphs when . This conjecture asserts that the result remains true for graphs, where the process selects endpoints without replacement; the restriction 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.