Asymptotically optimal time-and-budget conjecture for k-connectivity

Let kk be a positive integer, let ε>0\varepsilon>0, and let a (t,b)(t,b)-strategy BB of Builder be a strategy that observes at most tt arriving edges and purchases at most bb of them. A graph is kk-connected if it remains connected after deletion of any set of fewer than kk vertices. Asymptotically optimal time-and-budget conjecture for kk-connectivity. If

t(1+ε)nlogn/2andb(1+ε)kn/2,t\ge(1+\varepsilon)n\log n/2\quad\text{and}\quad b\ge(1+\varepsilon)kn/2,

then there exists a (t,b)(t,b)-strategy BB of Builder such that

limnP(Bt is k-connected)=1.\lim_{n\to\infty} \mathbb{P}(B_t\text{ is $k$-connected})=1.

The claim is stated as an open extension of the established construction for minimum degree: allowing asymptotically optimal time and budget should suffice to construct a kk-connected graph. The source notes that the case k=1k=1 is trivially true.

Sources & referencesView supporting material

Primary source

Alan Frieze, Michael Krivelevich and Peleg Michaeli, “Fast construction on a restricted budget”, arXiv:2207.07251 (2024).

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.