ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let qq be a positive integer, and let PP be a path whose vertex set is partitioned into mm subsets V1,…,VmV_1,\ldots,V_m, each of size at least q−1q-1. A subset of vertices is qq-stable if no two of its vertices are at distance less than qq, with distance counted in edges.

Fair stable-set splitting conjecture. There always exist pairwise disjoint qq-stable sets S1,…,SqS_1,\ldots,S_q covering all vertices but q−1q-1 in each VjV_j, with sizes differing by at most one, and satisfying

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

for all i∈[q]i\in[q] and all j∈[m]j\in[m].

This conjecture extends the paper's two-independent-set theorem to an arbitrary number of sets: when q=2q=2, qq-stable sets are precisely independent sets. Its resolution is not given in the supplied text.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.