In this paper, we study the entropy functions on extreme rays of the polymatroidal region which contain a matroid, i.e., matroidal entropy functions. We introduce variable strength orthogonal arrays indexed by a connected matroid M and positive integer v which can be regarded as expanding the classic combinatorial structure orthogonal arrays. It is interesting that they are equivalent to the partition-representations of the matroid M with degree v and the $(M,v)$ almost affine codes. Thus, a synergy among four fields, i.e., information theory, matroid theory, combinatorial design, and coding theory is developed, which may lead to potential applications in information problems such as network coding and secret-sharing. Leveraging the construction of variable strength orthogonal arrays, we characterize all matroidal entropy functions of order $n\le 5$ with the exception of $log10·U_{2,5}$ and $logv·U_{3,5}$ for some v.

Let Xi, i ∈ V form a Markov random field (MRF) represented by an undirected graph G = (V, E), and V’ be a subset of V. We determine the smallest graph that can always represent the subfield Xi, i ∈ V’ as an MRF. Based on this result, we obtain a necessary and suffcient condition for a subfield of a Markov tree to be also a Markov tree. When G is a path so that Xi, i ∈ V form a Markov chain, it is known that the I-Measure is always nonnegative (Kawabata and Yeung, 1992). We prove that Markov chain is essentially the only MRF such that the I-Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al., 2002).

Let N = (1,..., n). The entropy function h of a set of n discrete random variables (X _i : i ∈ N ) is a 2 ⁿ -dimensional vector whose entries are h(A) △ H(X ), A c N, the (joint) entropies of the subsets of the set of n random variables with H(X _Ø ) = 0 by convention. The set of all entropy functions for n discrete random variables, denoted by Γ _n *, is called the entropy region for n. Characterization of Γ _n * and its closure Γ _n * are well-known open problems in information theory. They are important not only because they play key roles in information theory problems but also they are related to other subjects in mathematics and physics. In this paper, we consider partitionsymmetrical entropy functions. Let p = (N ₁ ,..., N _t ) be a t-partition of N. An entropy function his called p-symmetrical if for all A, B ⊂ N, h(A) = h(B) whenever |A∩N _i | = |B∩N _i |, i = 1,..., t. The set of all the p-symmetrical entropy functions, denoted by ψ _p *, is called p-symmetrical entropy function region. We prove that ψ _p *, the closure of ψ _p *, is completely characterized by Shannon-type information inequalities if and only if p is the 1-partition or a 2-partition with one of its blocks being a singleton. The characterization of the partition-symmetrical entropy functions can be useful for solving some information theory and related problems where symmetry exists in the structure of the problems.

Matroidal entropy functions are entropy functions in the form $\mathbf {h}=\log v \cdot \mathbf {r} _{M}$ , where $v\ge 2$ is an integer and $\mathbf {r}_{M}$ is the rank function of a matroid M. They can be applied into capacity characterization and code construction of information theory problems such as network coding, secret sharing, index coding and locally repairable code. In this paper, by constructing the variable strength orthogonal arrays of some matroid operations, we characterize matroidal entropy functions induced by regular matroids and some matroids with the same p-characteristic set as uniform matroid $U_{2,4}$ .

Characterization of entropy functions is of fundamental importance in information theory. By imposing constraints on their Shannon outer bound, i.e., the polymatroidal region, one obtains the faces of the region and entropy functions on them with special structures. In this series of two papers, we characterize entropy functions on the 2-dimensional faces of the polymatroidal region of degree 4. In Part I, we formulate the problem, enumerate all 59 types of 2-dimensional faces of the region by an algorithm, and fully characterize entropy functions on 49 types of them. The entropy functions on the remaining 10 types of faces will be characterized in Part II, among which 8 types are fully characterized, and 2 types are partially characterized.

In this paper, we study the zero-error capacity of channels with memory, which are represented by graphs. We provide a method to construct code for any graph with one edge, thereby determining a lower bound on its zero-error capacity. Moreover, this code can achieve zero-error capacity when the symbols in a vertex with degree one are the same. We further apply our method to the one-edge graphs representing the binary channels with two memories. There are 28 possible graphs, which can be organized into 11 categories based on their symmetries. The code constructed by our method is proved to achieve the zero-error capacity for all these graphs except for the two graphs in Case 11.