Counting H-free orientations of graphs

DOI10.1017/S0305004122000147zbMath1504.05138arXiv2106.08845OpenAlexW3172915168MaRDI QIDQ5058452

Oliver Janzer, Matija Bucić, Benjamin Sudakov

Publication date: 20 December 2022

Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

Abstract: In 1974, ErdH{o}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 ErdH{o}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'ujo, Botler and Mota.

Full work available at URL: https://arxiv.org/abs/2106.08845

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The number of \(C_{2\ell}\)-free graphs
• Shattering, graph orientations, and connectivity
• On the number of orientations of random graphs with no directed cycles of a given length
• The number of \(K_{m,m}\)-free graphs
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• On the number of graphs without 4-cycles
• The number of graphs without forbidden subgraphs
• Cycles of even length in graphs
• A remark on the number of edge colorings of graphs
• The number of oriantations having no fixed tournament
• The maximum number of K ₃ -free and K ₄ -free edge 4-colorings
• On maximal paths and circuits of graphs
• On Colourings of Hypergraphs Without Monochromatic Fano Planes
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• Counting restricted orientations of random graphs
• Supersaturated Sparse Graphs and Hypergraphs
• The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques
• The number of K _s,t -free graphs
• The History of Degenerate (Bipartite) Extremal Graph Problems

Related Items (2)

Counting orientations of graphs with no strongly connected tournaments ⋮ Counting orientations of random graphs with no directed k‐cycles

This page was built for publication: Counting H-free orientations of graphs