The linkedness characterization of the two-agent price of connectivity

Let GG be a biconnected graph. For positive integers a,ba,b, say that GG is (a,b)(a,b)-linked if, for every pair of disjoint vertex sets M1,M2M_1,M_2 with M1=a|M_1|=a and M2=b|M_2|=b, there are disjoint connected subgraphs G1,G2G_1,G_2 such that MiGiM_i\subseteq G_i for i=1,2i=1,2. Let PoC(G,2)\operatorname{PoC}(G,2) denote the price of connectivity for two agents. Linkedness conjecture. If k2k\geq 2 is an integer and GG is (2,k1)(2,k-1)-linked but not (2,k)(2,k)-linked, then

PoC(G,2)=2k12k.\operatorname{PoC}(G,2)=\frac{2k-1}{2k}.

The conjecture would determine the price of connectivity for the two-agent case in terms of linkedness; the paper verifies it for complete graphs with an arbitrary matching removed, but does not establish it for general biconnected graphs.

Sources & referencesView supporting material

Primary source

Xiaohui Bei, Ayumi Igarashi, Xinhang Lu and Warut Suksompong, “The Price of Connectivity in Fair Division”, arXiv:1908.05433 (2022).

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.