Disjoint representability of sets and their complements

József Balogh, Peter Keevash, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)12-28
Number of pages17
JournalJournal of Combinatorial Theory. Series B
Volume95
Issue number1
DOIs
StatePublished - Sep 2005
Externally publishedYes

Keywords

  • Extremal problems
  • Set systems
  • Trace

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Disjoint representability of sets and their complements'. Together they form a unique fingerprint.

Cite this