We investigate the effect of the well-known Mycielski construction on the Shannon capacity of graphs and on one of its most prominent upper bounds, the (complementary) Lovász theta number. We prove that if the Shannon capacity of a graph, the distinguishability graph of a noisy channel, is attained by some finite power, then its Mycielskian has strictly larger Shannon capacity than the graph itself. For the complementary Lovász theta function we show that its value on the Mycielskian of a graph is completely determined by its value on the original graph, a phenomenon similar to the one discovered for the fractional chromatic number by Larsen, Propp and Ullman. We also consider the possibility of generalizing our results on the Sperner capacity of directed graphs and on the generalized Mycielsky construction. Possible connections with what Zuiddam calls the asymptotic spectrum of graphs are discussed as well.

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.

We investigate a communication setup where a source output is sent through a free noisy channel first and an additional codeword is sent through a noiseless, but expensive channel later. With the help of the second message the decoder should be able to decide with zero-error whether its decoding of the first message was error-free. This scenario leads to the definition of a digraph parameter that generalizes Witsenhausen's zero-error rate for directed graphs. We investigate this new parameter for some specific directed graphs and explore its relations to other digraph parameters, such as Sperner capacity and dichromatic number. We also look at the natural variant of the above problem, where the decoder should decode the first message with zero-error, not only decide whether its earlier decoding was correct. In this case, the Witsenhausen rate of an appropriately defined undirected graph turns out to be the relevant parameter.

We investigate a communication setup where a source output is sent through a free noisy channel first and an additional codeword is sent through a noiseless but expensive channel later. With the help of the second message the decoder should be able to decide with zero-error whether its decoding of the first message was error-free. This scenario leads to the definition of a digraph parameter that generalizesWitsenhausen's zero-error rate for directed graphs. We investigate this new parameter for some specific directed graphs and explore its relations to other digraph parameters like Sperner capacity and dichromatic number. When the original problem is modified to require zero-error decoding of the complete message then we arrive back to the Witsenhausen rate of an appropriately defined undirected graph.

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.

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 investigate the problem of minimum rate zero-error source coding when there are several decoding terminals having different side information about the central source variable and each of them should decode in an error-free manner. For one decoder this problem was considered by Witsenhausen. The Witsenhausen rate of the investigated multiple source is the asymptotically achievable minimum rate. We prove that the Witsenhausen rate of a multiple source equals the Witsenhausen rate of its weakest element. The proof relies on a powerful result of Gargano, Korner, and Vaccaro about the zero-error capacity of the compound channel.

Arbitrarily varying channels have been introduced as a model for transmission in cases of jamming. It is shown that this theory applies naturally to memories and yields, in a unified way, some new and old capacity theorems for write-unidirectional memories with side information. The role of cycles via outputwise varying channels is discussed. Exact conditions for memories to have positive capacity in the long run are derived.>

Write-unidirectional memories generalize write-once memories storing binary sequences of some fixed length in a reusable manner. At every new usage the content of the memory can be rewritten by either changing some of the zeroes to ones or changing some of the ones to zeroes, but not both. The author constructs codes of rate 0.5325. He discusses the four cases that arise according to whether or not the encoder and/or the decoder is informed of the previous state of the memory. J.M. Borden's converse bound (submitted to IEEE Trans. Inf. Theory) is rederived using Fibonacci sequences.>

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.