Abstract. We investigate the maximum size of graph families on a common vertex set of cardinality [Formula: see text] such that the symmetric difference of the edge sets of any two members of the family satisfies some prescribed condition. We solve the problem completely for infinitely many values of [Formula: see text] when the prescribed condition is connectivity or 2-connectivity, Hamiltonicity, or the containment of a spanning star. We also investigate local conditions that can be certified by looking at only a subset of the vertex set. In these cases a capacity-type asymptotic invariant is defined and when the condition is to contain a certain subgraph this invariant is shown to be a simple function of the chromatic number of this required subgraph. This is proven using classical results from extremal graph theory. Several variants are considered and the paper ends with a collection of open problems.

There are few mathematicians whose contributions go beyond named conjectures and theorems: Vladimir Iosifovich Levenshtein (, 1935–2017) is one such true exception. During the five decades of his active research career, he enriched combinatorics, coding, and information theory with elegant problem formulations, ingenious algorithmic solutions, and highly original proof techniques. However, his work accomplished much more—it paved the way for the creation and advancement of new scientific disciplines, such as natural language processing, metagenomics, sequence alignment, and reference-based genome assembly, as well as DNA-based data storage, to name a few. A crucial concept behind sequence alignment algorithms used in phylogeny, comparative, and cancer genomics, as well as in natural language processing is the Levenshtein (edit) distance and its extension, termed the Damerau–Levenshtein distance between strings. The Levenshtein distance equals the smallest number of insertions, deletions, or substitutions required to convert one string into another. Levenshtein introduced this metric in 1965 [item 1) in the Appendix], followed by the notion of deletion and insertion error-correcting codes that have since been used in a myriad of systems presented with synchronization errors [items 1) and 2) in the Appendix]. Levenshtein’s work also inspired the introduction of the trace reconstruction problem [items 3) and 4) in the Appendix] which has since sparked substantial interest in the field of DNA-based data storage.

A structured code that improves the previously best known exponential asymptotic lower bound for the maximum cardinality of a pairwise-colliding set of permutations is presented. The main contribution is an explicit construction of an infinite recursion of pairwise-colliding sets of partial-permutations.

We consider graphs whose vertex set is the set of permutations of the first $n$ natural numbers. Two such sequences are adjacent if for two different natural numbers they and their images in the two permutations occupy four different positions in some specific order, implying that the permutations are different. Several such relations are investigated, and for two of them the precise asymptotic magnitude of the largest clique in the graph is determined.

We determine the asymptotics of the largest cardinality of a set of Hamilton paths in the complete graph with vertex set [n] under the condition that for any two of the paths in the family there is a subpath of length k entirely contained in only one of them and edge-disjoint from the other one.

We begin a systematic study of the problem of the zero-error capacity of noisy binary channels with memory and solve some of the non-trivial cases.

Let ${\cal G}$ be a family of $n$-vertex graphs of uniform degree 2 with the property that the union of any two member graphs has maximum degree 4. We determine the leading term in the asymptotics of the largest cardinality of such a family. Several analogous problems are discussed.

Let $\mathbb{D}\subseteq \mathbb{N}$ be an arbitrary subset of the natural numbers. For every n, let $M(n, \mathbb{D})$ be the maximum of the cardinality of a set of Hamiltonian paths in the complete graph $K_n$ such that the union of any two paths from the family contains a not necessarily induced cycle of some length from $\mathbb{D}$. We determine or bound the asymptotics of $M(n, \mathbb{D})$ in various special cases. This problem is closely related to that of the permutation capacity of graphs and constitutes a further extension of the problem area around Shannon capacity. We also discuss how to generalize our cycle-difference problems and present an example where cycles are replaced by 4-cliques. These problems are in a natural duality to those of graph intersection, initiated by Erdős, Simonovits, and Sós. The lack of kernel structure as a natural candidate for optimum makes our problems quite challenging.

We introduce a new class of problems lying halfway between questions about graph capacity and intersection. We say that two binary sequencesxandyof the same length have a skewincidence if there is a coordinateifor whichxi=yi+1=1 or vice versa. We give relatively close bounds on the maximum number of binary sequences of lengthnany pair of which has a skewincidence. A systematic study of these problems helps to understand the mathematical difficulties to solve zero-error problems in information theory.

Körner and Malvenuto asked whether one can find $\binom{n}{\lfloor n/2\rfloor}$ linear orderings (i.e., permutations) of the first n natural numbers such that any pair of them places two consecutive integers somewhere in the same position. This led to the notion of graph-different permutations. We extend this concept to directed graphs, focusing on orientations of the semi-infinite path whose edges connect consecutive natural numbers. Our main result shows that the maximum number of permutations satisfying all the pairwise conditions associated with all of the various orientations of this path is exponentially smaller, for any single orientation, than the maximum number of those permutations which satisfy the corresponding pairwise relationship. This is in sharp contrast to a result of Gargano, Körner, and Vaccaro concerning the analogous notion of Sperner capacity of families of finite graphs. We improve the exponential lower bound for the original problem and list a number of open questions.

For a finite graph G whose vertices are different natural numbers we call two infinite permutations of the natural numbers G-different if they have two adjacent vertices of G somewhere in the same position. The maximum number of pairwise G-different permutations of the naturals is always finite. We study this maximum as a graph invariant and relate it to a problem of the first two authors on colliding permutations. An improvement on the lower bound for the maximum number of pairwise colliding permutations is obtained.

We call two permutations of the first n naturals colliding if they map at least one number to consecutive naturals. We give bounds for the exponential asymptotics of the largest cardinality of any set of pairwise colliding permutations of [n]. We relate this problem to the determination of the Shannon capacity of an infinite graph and initiate the study of analogous problems for infinite graphs with finite chromatic number.

We determine the exact exponential asymptotics of the maximum number of n-length binary strings any two of which differ in the following strong sense: there must be a coordinate in which one of them has a 1 in correspondence with a predetermined position within a "long run" of zeros in the other string. We discuss some generalizations and implications of this result.

The Nesetril--Pultr dimension of the Kneser graph is interpreted as the shortest length of strings over an infinite alphabet representing the vertices of the graph so that the absence of coincidences in the codewords of a pair of vertices is equivalent to adjacency, i.e., to the two underlying sets being disjoint. We study analogous but more demanding representations in case the alphabet size may be limited and yet the full intersection has to be determined from the coincidences. Our results introduce a connectionbetween extremal set theory and zero-error problems in multiterminal source coding in the Shannon sense.

The problem of error-free transmission capacity of a noisy channel was posed by Shannon in 1956 and remains unsolved, Nevertheless, partial results for this and similar channel and source coding problems have had a considerable impact on information theory, computer science, and mathematics. We review the techniques, results, information measures, and challenges encountered in this ongoing quest.

In a frequent practical situation one possesses inconsistent fragmentary data concerning some industrial process or natural phenomenon. It is an interesting and reasonable task to assess what the most concise way to store or transmit them would be. The authors consider the zero-error case of the problem, i.e., we would like to save all the data incorporating them into the most concise but necessarily alternative consistent data structures. More precisely, we want to find a set of alternatives which requires the minimum total storage place. From the mathematical viewpoint the model is information-theoretic and gives a common framework to deal with many combinatorial problems in the theory of extremal hypergraphs. From the practical viewpoint the interest of the mathematical theory is to produce new information measures capturing the inconsistency in the data.>

The capacity of uniform hypergraphs can be defined as a natural generalization of the Shannon capacity of graphs. Corresponding to every uniform hypergraph there is a discrete memoryless channel in which the zero error capacity, in the case of the smallest list size for which it is positive, equals the capacity of the hypergraph, and vice versa. Also, the problem of perfect hashing can be considered as a hypergraph capacity problem. Upper bounds are derived for the capacity of uniform hypergraphs, using a technique developed earlier for perfect hashing based on the concepts of graph entropy and hypergraph entropy. These are subadditive functionals on probabilistic graphs and hypergraphs (i.e. graphs and hypergraphs within a probability distribution given on their vertex sets). A modified version of this technique is given, replacing graph entropy by another subadditive functional on probabilistic graphs. This functional can be considered as a probabilistic refinement of Lovasz's delta -functional.>

The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This concept is at the core of a new bounding technique for graph covering problems and has furnished the best known bounds for the problem of perfect hashing. The basis of the technique is the sub-additivity of graph entropy with respect to the union of graphs. The tightness of the bounds depends on whether or not we have equality rather than just sub-additivity. As a first step in this analysis, we are investigating whether for a given graph G the entropies of G and $\bar G$ add up to the entropy of the complete graph on the same vertex set, i.e., the entropy of the underlying probability distribution. We shall prove that for a bipartite graph G and an arbitrary probability distribution P on its vertex set the entropies of G and $\bar G$ add up to the entropy of P. Related problems will be discussed. The results have interesting connections with the Ford–Fulkerson theory of network flows.

The problem of perfect hashing is generalized and some initial results are obtained. As a corollary, an improvement on earlier results for $( i, j )$-separating systems of partitions is provided.

A probabilistic problem that arises for conflict resolution in random-access communication is treated. An earlier conjecture is disproved and a technique for finding lower bounds on the number of graphs of given structure needed to cover all edges of a given graph is developed.>

The problem of determining the achievable rate region for an arbitrary source network with one "helper" is still unsolved. Csiszár and the author have shown that it reduces to the one-parameter entropy characterization problem (OPEC), treated in their monograph on information theory. For a discrete memoryless multiple source, solving the OPEC problem means finding a computable characterization of the per-letter conditional entropies of the first n outputs of each of the component sources given an arbitrary function of the first n outputs of the first component source. For sources with three components, the OPEC problem has been solved by Csiszár, Körner, and Marton. However, their result has a very asymmetric form and has not been generalized. This paper gives a substantially simpler proof of the same result in a new symmetric form. Moreover, for sources with more than three components, a new increased region of simultaneously attainable conditional entropies is derived.

The encoding of a discrete memoryless multiple source\{( X_{i}, Y_{i})\}_{i=1}^{\infty}for reconstruction of a sequence\{Z_{i}\}_{i=1}^{\infty}}, withZ_{i} = F( X_{i}, Y_{i}); i = 1,2, \cdotsis considered. We require that the encoding should be such that\{X_{i}\}_{i=1}^{\infty}is encoded first without any consideration of\{Y_{i}\}_{i=1}^{\infty}, while in a second part of the encoding, this latter sequence is encoded based on knowledge of the outcome of the first encoding. The resulting scheme is called successive encoding. We find general outer and inner bounds for the corresponding set of achievable rates along with a complete single letter characterization for the special caseH( X_{i}|Z_{i}, Y_{i}) = 0. Comparisons with the Slepian-Wolf problem and the Ahlswede-Korner-Wyner side information problem are carried out.

Asymptotically coincident upper and lower bounds on the exponent of the largest possible probability of correct decoding for block codes of any given rate above capacity have been given by Dueck and Körner. Their method is extended to show that the same bounds also hold in the presence of noiseless feedback.

A new and simple method is proposed for finding good encoders both for channels and for sources with side information. This method relies on the continuous version of a graph decomposition result of Lovász. The presently known best exponential error bounds for both problems follow in a unified manner with an improvement on the source coding bound. The previous bounds for universal codes of the authors and Marton are also improved.

A unified approach to multiterminal source coding problems not involving rate-distortion theory is presented. It is shown that, for determining file achievable rate region, attention may be restricted to source networks of a relatively simple structure. A product space characterizafion of the achievable rate region pinpoints the mathematical problem to be solved for getting a single letter characterization. The complexity of this problem depends on a structural condition, viz., the number of encoders of a certain kind in the source network. This approach yields all the known single-letter characterizations of achievable rate regions and a number of new ones for more complex networks. As a digression, for a class of source networks including that of Slepian and Wolf, exponential error bounds are derived which are attainable by universal codes. These bounds are tight in a neighborhood of the boundary of the achievable rate region.

Universally attainable error exponents for broadcast channels with degraded message sets are obtained using a technique which generalizes that introduced by Csiszár, Körner, and Martron for the ordinary channel. Lower and upper bounds to the error probabilities over a single broadcast channel are also given.

Asymptotically coincident upper and lower bounds on the exponent of the largest possible probability of the correct decoding of block codes are given for all rates above capacity. The lower bound sharpens Omura's bound. The upper bound is proved by a new and simple combinatorial argument.

How much separate information about two random binary sequences is needed in order to tell with small probability of error in which positions the two sequences differ? If the sequences are the outputs of two correlated memoryless binary sources, then in some cases the rate of this information may be substantially less than the joint entropy of the two sources. This result is implied by the solution of the source coding problem with two separately encoded side information sources for a special class of source distributions.

Given two discrete memoryless channels (DMC's) with a common input, it is desired to transmit private messages to receiver1rateR_{1}and common messages to both receivers at rateR_{o}, while keeping receiver2as ignorant of the private messages as possible. Measuring ignorance by equivocation, a single-letter characterization is given of the achievable triples(R_{1},R_{e},R_{o})whereR_{e}is the equivocation rate. Based on this channel coding result, the related source-channel matching problem is also settled. These results generalize those of Wyner on the wiretap channel and of Körner-Marton on the broadcast Channel.

A broadcast channel with one sender and two receivers is considered. Three independent messages are to be transmitted over this channel: one common message which is meant for both receivers, and one private message for each of them. The coding theorem and strong converse for this communication situation is proved for the case when one of the private messages has rate zero.

A technique is presented to determine the region of achievable rates for some source and channel networks. This technique is applied to the solution of a source:network problem that seems to be the simplest illustration of a new typical difficulty in coding for source networks: namely, when the same encoding of a source is required to meet the conflicting demands of 1) supplying side-information to the decoder of another source, and 2) providing direct-information to its own decoder in company with other side-information.

Let\{(X_i, Y_i,)\}_{i=1}^{\infty}be a memoryless correlated source with finite alphabets, and let us imagine that one person, encoder 1, observes onlyX^n = X_1,\cdots,X_nand another person, encoder 2, observes onlyY^n = Y_1,\cdots,Y_n. The encoders can produce encoding functionsf_n(X^n)andg_n(Y^n)respectively, which are made available to the decoder. We determine the rate region in case the decoder is interested only in knowingY^n = Y_1,\cdots,Y_n(with small error probability). In Section H of the paper we give a characterization of the capacity region for degraded broadcast channels (DBC's), which was conjectured by Bergmans [11] and is somewhat sharper than the one obtained by Gallager [12].

Any finite information source is given a graph structure, in which two vertices are adjacent whenever the two corresponding source letters are distinguishable by the coder-decoder pair. Usual sources correspond, therefore, to complete graphs. If the associated graph is not complete, however, an\varepsilon-code for the source can be constructed in two steps: in the first, distinct codewords are given to distinguishable letters only; in the second step, a similar encoding is carried out for the complementary graph, in which distinguishable letters become indistinguishable and the converse. A particularly simple case shows up when nonadjacency is an equivalence relation among the vertices of the graph: each class of nondistinguishable letters can then be considered as a letter in a coarser source alphabet. The two-step procedure is then particularly intuitive. A problem arises when this procedure does not destroy optimality of the resulting\varepsilon-code; some partial results are given in this direction. The results obtained are largely based on some graph-theoretical ideas and tools.