2025/02/28 by Sheats, Hannah
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2502.21287
In 1974, Erdős asked the following question: given a graph G and a directed graph H, how many ways are there to orient the edges of G such that it does not contain H as a subgraph? We denote this value by D(G, H). Further, we let D(n, H) denote the maximum of D(G, H) over all graphs G on n vertices. In 2006, Alon and Yuster gave an exact answer when H is a tournament. In 2023, Bucić, Janzer, and Sudakov gave asymptotic answers for all directed graphs H, and in the same paper, they gave an exact answer when H is a directed cycle. In this paper, we give a better bound for some specific non-bipartite directed graphs. Further, we obtain exact values of D(G, H) for some small non-edge-critical directed graphs H. Finally, for these graphs, we classify all graphs G that attain the bound D(G, H) = D(n, H).