Counting H-free orientations of graphs

DOI10.1017/S0305004122000147MaRDI QIDQ5058452zbMATH OpenOpenAlexFDO

Authors Matija Bucić, Oliver Janzer, Benny Sudakov

Publication date 20 December 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

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.

Recommendations

• A note on counting orientations
• On the number of orientations of random graphs with no directed cycles of a given length
• Counting restricted orientations of random graphs
• The number of oriantations having no fixed tournament
• Counting orientations of graphs with no strongly connected tournaments

Cites work

• A remark on the number of edge colorings of graphs
• Counting restricted orientations of random graphs
• Cycles of even length in graphs
• scientific article; zbMATH DE number 3487496 (Why is no real title available?)
• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• scientific article; zbMATH DE number 2053394 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 881297 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• On colourings of hypergraphs without monochromatic Fano planes
• On maximal paths and circuits of graphs
• On the number of graphs without 4-cycles
• On the number of orientations of random graphs with no directed cycles of a given length
• Shattering, graph orientations, and connectivity
• Supersaturated sparse graphs and hypergraphs
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The Erdős–Rothschild problem on edge-colourings with forbidden monochromatic cliques
• The history of degenerate (bipartite) extremal graph problems
• The maximum number of \(K_{3}\)-free and \(K_{4}\)-free edge 4-colorings
• The number of \(C_{2\ell}\)-free graphs
• The number of \(K_{m,m}\)-free graphs
• The number of \(K_{s,t}\)-free graphs
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• The number of graphs without forbidden subgraphs
• The number of oriantations having no fixed tournament

Cited in

(10)

• Counting \(H\)-free graphs
• The number of oriantations having no fixed tournament
• Counting orientations of graphs with no strongly connected tournaments
• A note on counting orientations
• Subgraphs of weakly quasi-random oriented graphs
• On the number of orientations of random graphs with no directed cycles of a given length
• Counting restricted orientations of random graphs
• Counting orientations of random graphs with no directed k‐cycles
• Turán problems for oriented graphs
• Forbidden tournaments and the orientation completion problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5058452)