Mathematics – Combinatorics
Scientific paper
2009-11-20
Mathematics
Combinatorics
35 pages
Scientific paper
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,B\ssq V(D)$ such that $e(A,B)\ge e(D)^{2}/32|D|^{2}$ and $e(B,A)\le e(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.
Amini Omid
Griffiths Simon
Huc Florian
No associations
LandOfFree
Subgraphs of weakly quasi-random oriented graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Subgraphs of weakly quasi-random oriented graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subgraphs of weakly quasi-random oriented graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-431926