TY - JOUR

T1 - Disjoint representability of sets and their complements

AU - Balogh, József

AU - Keevash, Peter

AU - Sudakov, Benny

N1 - Funding Information:
E-mail addresses: [email protected] (J. Balogh), [email protected] (P. Keevash), [email protected] (B. Sudakov). 1Research supported in part by NSF Grant DMS-0302804. Part of this research was done while visiting the Institute for Advanced Study at Princeton. 2 Research supported in part by NSF Grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship.

PY - 2005/9

Y1 - 2005/9

N2 - 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 Ck = {∅, {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 rk-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 rk-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.

AB - 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 Ck = {∅, {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 rk-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 rk-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.

KW - Extremal problems

KW - Set systems

KW - Trace

UR - http://www.scopus.com/inward/record.url?scp=23244457607&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23244457607&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2005.02.005

DO - 10.1016/j.jctb.2005.02.005

M3 - Article

AN - SCOPUS:23244457607

SN - 0095-8956

VL - 95

SP - 12

EP - 28

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -