Linear asymptotics conjecture for the Waiter-Client tree degree threshold

Let D(n)D(n) be the largest integer tt such that for every tree TT with v(T)=nv(T)=n and Δ(T)t\Delta(T)\leq t, Waiter has a winning strategy in WC(n,T)\operatorname{WC}(n,T). Linear asymptotics conjecture. There exists a constant cc such that

D(n)=cn+o(n).D(n)=cn+o(n).

The paper establishes linear lower and upper bounds on D(n)D(n) that differ by a multiplicative constant; the conjecture asserts that a limiting linear constant exists.

Sources & referencesView supporting material

Primary source

Grzegorz Adamski, Sylwia Antoniuk, Małgorzata Bednarska-Bzdęga, Dennis Clemens, Fabian Hamann and Yannick Mogge, “Creating spanning trees in Waiter-Client games”, arXiv:2403.18534 (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.