Alon–Yuster conjecture on orientations avoiding directed triangles

Given a graph GG and an oriented graph H\vec H, let D(G,H)D(G,\vec H) be the number of orientations of GG containing no copy of H\vec H, and define

D(n,H)=max{D(G,H):G is an n-vertex graph}.D(n,\vec H)=\max\{D(G,\vec H):G\text{ is an }n\text{-vertex graph}\}.

Let K3K^\circlearrowright_3 denote the strongly connected orientation of a triangle. Alon–Yuster's conjecture. For n1n\geq 1,

D(n,K3)=max{2n2/4,n!}.D(n,K^\circlearrowright_3)=\max\{2^{\lfloor n^2/4\rfloor},n!\}.

The conjecture was posed by Alon and Yuster after they established the corresponding extremal behavior for sufficiently large nn and computed the values for small nn. The paper confirms the conjecture and further shows that the balanced complete bipartite graph is the unique nn-vertex extremal graph when the value is 2n2/42^{\lfloor n^2/4\rfloor}, so the claim is solved.

Sources & referencesView supporting material

Primary source

Pedro Araújo, Fábio Botler and Guilherme Oliveira Mota, “Counting graph orientations with no directed triangles”, arXiv:2005.13091 (2020).

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.