Giant Components in Nonlinear Degree-Dependent Random Graphs

Definitions and mathematical statement

For a finite graph $H$, let $V(H)$ be its vertex set and define its largest-component size by \[ L_1(H)=\max\{\lvert V(C)\rvert:C\text{ is a connected component of }H\}, \] with $L_1(H)=0$ when $V(H)=\varnothing$. For a sequence of graphs whose vertex counts tend to infinity, the usual giant-component question concerns components containing a positive proportion of all vertices. In a random-graph formulation, the probability quantifiers and limiting regime must also be specified.

The supplied problem asks: determine the emergence and size of the giant component in the degree-dependent random-graph processes \[ G^f_{n,m}\qquad\text{and}\qquad G^{f,*}_{n,m} \] when the attachment function $f$ is genuinely nonlinear. This entails describing the transition and the asymptotic behavior of the largest-component sizes in the intended parameter regime.

Unresolved formulation. The supplied record does not define either random-graph process. In particular, it does not specify the vertex sets, initial graphs, transition probabilities, the roles and admissible ranges of $n$ and $m$, the treatment of loops and repeated edges, or the distinction denoted by the asterisk. It also does not give the domain, codomain, positivity or growth assumptions on $f$, or a definition of "genuinely nonlinear." The asymptotic scaling and required probability quantifiers are absent. Consequently, the displayed problem is a faithfully retained research target, but a fully quantified mathematical statement cannot be recovered from this record alone; the missing process definitions and hypotheses require source clarification.

Short English statement

Determine when a giant connected component appears, and how large it becomes, in the two supplied degree-dependent random-graph models with genuinely nonlinear attachment. The record omits the model definitions, admissible attachment functions, and limiting regime, so the precise probabilistic statement remains unresolved.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004137$, title Giant Components in Nonlinear Degree-Dependent Random Graphs, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2019 and names no individual proposer.
• Supplied report citation: Combinatorics, Probability and Computing (2020), Oberwolfach Reports, DOI 10.4171/owr/2019/19, pp. 1113--1189. https://doi.org/10.4171/owr/2019/19. The background attributes the problem to workshop open-problem discussions documented in Oberwolfach Reports.
• Supplied literature reference, labeled Janson--Warnke: https://arxiv.org/abs/1904.11861. No title or specific supporting result is supplied.
• Supplied literature reference, labeled Oberwolfach problem report: https://oa.tib.eu/renate/bitstreams/47388107-8726-4158-8c92-21a2323c2cf7/download.
• Literature assessment date: 2026-08-22. This is supplied dated curation, not an independently verified assessment. It labels the problem open and states that giant-component behavior is understood for several linear or specially structured degree-dependent attachment rules, while the genuinely nonlinear problem is not settled in general. The background explicitly calls this dated literature triage derived from the supplied OWR curation and requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports that the official Oberwolfach report was checked directly, with definitions restored in the clean statement. These are supplied verification claims; the supplied clean statement itself contains no process definitions, and no independent source check is asserted here.