Disjoint representability of sets and their complements

For a hypergraph H and a set S, the trace of H on S is the set of all intersections of edges of H with S. We will consider forbidden trace problems, in which we want to find the largest hypergraph H that does not contain some list of forbidden configurations as traces, possibly with some restriction on the number of vertices or the size of the edges in H . In this paper we will focus on combinations of three forbidden configurations: the k-singleton [ k ] ( 1 ) , the k-co-singleton [ k ] ( k - 1 ) and the k-chain C k = { ∅ , { 1 } , [ 1 , 2 ] , … , [ 1 , k - 1 ] } , where we write [ k ] ( ℓ ) for the set of all ℓ -subsets of [ k ] = { 1 , … , k } . Our main topic is hypergraphs with no k-singleton or k-co-singleton trace. We obtain an exact result in the case k = 3 , both for uniform and non-uniform hypergraphs, and classify the extremal examples. In the general case, we show that the number of edges in the largest r-uniform hypergraph with no k-singleton or k-co-singleton trace is of order r k - 2 . By contrast, Frankl and Pach showed that the number of edges in the largest r-uniform hypergraph with no k-singleton trace is of order r k - 1 . We also give a very short proof of the recent result of Balogh and Bollobás that there is a finite bound on the number of sets in any hypergraph without a k-singleton, k-co-singleton or k-chain trace, independently of the number of vertices or the size of the edges.