Quasi-random oriented graphs
From MaRDI portal
Publication:2853337
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
- scientific article; zbMATH DE number 4099367 (Why is no real title available?)
- Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
- Quasi-Random Set Systems
- Quasi-random graphs
- 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
(14)- On the density of transitive tournaments
- 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
- 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)
