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.

The 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 Γ4. In Part I, we formulated the problem, enumerated all 59 types of 2-dimensional faces of Γ4by an algorithm, and fully characterized entropy functions on 49 types of them. In this paper, i.e., Part II, we will characterize entropy functions on the remaining 10 types of faces, among which 8 types are fully characterized, and 2 types are partially characterized. To characterize these types of faces, we introduce some new combinatorial design structures that are interesting in themselves.

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.

Matroidal entropy functions are entropy functions in the form h = logv·rM, wherev≥ 2 is an integer and rMis the rank function of a matroidM. They can be applied into capacity chracterization 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 matroidU2,4.

In this paper, we classify all G-symmetric almost entropic regions according to their Shannon-tightness, that is, whether they can be fully characterized by Shannon-type inequalities, where$G$is a permutation group of degree 6 or 7.

In this paper, we characterize entropy functions on the 2-dimensional faces of the polymatroidal region Γ4. We enumerate all 59 types of 2-dimensional faces of Γ4and fully characterized entropy functions on 27 types of them, among which 4 types are non-trivial.

In this paper, we study the zero-error capacity of binary channels with two memories. Among all 11 categories of "one-edge" channels, we solve 10 of them and give a lower and an upper bound on the capacity of the remaining one.

In this paper, we characterize matroidal entropy functions, i.e., entropy functions in the form h = log v • r, where v ≥ 2 is an integer and r is the rank function of a matroid M. By constructing the variable strength arrays of some matroid operations, we characterized matroidal entropy functions induced by regular matroids and some matroids with the same p-characteristic set as uniform matroid U2,4.

Let Xi, i E 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 E V' as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When G is a path so that Xi, i E V form a Markov chain, it is known that the I-Measure is always nonnegative (Kawabata and Yeung in 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. in 2002).

Let N = (1,..., n). The entropy function h of a set of n discrete random variables (Xi: i ∈ N ) is a 2n-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 = (N1,..., Nt) 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∩Ni| = |B∩Ni|, 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.

We prove that by imposing a conditional mutual independence constraint and a marginalisation constraint, the almost entropic region can be completely characterised by Shannon-type information inequalities. Such a property is applied to obtain an explicit lower bound on the generalised Wyner common information.

Consider the entropy function region for discrete random variables Xi, i ϵ N and partition N into N1and N2with 0 ≤ |N1| ≤ |N2|. An entropy function h is called (N1, N2)-symmetrical if for all A, B ⊂ N, h(A) = h(B) whenever |A ∩ N1| = |B ∩N1|, i = 1,2. We prove that for |N1| = 0 or 1, the closure of the (N1, N2)-symmetrical entropy function region is completely characterized by Shannon-type information inequalities. Applications of this work include threshold secret sharing and distributed data storage, where symmetry exists in the structure of the problem.

Contrary to the traditional method of information inequalities, in this paper, the entropy function region Γn* and its closure ̅Γn* are characterized via extreme rays of its outer bound polymatroidal region Γn. The characterization of Γ3* and the tightness of Γnas an outer bound on ̅Γn* are studied.