Quasi-random oriented graphs
From MaRDI portal
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
Recommendations
Cites work
- Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
- scientific article; zbMATH DE number 4099367 (Why is no real title available?)
- Quasi-random graphs
- Quasi-Random Set Systems
- Quasi-random tournaments
- Quasi-randomness and the distribution of copies of a fixed graph
- Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
- Quasi-randomness of graph balanced cut properties
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- Quasi‐random classes of hypergraphs
- Subgraphs of weakly quasi-random oriented graphs
- The quasi-randomness of hypergraph cut properties
Cited in
(16)- Interlacing families and the Hermitian spectral norm of digraphs
- On the maximum density of fixed strongly connected subtournaments
- Tournament quasirandomness from local counting
- On the largest eigenvalue of a mixed graph with partial orientation
- Cut distance identifying graphon parameters over weak* limits
- Graphs with many strong orientations
- Subgraphs of weakly quasi-random oriented graphs
- 4-cycles in mixing digraphs
- Forcing quasirandomness with triangles
- On the density of transitive tournaments
- Quasi-random graphs
- Quasirandom-Forcing Orientations of Cycles
- Extremal results on feedback arc sets in digraphs
- Quasi-random Boolean functions
- A note on directed analogues of the Sidorenko and forcing conjectures
- Forcing quasirandomness in a regular tournament
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)
