124 problems

Lower-bound conjecture for tournament dijoins. One should have

A regular tournament is a tournament in which every vertex has the same indegree and outdegree. Kelly's conjecture. Every regular tournament on $n=2k+1$ vertices has a decompositio…

Sumner's conjecture. Every oriented tree of order $n>1$ is $(2n-2)$-unavoidable; equivalently,

Pokrovskiy's conjecture. For every $k\in\mathbb{N}$, there exists an integer $h(k)$ such that every $2k$-connected tournament with $\delta^0(D)\geq h(k)$ is $k$-linked.

Let $T$ be an oriented tree with $k$ edges and $ll$ leaves, and let a tournament be an orientation of a complete graph. Havet–Thomassé's conjecture. Every tournament on $k+\ell$ ve…

Let $\vec{H}$ be a strongly connected tournament with $k:=v(H)\geqslant 4$, and let $p\gg n^{-2/(k+1)}$. Tournament orientation-counting conjecture. Then, with high probability, ……

Directed Erdős–Hajnal conjecture. For every tournament $H$, there exists $\epsilon(H)>0$ such that every $H$-free tournament with $n$ vertices contains a transitive subtournament of…

Let $Q_n$ be the tournament on $[n]=\{1,\ldots,n\}$ obtained from the natural transitive tournament by reversing precisely the consecutive pairs $12,23,\ldots,(n-1)n$. Equivalently…

Approximation conjecture. There is a function $f$ such that for every integer $k$, there is a polynomial-time algorithm which, given a tournament $T$, correctly concludes that…

Subquadratic growth conjecture.

Let $n$ be sufficiently large, and let $G$ be a regular tripartite tournament on $3n$ vertices. Denote by ${\mathcal T}_\triangle$ the known regular tripartite tournament obtained…

The all-$k$ dijoin counterexample conjecture. For any $k\geq3$, there is a tournament $T_k$ with $\operatorname{inv}(T_k)=k$ such that

The $Q_n$ inversion-number conjecture.

Price-of-symmetrisation conjecture. For $2\leq n\leq 10$,

Conjecture on the possible bases.

Let $cmathcal{P}$ be a hereditary property of tournaments, and let $cmathcal{P}_n$ denote the tournaments in $cmathcal{P}$ on $n$ vertices. There exists a constant $calpha>0$ and a…

Exact transitive-triple packing conjecture.

Let $T$ be a tournament, namely an oriented graph in which every pair of distinct vertices is joined by exactly one directed arc. For a vertex $x$, let $N_T^+(x)$ and $N_T^{++}(x)$…

A digraph is semicomplete if it has no pair of non-adjacent vertices. A tournament is an orientation of a complete graph, hence a semicomplete digraph with no directed 2-cycles. A…

Bang-Jensen–DeVos–Mütze conjecture. Every $(2k-1)$-strong semicomplete digraph on at least $2k+1$ vertices contains a spanning $k$-strong tournament.

Let $T$ be an orientation of a tree with maximum degree at least $3$. An oriented graph $D$ is converse invariant if $f_T(D)=f_T(\overline{D})$ for every tournament $T$, where…

Deficient-sequence characterization conjecture. A partition $\lambda$ is complete if and only if, for every $\lambda'\subseteq\lambda$, the set $\mathfrak{S}^2(\lambda')$ has no de…

Complete-partition classification conjecture. A partition $\lambda$ is complete if and only if

Bebeacua's conjecture. For every positive integer $n$,

A poset tournament is a tournament $T$ for which there exists a total ordering $<$ of $V(T)$ such that, for all $u<v<w$, if $u\to_T v$ and $v\to_T w$, then $u\to_T w$. Equivalently…