论文标题
计算图方向，没有定向三角形
Counting graph orientations with no directed triangles
论文作者
论文摘要
Alon和Yuster证明了任何$ n $ vertex图的方向数量，其中每个$ k_3 $是传输的，最多是$ 2^{\ lfloor n^2/4 \ rfloor} $ for $ n \ geQ 10^4 $，并认为$ n $ $ n $ $ n $ n $ n $ n $ \ 8 $ 8 $ \ 8 $。我们确认了他们的猜想，此外，通过证明具有$ n $ vertices的平衡完整二分图是唯一的$ n $ vertex图，以$ 2^{\ lfloor n^2/4 \ rfloor} $。
Alon and Yuster proved that the number of orientations of any $n$-vertex graph in which every $K_3$ is transitively oriented is at most $2^{\lfloor n^2/4\rfloor}$ for $n \geq 10^4$ and conjectured that the precise lower bound on $n$ should be $n \geq 8$. We confirm their conjecture and, additionally, characterize the extremal families by showing that the balanced complete bipartite graph with $n$ vertices is the only $n$-vertex graph for which there are exactly $2^{\lfloor n^2/4\rfloor}$ such orientations.
