TY - JOUR

T1 - Counting H-free orientations of graphs

AU - Bucic, Matija

AU - Janzer, Oliver

AU - Sudakov, Benny

N1 - Funding Information:
Research supported in part by SNSF grant 200021_196965.
Funding Information:
Research supported by an ETH Zürich Postdoctoral Fellowship 20-1 FEL-35.
Publisher Copyright:
© The Author(s), 2022. Published by Cambridge University Press on behalf of Cambridge Philosophical Society.

PY - 2023/1/25

Y1 - 2023/1/25

N2 - In 1974, ErdÅ's posed the following problem. Given an oriented graph H, determine or estimate the maximum possible number of H-free orientations of an n-vertex graph. When H is a tournament, the answer was determined precisely for sufficiently large n by Alon and Yuster. In general, when the underlying undirected graph of H contains a cycle, one can obtain accurate bounds by combining an observation of Kozma and Moran with celebrated results on the number of F-free graphs. As the main contribution of the paper, we resolve all remaining cases in an asymptotic sense, thereby giving a rather complete answer to ErdÅ's's question. Moreover, we determine the answer exactly when H is an odd cycle and n is sufficiently large, answering a question of Araújo, Botler and Mota.

AB - In 1974, ErdÅ's posed the following problem. Given an oriented graph H, determine or estimate the maximum possible number of H-free orientations of an n-vertex graph. When H is a tournament, the answer was determined precisely for sufficiently large n by Alon and Yuster. In general, when the underlying undirected graph of H contains a cycle, one can obtain accurate bounds by combining an observation of Kozma and Moran with celebrated results on the number of F-free graphs. As the main contribution of the paper, we resolve all remaining cases in an asymptotic sense, thereby giving a rather complete answer to ErdÅ's's question. Moreover, we determine the answer exactly when H is an odd cycle and n is sufficiently large, answering a question of Araújo, Botler and Mota.

UR - http://www.scopus.com/inward/record.url?scp=85129687803&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85129687803&partnerID=8YFLogxK

U2 - 10.1017/S0305004122000147

DO - 10.1017/S0305004122000147

M3 - Article

AN - SCOPUS:85129687803

SN - 0305-0041

VL - 174

SP - 79

EP - 95

JO - Mathematical Proceedings of the Cambridge Philosophical Society

JF - Mathematical Proceedings of the Cambridge Philosophical Society

IS - 1

ER -