James B. Shearer - itosg abstract

IBM - Personal communication

This web page contains the abstract of my paper:

"Some Intersection Theorems for Ordered Sets and Graphs" with F.R.K. Chung, P. Frankl and R.L. Graham, Journal of Combinatorial Theory Series A, 43(1986), p. 23-37.

Abstract: A classic topic in combinatorics is the study of problems of the following type: What are the maximum families F of subsets of a finite set with the property that the intersection of any two sets in the family satisfies some specified condition?

Typical restrictions on the intersections f intersect f' of any f and f' in F are:

f intersect f' is not empty, where all f contained in F have k elements (Erdos, Ko and Rado (1961)).
|f intersect f'| >=j (Katona (1964)).

In this paper we consider the general following question: For a given family B of subsets of [n]={1,2,...,n}, what is the largest family F of subsets of [n] satisfying

f,f' contained in F implies b contained in f intersect f' for some b contained in B.

Of particular interest are those B for which the maximum families consist of so-called "kernel systems," i.e., the family of all supersets of some fixed set in B. For example, we show that the set of all (cyclic) translates of a block of consecutive integers in [n] is such a family. It turns out rather unexpectedly that many of the results we obtain here depend strongly on properties of the well-known entropy function (from information theory).