Tournament (graph theory, $u\to v\text{or}v\to u$)

A tournament is an orientation of a complete graph: between each pair of distinct vertices there is exactly one directed edge.

A median order maximizes the number of forward directed edges in a linear ordering of the vertices of a tournament. Every interval inherits a median order. Moving the first vertex of an interval to its end proves that it has at least as many outgoing as incoming edges in that interval; otherwise the move would increase the number of forward edges. Reversing all edges and the order gives the dual assertion for the last vertex.

A graph embedding into an ordered tournament is half-sparse when the displayed inequality holds for every proper final interval $I$. Reserving two extra tournament vertices allows extension at any outward-oriented leaf: the median order of a tournament supplies at least half of the later vertices as outneighbours of the parent's image, while half-sparsity leaves at least one of them unused. Adding one image while extending every old final interval by two preserves the inequality.

A regular tournament has equal outdegree and indegree at every vertex. On $2k+1$ vertices, label by residues modulo $2k+1$ and direct $i\to j$ when $j-i\in \{1,\dots ,k\}$. This gives an explicit regular tournament. It contains no outward-oriented star with more than $k$ leaves.