Counterexamples to Aigner's majorization conjecture for star-forest search
Abstract
In adaptive quantitative group testing with exactly two defective items, each test reports how many defectives lie in a chosen subset. We study configurations in which the possible defective pairs form the edges of a star forest. Aigner proved a necessary majorization condition on the ordered star sizes for identifying the defective pair within a prescribed number of tests, and conjectured that this condition was sufficient. We disprove the conjecture by an explicit six-test counterexample and give an analytic family of counterexamples for every test budget k≥6. The obstruction uses two tight prefix sums to force incompatible demands on the outcomes of the first test. We also prove, by exhaustive computation combined with analytic reductions, that the converse holds for 0≤ k≤5. Thus six is the first test budget at which majorization alone fails. The counterexamples and their infinite extension do not depend on the exhaustive computation.
Related
- A counterexample to Huang's weak majorization conjecture
- Counterexamples to the Monotone Completeness Conjecture
- Counterexamples to the ordinary Fried conjecture near hyperbolic metrics
- Counterexamples to the inhomogeneous Duffin-Schaeffer Conjecture
- A Note on the OpenAI Construction of Counterexamples to the Kaplansky Direct-Finiteness Conjecture
BibTeX
@misc{karpelevitch2026counterexamples,
title = {{Counterexamples to Aigner's majorization conjecture for star-forest search}},
author = {Fedor Karpelevitch},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38284},
eprint = {2609.38284},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38284},
}
RIS
TY - UNPB
TI - Counterexamples to Aigner's majorization conjecture for star-forest search
AU - Fedor Karpelevitch
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.38284
UR - https://arxiv.org/abs/2609.38284
AB - In adaptive quantitative group testing with exactly two defective items, each test reports how many defectives lie in a chosen subset. We study configurations in which the possible defective pairs form the edges of a star forest. Aigner proved a necessary majorization condition on the ordered star sizes for identifying the defective pair within a prescribed number of tests, and conjectured that this condition was sufficient. We disprove the conjecture by an explicit six-test counterexample and give an analytic family of counterexamples for every test budget k≥6. The obstruction uses two tight prefix sums to force incompatible demands on the outcomes of the first test. We also prove, by exhaustive computation combined with analytic reductions, that the converse holds for 0≤ k≤5. Thus six is the first test budget at which majorization alone fails. The counterexamples and their infinite extension do not depend on the exhaustive computation.
ER -