Alon–Yuster conjecture on orientations avoiding directed triangles

About 6 years old · traced to

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 K3↻K^\circlearrowright_3 denote the strongly connected orientation of a triangle. Alon–Yuster's conjecture. For n≥1n\geq 1,

D(n,K3↻)=max⁡{2⌊n2/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 2⌊n2/4⌋2^{\lfloor n^2/4\rfloor}, so the claim is solved.

References

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.