Acyclic orientations of random graphs
From MaRDI portal
A Bernoulli subgraph of an undirected graph is a random subgraph obtained by independently keeping edges with a common probability. The distribution of the number of acyclic orientations is studied for a Bernoulli subgraph of a complete graph of order \(n\) and for a Bernoulli subgraph of an \(n\)-cube.
Recommendations
Cites work
- Acyclic orientations of graphs
- Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph
- Combinatorial problems of commutation and rearrangements
- Elements of a theory of computer simulation. I
- Information Bounds Are Weak in the Shortest Distance Problem
- Largest random component of a k-cube
- Optimal Randomized Algorithms for Local Sorting and Set-Maxima
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
- Weighted sums of certain dependent random variables
Cited in
(27)- Elements of a theory of simulation. II: Sequential dynamical systems.
- Matrix method for linear sequential dynamical systems on digraphs
- Sinks in acyclic orientations of graphs
- Elements of a theory of simulation. III: Equivalence of SDS.
- ETS IV: Sequential dynamical systems: fixed points, invertibility and equivalence
- Discrete dynamical systems on graphs and Boolean functions
- Attractor stability in finite asynchronous biological system models
- Combinatorics of sequential dynamical systems
- On certain morphisms of sequential dynamical systems
- Update schedules of sequential dynamical systems
- Acyclic orientations on the Sierpinski gasket
- On enumeration of conjugacy classes of Coxeter elements
- An atlas of limit set dynamics for asynchronous elementary cellular automata
- REDUCTION OF DISCRETE DYNAMICAL SYSTEMS OVER GRAPHS
- The acyclic orientation game on random graphs
- Counting restricted orientations of random graphs
- Agent-based modeling, mathematical formalism for
- Orientability Thresholds for Random Hypergraphs
- A new approach to the orientation of random hypergraphs
- Sequential dynamical systems over words
- Neutrality in fitness landscapes.
- Connectivity of old and new models of friends-and-strangers graphs
- Asynchronous, finite dynamical systems
- Lipschitz continuity under toric equivalence for asynchronous Boolean networks
- On the diameters of friends-and-strangers graphs
- The distribution of the length of the longest path in random acyclic orientations of a complete bipartite graph
- Period-3 orbits of sequential dynamical systems and their relationship to error-correcting codes over finite fields
This page was built for publication: Acyclic orientations of random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1271856)
