Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation
We disprove the analogue of Hedetniemi's conjecture for Shannon OR-capacity, which asserts that the capacity of a categorical product equals the smaller capacity of its factors. For every sufficiently large complete graph, we construct a second graph of larger capacity such that their categorical product has capacity strictly below that of the complete graph. Further constructions show that, for every real threshold above an explicit constant, both factor capacities can exceed that threshold while the product capacity lies below it. We also construct graph pairs, again with one complete…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.41977
curl -X POST /api/v1/records/arxiv/2610.41977/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.41977/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'