BST-ordering bound for tournament clique number

Conjecture 3.16 · arXiv:2310.04265

arXiv Conjecture high confidence— first stated 2023-10-06

Authors: Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes

Status unclear medium confidence

Conjecture 3.16 specialises Conjecture 3.13 to BST-orderings of tournaments, asserting the existence of a function f such that every tournament admits a BST-ordering satisfying a simultaneous bound on clique number and dichromatic number. A follow-up paper (arXiv:2401.07776, Aubian 2024) provides a counterexample to 'a conjecture of Aboulker, Aubian, Charbit and Lopes' from the source paper, but the available abstract does not identify which specific conjecture was disproved; it is not confirmed whether Conjecture 3.16 is the target.

Cited literature (1)

counterexample Computing the clique number of tournaments (2024)

Guillaume Aubian · arXiv preprint · arXiv:2401.07776

Proves that deciding whether a tournament has clique number at most k (k >= 3) is NP-complete, and provides a counterexample to an unspecified conjecture of Aboulker, Aubian, Charbit and Lopes from arXiv:2310.04265; it is not confirmed from the abstract alone whether this counterexample targets Conjecture 3.16 specifically.

Reviewer notes. The full statement of Conjecture 3.16 was not completely retrievable from the arXiv HTML render (truncated mid-sentence). A counterexample to some conjecture in arXiv:2310.04265 is reported in arXiv:2401.07776, but identifying whether it is Conjecture 3.16 (BST-orderings) or another conjecture in the paper requires reading the full text of 2401.07776, which could not be retrieved (PDF binary). The paper arXiv:2402.10782 (NP-completeness of forest-orderings) is thematically related but does not address Conjecture 3.16 directly.

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

Conjecture. There exists a function $f$ such that, for every tournament $T$, there exists a $BST$-ordering $\prec$ of $T$ such:

Context

$BST$-orderings are identified as natural candidates for the ordering of Conjecture 3.13. This conjecture specialises Conjecture 3.13 to $BST$-orderings, which arise from the theory of binary search trees on tournaments.

Notes. Statement appears truncated in the source; conditions following 'such:' are not captured in the extracted text.

Source paper

Clique number of tournaments
Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes · 2023-10-06
https://arxiv.org/abs/2310.04265