Alishahi–Meunier conjecture on stable almost fair splittings of paths

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 q1q-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 q1q-1 vertices in each VjV_j, with sizes differing by at most one, and satisfying

SiVjVj+1q1|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.

Sources & referencesView supporting material

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.