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.

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.

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.

We prove that no nonregular deterministic context-free language is accepted by any systolic Y-tree automaton while some of them, but not all, can be accepted by nondeterministic systolic Y-tree automata. We show that weak superstable systolic automata over incomplete Y-tree can accept only regular languages. We also show that the weak superstability and the superstability problems are decidable for deterministic systolic automata over a sparse and superprefix Y-tree. Moreover we prove that the regularity problem is decidable for systolic binary tree automata.