Alishahi–Meunier conjecture on stable almost fair splittings of paths

About 8 years old · traced to

Let qq be a positive integer, and let PP be a path whose vertex set is partitioned into mm subsets V1,…,VmV_1,\dots,V_m, each of size at least q−1q-1. A set of vertices is qq-stable if any two distinct vertices in it are at distance at least qq in PP. Alishahi–Meunier's conjecture. There exist pairwise disjoint qq-stable sets S1,…,SqS_1,\dots,S_q covering all but q−1q-1 vertices in each VjV_j, with sizes differing by at most one, and satisfying

∣Si∩Vj∣≥⌊∣Vj∣+1q⌋−1|S_i\cap V_j|\ge \left\lfloor\frac{|V_j|+1}{q}\right\rfloor-1

for all i∈{1,2,…,q}i\in\{1,2,\dots,q\} and j∈{1,2,…,m}j\in\{1,2,\dots,m\}. This conjecture asks for a particularly balanced stable splitting of a path; the source gives no resolution, so its status remains open.

References

Primary source

Alexander Black, Umur Cetin, Florian Frick, Alexander Pacun and Linus Setiabrata, “Fair splittings by independent sets in sparse graphs”, arXiv:1809.03268 (2018).

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.