Conjecture on minimum-degree construction time in the semi-random graph process

Let nn be the number of vertices, let k=k(n)k=k(n), and let τ(σ,Pmin,k)\tau(\sigma,\operatorname{\mathcal{P}}_{\min,k}) denote the first round in which Builder's graph has minimum degree at least kk. The notation k=o(n)k=o(n) means that k/n0k/n\to 0 as nn\to\infty.

Minimum-degree construction-time conjecture. The conclusion of Theorem~~ holds for k=o(n)k=o(n).

The preceding theorem proves the corresponding upper bound when k=o(n1/2)k=o(n^{1/2}), while a weaker upper bound is established for k=o(n)k=o(n). Thus the conjecture asserts that the sharper estimate from the second part extends to the larger range.

Sources & referencesView supporting material

Primary source

Sofiya Burova and Lyuben Lichev, “The semi-random tree process”, arXiv:2204.07376 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.