Counting H-free orientations of graphs
OPEN ACCESS
Loading...
Author / Producer
Date
2023-01
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
In 1974, Erdos 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 Erdos’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.
Permanent link
Publication status
published
External links
Editor
Book title
Volume
174 (1)
Pages / Article No.
79 - 95
Publisher
Cambridge University Press
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Notes
Funding
196965 - Problems in Extremal and Probabilistic Combinatorics (SNF)
20-1 FEL-35 - Problems in Extremal Combinatorics (ETHZ)
20-1 FEL-35 - Problems in Extremal Combinatorics (ETHZ)