Minimum Degree after Random Edge Percolation

Definitions and mathematical statement

Let $G$ have minimum degree $D$, and form a random graph $H$ by retaining each edge of $G$ independently with probability $1/2$, keeping the vertex set unchanged. Under the conventional interpretation that $G$ is a finite, nonempty, simple undirected graph, define \[ \delta(G)=\min_{v\in V(G)}\deg_G(v)=D, \qquad d(H)=\max_{\substack{F\subseteq H\\V(F)\ne\varnothing}}\delta(F). \] Here $F$ ranges over subgraphs with at least one vertex, and $d(H)$ is a random variable. The source does not explicitly specify finiteness, simplicity, or directedness, so this graph convention requires confirmation.

The supplied problem asks how large $d(H)$ must be in terms of $D$, uniformly over the intended class of graphs $G$. In particular, it asks whether \[ d(H)\geq \frac{D}{3}-o(D). \] The asymptotic notation would mean an error $r(D)$ satisfying $r(D)/D\to0$ as $D\to\infty$. However, the source does not specify the probabilistic meaning of this inequality, or whether the error is uniform over $G$. For example, an assertion about $\mathbb E[d(H)]$ and an assertion that $d(H)$ exceeds a threshold with probability tending to one are different statements. No such interpretation is selected here. Consequently, the displayed inequality records the supplied target but is not a fully quantified conjecture until these qualifications are resolved.

Short English statement

Independently keep half the edges of a graph of minimum degree $D$, and consider the greatest minimum degree among its nonempty subgraphs. The question asks for a universal lower bound, especially $D/3-o(D)$. The intended probability guarantee, graph class, and uniformity of the error term are unspecified.

Sources

• Local UnsolvedMath registry, supplied source record for permanent ID $30003337$, titled Minimum Degree after Random Edge Percolation; exact source problem code catalogue entry. The record belongs to the Oberwolfach Reports Open Problems collection and supplies proposed year $2017$, without a named proposer.
• Supplied report citation: Combinatorics (2018), Oberwolfach Reports, DOI 10.4171/owr/2017/1, pp. 5--81. Original OWR report: https://doi.org/10.4171/owr/2017/1. The supplied title year is retained despite its apparent mismatch with the DOI year and proposed year.
• Supplied literature reference: Bukh--Krivelevich--Narayanan, "colouring random subgraphs": https://arxiv.org/abs/2312.08340.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that the universal lower bound remains $D/4$ minus lower-order terms, while a 2025 construction gives an upper bound $D/3$ plus lower-order terms for infinitely many degrees; it describes the exact asymptotic value as open. This is supplied dated curation, not an independently verified literature assessment. Its probability guarantees and other technical hypotheses are not supplied.