Subgraphs of weakly quasi-random oriented graphs

DOI10.1137/100794419zbMATH Open1228.05261arXiv0911.3969OpenAlexW2046691122MaRDI QIDQ3094909FDOQ3094909

Authors: Omid Amini, Simon Griffiths, Florian Huc 

Publication date: 27 October 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: It is an intriguing question to see what kind of information on the structure of an oriented graph $D$ one can obtain if $D$ does not contain a fixed oriented graph $H$ as a subgraph. The related question in the unoriented case has been an active area of research, and is relatively well-understood in the theory of quasi-random graphs and extremal combinatorics. In this paper, we consider the simplest cases of such a general question for oriented graphs, and provide some results on the global behavior of the orientation of $D$. For the case that $H$ is an oriented four-cycle we prove: in every $H$-free oriented graph $D$, there is a pair $A,BssqV(D)$ such that $e(A,B)gee(D{)}^2/32|D{|}^2$ and $e(B,A)lee(A,B)/2$. We give a random construction which shows that this bound on $e(A,B)$ is best possible (up to the constant). In addition, we prove a similar result for the case $H$ is an oriented six-cycle, and a more precise result in the case $D$ is dense and $H$ is arbitrary. We also consider the related extremal question in which no condition is put on the oriented graph $D$, and provide an answer that is best possible up to a multiplicative constant. Finally, we raise a number of related questions and conjectures.

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

Recommendations

• Quasi-random oriented graphs
• On the number of orientations of random graphs with no directed cycles of a given length
• A note on counting orientations
• Counting H-free orientations of graphs
• Counting restricted orientations of random graphs

zbMATH Keywords

forbidden subgraphoriented graphsquasi-randomness

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Cited In (5)

• A density result for random sparse oriented graphs and its relation to a conjecture of Woodall
• Quasi-random oriented graphs
• A note on counting orientations
• Extremal results on feedback arc sets in digraphs
• Weakly saturated subgraphs of random graphs

This page was built for publication: Subgraphs of weakly quasi-random oriented graphs

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