Subgraphs of weakly quasi-random oriented graphs

DOI10.1137/100794419MaRDI QIDQ3094909zbMATH OpenOpenAlexFDO

Authors Omid Amini, Simon Griffiths, Florian Huc

Publication date 27 October 2011

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

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

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)

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.

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

Cited in

(5)

• Weakly saturated subgraphs of random graphs
• 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

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)