The linkedness characterization of the two-agent price of connectivity

About 7 years old · traced to

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 Mi⊆GiM_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 k≥2k\geq 2 is an integer and GG is (2,k−1)(2,k-1)-linked but not (2,k)(2,k)-linked, then

PoC⁡(G,2)=2k−12k.\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.

References

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.