We introduce an algebraic concept of the frame for abstract conditional independence (CI) models, together with basic operations with respect to which such a frame should be closed: copying and marginalization. Three standard examples of such frames are (discrete) probabilistic CI structures, semi-graphoids and structural semi-graphoids. We concentrate on those frames which are closed under the operation of set-theoretical intersection because, for these, the respective families of CI models are lattices. This allows one to apply the results from lattice theory and formal concept analysis to describe such families in terms of implications among CI statements. The central concept of this paper is that of self-adhesivity defined in algebraic terms, which is a combinatorial reflection of the self-adhesivity concept studied earlier in context of polymatroids and information theory. The generalization also leads to a self-adhesivity operator defined on the meta-level of CI frames. We answer some of the questions related to this approach and raise other open questions. The core of the paper is in computations. The combinatorial approach to computation might overcome some memory and space limitation of software packages based on polyhedral geometry, in particular, if SAT solvers are utilized. We characterize some basic CI families over 4 variables in terms of canonical implications among CI statements. We apply our method in information-theoretical context to the task of entropic region demarcation over 5 variables.

The paper deals with conditional linear information inequalities valid for entropy functions induced by discrete random variables. Specifically, the so-called conditional Ingleton inequalities are in the center of interest: these are valid under conditional independence assumptions on the inducing random variables. We discuss five inequalities of this particular type, four of which has appeared earlier in the literature. Besides the proof of the new fifth inequality, simpler proofs of (some of) former inequalities are presented. These five information inequalities are used to characterize all conditional independence structures induced by four discrete random variables.

This paper deals with chain graph models under alternative AMP interpretation. A new representative of an AMP Markov equivalence class, called the largest deflagged graph, is proposed. The representative is based on revealed internal structure of the AMP Markov equivalence class. More specifically, the AMP Markov equivalence class decomposes into finer strong equivalence classes and there exists a distinguished strong equivalence class among those forming the AMP Markov equivalence class. The largest deflagged graph is the largest chain graph in that distinguished strong equivalence class. A composed graphical procedure to get the largest deflagged graph on the basis of any AMP Markov equivalent chain graph is presented. In general, the largest deflagged graph differs from the AMP essential graph, which is another representative of the AMP Markov equivalence class.

One of the most common ways of representing classes of equivalent Bayesian networks is the use of essential graphs which are also known in the literature as completed patterns or completed pdags. The name essential graph was proposed by Andersson, Madigan and Perlman who also gave a graphical characterization of essential graphs. In this paper an alternative characterization of essential graphs is presented. The main observation is that every essential graph is the largest chain graph within a special class of chain graphs. More precisely, every equivalence class of Bayesian networks is contained in an equivalence class of chain graphs without flags (= certain induced subgraphs). A special operation of legal merging of (connectivity) components for a chain graph without flags is introduced. This operation leads to an algorithm for finding the essential graph on the basis of any graph in that equivalence class of chain graphs without flags which contains the equivalence class of a Bayesian network. In particular, the algorithm may start with any Bayesian network.

Irrelevance relations are sets of statements of the form: given that the ‘value’ of Z is known, the ‘values’ of Y can add no further information about the ‘values’ of X. Undirected Graphs (UGs), Directed Acyclic Graphs (DAGs) and Chain Graphs (CGs) were used and investigated as schemes for the purpose of representing irrelevance relations. It is known that, although all three schemes can approximate irrelevance, they are inadequate in the sense that there are relations which cannot be fully represented by anyone of them. In this paper annotated graphs are defined and suggested as a new model for graphical representation. It is shown that this new model is a proper generalization of the former models: any irrelevance relation that can be represented by either one of the previous models can also be represented by an annotated graph, and there are relations that can be represented by an annotated graph but cannot be represented by either one of the former models. The question of whether this new model is powerful enough to represent all the irrelevance relations, as well as some other related questions, is still open.