Simultaneous fair representation in path partitions

Conjecture 1.6 · arXiv:1611.03196

arXiv Conjecture low confidence— first stated 2016-11-10

Authors: Ron Aharoni, Noga Alon, Eli Berger, Maria Chudnovsky, Dani Kotlar, Martin Loebl, Ran Ziv

Status open medium confidence

No follow-up paper was found that resolves the full statement of Conjecture 1.6 from arXiv:1611.03196, which asks for an independent set in a partitioned path satisfying both the global budget condition (sum b_i ≤ m/2) and the per-part cap (b_i ≤ 1) simultaneously. Related work has appeared on fair representation in cycles (computational complexity, PPA-completeness) and sparse graphs, but these address different graph classes. Alishahi and Meunier (2017, arXiv:1704.02921) proved 'a conjecture of Ron Aharoni and coauthors' about colored paths, but this could not be confirmed to be specifically Conjecture 1.6; it may instead resolve a different conjecture from the same paper.

Cited literature (1)

partial Fair splitting of colored paths (2017)

Meysam Alishahi, Frédéric Meunier · arXiv preprint · arXiv:1704.02921

Proves 'a conjecture of Ron Aharoni and coauthors' about fair splitting of colored paths into two disjoint independent sets, but which specific conjecture from arXiv:1611.03196 this resolves could not be confirmed; it may be a different conjecture from the same paper rather than Conjecture 1.6.

Reviewer notes. Conjecture 1.6 is a joint condition combining two separately-provable bounds (Theorem 1.7 of the source paper). Related literature has grown around cycles and sparse graphs (fair representation in cycles, PPA-completeness of finding such sets), but no paper explicitly claiming to prove or disprove Conjecture 1.6 for paths was found. The conjecture is 9 years old, so medium rather than high confidence in 'open' status.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. Given a partition of the vertex set of a path into sets $V_1, \ldots, V_m$ there exists an independent set $S$ and integers $b_i$, $i \leq m$, such that $|S \cap V_i| \geq \frac{|V_i|}{2} - b_i$ for all $i$, and 1. $\sum_{i \leq m} b_i \leq \frac{m}{2}$ and 2. $b_i \leq 1$ for all $i \leq m$.

Context

The paper proves (Theorem 1.7) that either condition alone holds for the independence complex of a path, but not necessarily both simultaneously. Conjecture 1.6 asserts both conditions can be satisfied at once. The matching complex of a path is the independence complex of a path one vertex shorter.

Notes. PDF source — sum symbol garbled as (cid:80) and fractions may be garbled; LaTeX reconstructed from context.

Source paper

Fair representation by independent sets
Ron Aharoni, Noga Alon, Eli Berger, Maria Chudnovsky, Dani Kotlar, Martin Loebl, Ran Ziv · 2016-11-10
https://arxiv.org/abs/1611.03196 PDF source