26 problems

Consider the two-colored PAM with $m_1=m_2=m$, attachment kernel … and minority-vertex probability $\mu_1$. PageRank fairness conjecture. For every sufficiently small $c>0$, there…

Fix $m\geqslant2$ and $\delta>0$. Let $T_n$ be the number of triangles in the instantaneous variant of the linear preferential attachment model, with connections specified by the i…

Let $T_n(f)$ be the preferential attachment tree on $[n]$ generated by the nondecreasing attachment function $f:{\mathbb{N}}_0\to\mathbb{R}_{>0}$. Write $D_n(f)$ for the graph dist…

Prokhorenkova et al.'s modularity conjecture. With high probability,

Let $X$ denote the limiting random variable associated with the normalized maximum degree in Theorem 1.2, and let $D_1$ and $D_2$ be the constants appearing there. Maximum-degree l…

Let the PAVD model be the preferential attachment model with vertex death from Definition. Suppose that the attachment and death-rate sequences $b$ and $d$ satisfy Assumptions and.…

Let $G_n$ be the final snapshot of a preferential attachment network on $n$ vertices, and suppose the changepoint is in the late-change regime $\tau_n=n-\Delta$ with…

Let $G_n^h=(V,E)$ be a preferential attachment graph, where $n$ is the number of vertices and $h$ is the number of edges added per step. Write $\operatorname{mod}(G_n^h)$ for its m…

Powerlessness conjecture. When $\gamma<\tfrac{1}{2}$, all tests based on the vertex degrees $\{D_v(n)\}_{v\in[n]}$ are powerless, and all tests based on $G_n$ are powerless.

Let $G(T,\delta,m)$ be the preferential attachment graph and let its Rips complex of radius $r$ be formed using the graph metric. Diameter-dominance conjecture. The Betti numbers o…

For $q\geq 2$ and $m\geq 2q$, let $X(T,\delta,m)$ denote the affine preferential attachment clique complex and let $\beta_q(X(T,\delta,m))$ be its $q$-th Betti number. If…

Let $X(\infty,\delta,m(\cdot))$ be the clique complex of the graph obtained by adding one node and $m(t)$ preferential-attachment edges at each time $t$, where…

Noise-threshold conjecture. For linear preferential attachment (LPA), corresponding to $\alpha=0$ and $\beta=1$, if $\theta=o(n^{-1/2})$, then

Let $PA_t(m,\delta)$ be the preferential attachment graph at time $t$, with parameters $m$ and $\delta$, and let $(PA_t(m,\delta))_{t\ge 1}$ denote the resulting graph sequence. Th…

Let $\mathcal{T}$ be a $(\mu,f,\ell)$-RIF tree, and define … Assume that $\alpha=\infty$, and let $N_0(t,B)$ denote the number of degree-zero vertices present by time $t$ whose fit…

Let $\mathcal{T}$ be a $(\mu,f,\ell)$-RIF tree, and define … For $\alpha<\infty$, let $N_k(t,B)$ denote the number of degree-$k$ vertices present by time $t$ whose fitness lies in…

Let $m(t)$ denote the time-dependent memory parameter in Regime $R3$, let $\mu_\epsilon$ be the mean of the fitness increments, and let the cumulative fitness distribution be the d…

Let $m\in\mathbb{N}$, let $G_t$ be a graph in Regime $R2$, and let $\mathbf{\deg}_t$ be its empirical degree distribution. Let $\mathbf{\deg}_t^{BB(m)}$ be the empirical degree distr…

Sharp large-time behavior conjecture. For $\tau$ fixed,

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

Scaling-limit conjecture. There exists a random compact metric space $\mathcal{L}^{(S)}_{\delta}$ such that

Affine preferential attachment metric conjecture. The function $d_\delta$ is a metric on trees with at least $3$ vertices.

For $\gamma>1$, define … where $\log x=\max\{0,\log x\}$. Let $G_n$ be the geometric preferential attachment graph under the paper's standing assumptions, let $v_n$ be the vertex s…

Let $N$ be the number of types, let $m$ be the number of sampled vertices added at each step, and let $p_{\mathbf{u}}^i$ be the probability that a new vertex is assigned type $i$ w…

Let $G_{m,\delta}(t)$ be the preferential attachment graph with parameters $m$ and $\delta$, and let $V_1,V_2\in [t]$ be two uniformly chosen independent vertices. Write…