Counterexamples to Aigner's majorization conjecture for star-forest search
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\ge6$. The obstruction uses two…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.38284
curl -X POST /api/v1/records/arxiv/2609.38284/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.38284/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'