17 problems

A Baxter permutation of size $n$ is a permutation avoiding the two patterns specified in the source, and bipolar-oriented planar maps with general face degrees correspond to Baxter…

Let $G$ be an oriented graph, let $\b7$ denote its minimum semidegree, and let $k$ be a nonnegative integer. An orientation of the $k$-edge path is an oriented graph obtained by as…

For $\gamma\in(0,2)$ and $\widetilde\theta\in(0,\pi)$, let $\mathfrak L_\Phi^{\operatorname{LDP}}$ and $\mathfrak L_\Phi^{\operatorname{SDP}}$ denote candidate random functions obt…

For a digraph $D$, let $ell(D)$ be the length of a longest directed path, let $g(D)$ be its girth, and let $delta^+(D)$ be its minimum out-degree. Proposed weaker Thomassé conjectu…

Let $D$ be an oriented graph, and let $delta$ denote its minimum out-degree. Thomassé's conjecture. The graph $D$ contains a directed path of length $2\delta$. This is the $g=3$ ca…

Let $k\in\mathbb N$, and let an oriented graph be a digraph with no pair of oppositely directed edges. Thomassé's conjecture. Every oriented graph of minimum outdegree at least $k$…

Let $l$ and $k$ be positive integers, and let $T$ be a tournament with $l^{k-1}+1$ vertices. A directed monochromatic path has all edges of one colour, while a directed rainbow pat…

The extremal digraph conjecture for directed paths. For every $k,n\in \mathbb{N}^*$ with $n\ge 3k$,

Choi–Lidický–Pfender conjecture.

An oriented graph is a digraph without 2-cycles. Let $h$ and $g$ be positive integers, and let $l(h,g)$ be the minimum integer such that every oriented graph of girth $g$ and minim…

Let $\vec{K}_{\mathbb{N}}$ be the complete symmetric digraph on the natural numbers, with each directed edge coloured red or blue. A red directed path of length $r$ is a directed p…

Let $Q_n$ be the $n$-dimensional hypercube, identified with the power set $\mathcal{P}[n]$. For disjoint subsets $A,B\subseteq Q_n$, let $\overrightarrow{p}_v(A,B)$ denote the maxi…

Let $Q_n$ be the $n$-dimensional hypercube, identified with the power set $\mathcal{P}[n]$. For disjoint subsets $A,B\subseteq \mathcal{P}[n]$, let $\overrightarrow{p}_e(A,B)$ deno…

Erdős–Sands–Sauer–Woodrow conjecture. For each positive integer $k$ there is a least integer $f(k)$ such that every $k$-colored tournament contains a set $S$ of $f(k)$ vertices wit…

Thomassé's conjecture. The number of induced $3$-vertex directed paths in $G$ is at most

Let a path with two blocks be an oriented path whose arcs occur in two consistently oriented blocks, and let an $n$-chromatic digraph be a digraph of chromatic number $n$. El-Sahil…

Let $G$ be an oriented graph such that $d^+(v)+d^-(v)=d$ for every vertex $v$ of $G$, where $d$ is odd. Define the excess of $G$ by … where $d^+(v)$ and $d^-(v)$ are the outdegree…