Alon–Yuster conjecture on orientations avoiding directed triangles
Alon–Yuster conjecture on orientations avoiding directed triangles
Given a graph and an oriented graph , let be the number of orientations of containing no copy of , and define
Let denote the strongly connected orientation of a triangle. Alon–Yuster's conjecture. For ,
The conjecture was posed by Alon and Yuster after they established the corresponding extremal behavior for sufficiently large and computed the values for small . The paper confirms the conjecture and further shows that the balanced complete bipartite graph is the unique -vertex extremal graph when the value is , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.