Comparable pairs in families of sets

Noga Alon, Shagnik Das, Roman Glebov, Benny Sudakov

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

Given a family F of subsets of [n], we say two sets A,B∈F are comparable if A⊂. B or B⊂. A. Sperner's celebrated theorem gives the size of the largest family without any comparable pairs. This result was later generalised by Kleitman, who gave the minimum number of comparable pairs appearing in families of a given size.In this paper we study a complementary problem posed by Erdos, Daykin and Frankl in the early '80s. They asked for the maximum number of comparable pairs that can appear in a family of m subsets of [n], a quantity we denote by c(n, m). We first resolve an old conjecture of Alon and Frankl, showing that c(n, m)=o(m2) when m=nω(1)2n/2. We also obtain more accurate bounds for c(n, m) for sparse and dense families, characterise the extremal constructions for certain values of m, and sharpen some other known results.

Original languageEnglish (US)
Pages (from-to)164-185
Number of pages22
JournalJournal of Combinatorial Theory. Series B
Volume115
DOIs
StatePublished - Nov 1 2015

All Science Journal Classification (ASJC) codes

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

Keywords

  • Alon-Frankl conjecture
  • Comparable pairs
  • Extremal set theory
  • Tower of cubes

Fingerprint Dive into the research topics of 'Comparable pairs in families of sets'. Together they form a unique fingerprint.

  • Cite this