Quasi-random oriented graphs
From MaRDI portal
Publication:2853337
DOI10.1002/JGT.21701zbMATH Open1273.05203arXiv1101.5421OpenAlexW1893778160MaRDI QIDQ2853337FDOQ2853337
Authors: Simon Griffiths 
Publication date: 21 October 2013
Published in: Journal of Graph Theory (Search for Journal in Brave)
Abstract: We show that a number of conditions on oriented graphs, all of which are satisfied with high probability by randomly oriented graphs, are equivalent. These equivalences are similar to those given by Chung, Graham and Wilson in the case of unoriented graphs, and by Chung and Graham in the case of tournaments. Indeed, our main theorem extends to the case of a general underlying graph G the main result of Chung and Graham which corresponds to the case that G is complete. One interesting aspect of these results is that exactly two of the four orientations of a four-cycle can be used for a quasi-randomness condition, i.e., if the number of appearances they make in D is close to the expected number in a random orientation of the same underlying graph, then the same is true for every small oriented graph H
Full work available at URL: https://arxiv.org/abs/1101.5421
Recommendations
Cites Work
- Quasi-random graphs
- Title not available (Why is that?)
- Quasi-randomness and the distribution of copies of a fixed graph
- Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
- Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- Quasi‐random classes of hypergraphs
- Quasi-Random Set Systems
- The quasi-randomness of hypergraph cut properties
- Quasi-random tournaments
- Quasi-randomness of graph balanced cut properties
- Subgraphs of weakly quasi-random oriented graphs
Cited In (14)
- On the maximum density of fixed strongly connected subtournaments
- Quasi-random Boolean functions
- Cut distance identifying graphon parameters over weak* limits
- Quasirandom-Forcing Orientations of Cycles
- 4-cycles in mixing digraphs
- Tournament quasirandomness from local counting
- On the largest eigenvalue of a mixed graph with partial orientation
- Quasi-random graphs
- Graphs with many strong orientations
- Subgraphs of weakly quasi-random oriented graphs
- Forcing quasirandomness with triangles
- Extremal results on feedback arc sets in digraphs
- On the density of transitive tournaments
- Interlacing families and the Hermitian spectral norm of digraphs
This page was built for publication: Quasi-random oriented graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2853337)
