  Directed acyclic graphical models, or DAG models, are widely used to
represent complex causal systems. Since the basic task of learning such a model
from data is NP-hard, a standard approach is greedy search over the space of
directed acyclic graphs or Markov equivalence classes of directed acyclic
graphs. As the space of directed acyclic graphs on $p$ nodes and the associated
space of Markov equivalence classes are both much larger than the space of
permutations, it is desirable to consider permutation-based greedy searches.
Here, we provide the first consistency guarantees, both uniform and
high-dimensional, of a greedy permutation-based search. This search corresponds
to a simplex-like algorithm operating over the edge-graph of a sub-polytope of
the permutohedron, called a DAG associahedron. Every vertex in this polytope is
associated with a directed acyclic graph, and hence with a collection of
permutations that are consistent with the directed acyclic graph ordering. A
walk is performed on the edges of the polytope maximizing the sparsity of the
associated directed acyclic graphs. We show via simulated and real data that
this permutation search is competitive with current approaches.
