The matching-orientation conjecture for directed graphs

Let HH be a graph and let H\vec{H} be a directed graph with underlying graph HH. For a graph or directed graph, let M\mathcal{M} denote the family of maximal matchings, and let M(H)\overrightarrow{\mathcal{M}(H)} be the corresponding family of directed matchings. The matching-orientation conjecture. If

M(H)=M(H),\mathcal{M}(\vec{H})=\overrightarrow{\mathcal{M}(H)},

then, for large enough nn,

D(n,H)=2ex(n,H).D(n,\vec{H})=2^{\mathrm{ex}(n,H)}.

This conjecture seeks a general criterion ensuring that the orientation-counting extremal function agrees with the ordinary extremal-number bound; the paper presents it as a difficult conjectural extension of its exact results for particular orientations, and its resolution remains open.

Sources & referencesView supporting material

Primary source

Hannah Sheats, “Orientations of graphs omitting non-edge-critical directed graphs”, arXiv:2502.21287 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.