Property (*) range extension to d = o(n/log n)

Informal Conjecture on Property (*) for d = o(n/log n) · arXiv:2207.13651

arXiv Informal medium confidence— first stated 2022-07-27

Authors: Jacob Fox, Sammy Luo, Huy Tuan Pham

Status open high confidence

Fox, Luo, and Pham prove Property (*) for the random irregular subgraph model when d = o(n/(log n)^{12}) (Theorem 1.3), and conjecture the result extends to the wider range d = o(n/log n). No subsequent paper resolving this conjecture was found in a web search; the conjecture remains open as of May 2026. The paper appeared in Random Structures & Algorithms (2024).

Reviewer notes. The paper's main theorem (Theorem 1.3) covers d = o(n/(log n)^{12}); the informal conjecture asks to push this to d = o(n/log n). The authors also remark that for d = omega(n/log n) the model likely fails Property (*). No follow-up resolving or extending this conjecture was found in the indexed literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. The irregular random subgraph $H = H(G)$ satisfies Property $(*)$ — that is, $m(H,k) = (1+o(1))n/(d+1)$ for all $0 \leq k \leq d$ — with high probability for all $d = o(n/\log n)$.

Context

After proving Theorem 1.3 for $d = o(n/(\log n)^{12})$, the authors conjecture the range extends to $d = o(n/\log n)$. They also remark that for $d = \omega(n/\log n)$ the random subgraph model likely fails to satisfy Property $(*)$, and that new ideas would be required to establish Conjecture 1.2 in the full range.

Notes. Stated in prose without a labelled theorem environment: 'We conjecture that with high probability for all d = o(n/log n), the irregular random subgraph H satisfies Property *'.

Source paper

On random irregular subgraphs
Jacob Fox, Sammy Luo, Huy Tuan Pham · 2022-07-27
https://arxiv.org/abs/2207.13651 PDF source