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 asks for a function $f$ such that every tournament $T$ has a BST-ordering $\prec$ with $\omega(T^{\prec})\leq f(\operatorname{\overrightarrow{\omega}}(T))$. It proposes BST-orderings as canonical candidates for Conjecture 3.13. The status remains unclear because the May 2026 review could not identify which conjecture a related 2024 counterexample targets.

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 complete formula was verified in the cached arXiv HTML. Full-text verification of arXiv:2401.07776 is still needed to settle the status.

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 that $\omega(T^{\prec})\leq f(\operatorname{\overrightarrow{\omega}}(T))$.

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. The source's grammatical typo 'such:' is normalized to 'such that'.

Source paper

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