Appears in collection : 2016 - T1 - WS1 - Distributed computation and communication theme

In a suitable reformulation, standard problems in Erdösian extremal combinatorics, especially intersection theorems, are in a surprisingly close connection with zero-error problems in the Shannon theory of information. Combinatorialists are, however, mostly interested in problems where the conjectured solution has a beautiful and simple structure (mostly kernel structures), and thus they seem to ignore the problems closest to information theory. Our aim is to introduce a wealth of new problems where the objects playing the role of codewords are not appropriately different strings from some finite alphabet. Rather, they are permutations or even Hamilton paths in large complete graphs. We discuss some results in an attempt to understand why and when standard information-theoretic methods (greedy algorithms, random choice) fail to yield a solution.