Acyclic orientations of random graphs

DOI10.1006/AAMA.1998.0595zbMath0916.05062OpenAlexW2092274915MaRDI QIDQ1271856

Christian M. Reidys

Publication date: 11 November 1998

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/aama.1998.0595

zbMATH Keywords

number of acyclic orientationsBernoulli subgraph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30)

Related Items (20)

Discrete dynamical systems on graphs and Boolean functions ⋮ An atlas of limit set dynamics for asynchronous elementary cellular automata ⋮ Attractor stability in finite asynchronous biological system models ⋮ Connectivity of old and new models of friends-and-strangers graphs ⋮ On enumeration of conjugacy classes of Coxeter elements ⋮ Agent-Based Modeling, Mathematical Formalism for ⋮ Combinatorics of sequential dynamical systems ⋮ Neutrality in fitness landscapes. ⋮ Matrix method for linear sequential dynamical systems on digraphs ⋮ Sequential dynamical systems over words ⋮ On certain morphisms of sequential dynamical systems ⋮ REDUCTION OF DISCRETE DYNAMICAL SYSTEMS OVER GRAPHS ⋮ Update schedules of sequential dynamical systems ⋮ Asynchronous, finite dynamical systems ⋮ Lipschitz continuity under toric equivalence for asynchronous Boolean networks ⋮ On the diameters of friends-and-strangers graphs ⋮ Elements of a theory of simulation. II: Sequential dynamical systems. ⋮ ACYCLIC ORIENTATIONS ON THE SIERPINSKI GASKET ⋮ Elements of a theory of simulation. III: Equivalence of SDS. ⋮ ETS IV: Sequential dynamical systems: fixed points, invertibility and equivalence

Cites Work

• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• Largest random component of a k-cube
• Elements of a theory of computer simulation. I
• Weighted sums of certain dependent random variables
• Combinatorial problems of commutation and rearrangements
• Acyclic orientations of graphs
• Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph
• The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
• Information Bounds Are Weak in the Shortest Distance Problem
• Optimal Randomized Algorithms for Local Sorting and Set-Maxima

This page was built for publication: Acyclic orientations of random graphs