The lower-bound conjecture for coupon collecting with friends

About 5 years old · traced to

Let nn) collectors each seek a complete collection of mm coupon types. The process has a collection phase of rcr_c rounds, followed by an exchanging phase of rer_e rounds in which collectors interact and exchange coupons.

Lower-bound conjecture. If

rc=O(n+nln⁡nm),r_c=O\left(n+\frac{n\ln n}{m}\right),

then

re=Ω(mlog⁡mn)r_e=\Omega(m\log mn)

is necessary to succeed with any positive constant probability.

The conjecture asserts that the currently known upper bound on the number of interactions is tight even when only a positive constant success probability is required. The motivation is that existing lower bounds account only for the difficulty of ensuring a single interaction, not for the difficulty collectors with incomplete collections face in obtaining multiple coupons during the exchanging phase.

References

Primary source

Dan Alistarh and Peter Davies, “Collecting Coupons is Faster with Friends”, arXiv:2112.05830 (2021).

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.