Intersection problems and graph capacity

Autorizzazione CdF di Scienze Matematiche,Fisiche e Naturali del 16 novembre 2009

We introduce a new class of problems lying halfway between questions about graph capacity and intersection. We say that two binary sequences x and y of the same length have a skewincidence if there is a coordinate i for which xi = yi+1 = 1 or vice versa. We give relatively close bounds on the maximum number of binary sequences of length n any 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.