English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

DAG models are statistical models satisfying a collection of conditionalindependence relations encoded by the nonedges of a directed acyclic graph(DAG) $\mathcal{G}$. Such models are used to model complex cause-effect systemsacross a variety of research fields. From observational data alone, a DAG model$\mathcal{G}$ is only recoverable up to Markov equivalence. Combinatorially,two DAGs are Markov equivalent if and only if they have the same underlyingundirected graph (i.e. skeleton) and the same set of the induced subDAGs $i\toj \leftarrow k$, known as immoralities. Hence it is of interest to study thenumber and size of Markov equivalence classes (MECs). In a recent paper, theauthors introduced a pair of generating functions that enumerate the number ofMECs on a fixed skeleton by number of immoralities and by class size, and theystudied the complexity of computing these functions. In this paper, we lay thefoundation for studying these generating functions by analyzing their structurefor trees and other closely related graphs. We describe these polynomials forsome important families of graphs including paths, stars, cycles, spidergraphs, caterpillars, and complete binary trees. In doing so, we recoverimportant connections to independence polynomials, and extend some classicalidentities that hold for Fibonacci numbers. We also provide tight lower andupper bounds for the number and size of MECs on any tree. Finally, we usecomputational methods to show that the number and distribution of high degreenodes in a triangle-free graph dictates the number and size of MECs.

Counting Markov Equivalence Classes for DAG models on Trees