Quasirandom-Forcing Orientations of Cycles

DOI10.1137/23M1548700MaRDI QIDQ6071821zbMATH OpenFDO

Authors A. Grzesik, Bartłomiej Kielak, Daniel Král'

Publication date 29 November 2023

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

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

zbMATH Keywords

directed cyclequasirandomnesstournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

Abstract: An oriented graph $H$ is quasirandom-forcing if the limit (homomorphism) density of $H$ in a sequence of tournaments is $2^{-|H|}$ if and only if the sequence is quasirandom. We study generalizations of the following result: the cyclic orientation of a cycle of length $ell$ is quasirandom-forcing if and only if $ellequiv2$ mod $4$. We show that no orientation of an odd cycle is quasirandom-forcing. In the case of even cycles, we find sufficient conditions on an orientation to be quasirandom-forcing, which we complement by identifying necessary conditions. Using our general results and spectral techniques used to obtain them, we classify which orientations of cycles of length up to $10$ are quasirandom-forcing.

Recommendations

• Orientations making \(k\)-cycles cyclic
• Cyclical orientations of graphs
• Quasi-random oriented graphs
• Orienting cycle elements in orientable rotation systems
• Quantitative nonorientability of embedded cycles
• Cycle reversals in oriented plane quadrangulations and orthogonal plane partitions
• Acyclic orientations on the Sierpinski gasket
• Arbitrary orientations of Hamilton cycles in oriented graphs

Cites work

• An approximate version of Sidorenko's conjecture
• Bipartite subgraphs and quasi-randomness
• Characterization of quasirandom permutations by a pattern sum
• Cycles of a given length in tournaments
• Cycles of length three and four in tournaments
• Decomposition of tournament limits
• Forcing quasirandomness with triangles
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 4099367 (Why is no real title available?)
• scientific article; zbMATH DE number 3194324 (Why is no real title available?)
• scientific article; zbMATH DE number 3102313 (Why is no real title available?)
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Hypergraphs, quasi-randomness, and conditions for regularity
• Impartial digraphs
• Large networks and graph limits
• Lower bound on the size of a quasirandom forcing set of permutations
• Natural quasirandomness properties
• No additional tournaments are quasirandom-forcing
• On the density of transitive tournaments
• On the maximum density of fixed strongly connected subtournaments
• ON THE METHOD OF PAIRED COMPARISONS
• On the number of 5-cycles in a tournament
• On universality of graphs with uniformly distributed edges
• Partial associativity and rough approximate groups
• Pseudo-random hypergraphs
• Quasi-random graphs
• Quasi-random hypergraphs
• Quasi-Random Set Systems
• Quasi-random subsets of \(\mathbb{Z}_ n\)
• Quasi-random tournaments
• Quasirandom Groups
• Quasirandom Latin squares
• Quasirandom permutations
• Quasirandom permutations are characterized by 4-point densities
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Regularity Lemma for k-uniform hypergraphs
• The counting lemma for regular k‐uniform hypergraphs
• The Maximum Number of Strongly Connected Subtournaments^*
• Tournament quasirandomness from local counting
• Transversals in quasirandom latin squares
• Weak quasi-randomness for uniform hypergraphs

Cited in

(3)

• Series-parallel orientations preserving the cycle-radius
• Forcing generalised quasirandom graphs efficiently
• Forcing quasirandomness in a regular tournament

This page was built for publication: Quasirandom-Forcing Orientations of Cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6071821)