기초과학연구원 이산수학그룹
On March 24, 2026, Hidde Koerts from the University of Waterloo gave a talk at the Discrete Math Seminar on characterizing tournaments with no backedge graph of small clique number. The title of his talk was “Characterizing large clique number in tournaments“.
A backedge graph of a tournament $T$ with respect to a total ordering $\prec$ of the vertices of $T$ is a graph on $V(T)$ where $uv$ is an edge if and only if $uv \in A(T)$ and $v \prec u$. In 2023, Aboulker, Aubian, Charbit and Lopes introduced the clique number of tournaments based on backedge graphs as a natural counterpart to the dichromatic number of tournaments. Specifically, the clique number of a tournament is the minimum clique number of a backedge graph when considering all possible orderings.
Given this definition, it is not immediately clear what the canonical clique object should be. In this talk, we provide an answer to this question. We show that if a tournament has large clique number, it contains a reasonably large subtournament from one of two simple and previously studied families of tournaments of unbounded clique number.
This talk is based on joint work with Logan Crew, Xinyue Fan, Benjamin Moore, and Sophie Spirkl.