Comparable pairs in families of sets

DOI10.1016/J.JCTB.2015.05.009zbMATH Open1319.05130arXiv1411.4196OpenAlexW1779152938MaRDI QIDQ490990FDOQ490990

Authors: Noga Alon, Shagnik Das, Roman Glebov, Benny Sudakov 

Publication date: 21 August 2015

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: Given a family $mathcalF$ of subsets of $[n]$, we say two sets $A,BinmathcalF$ are comparable if $AsubsetB$ or $BsubsetA$. 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 ErdH{o}s and 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(m^2)$ when $m=n^{omega(1)}{2}^{n/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.

Full work available at URL: https://arxiv.org/abs/1411.4196

Recommendations

• Several families with incomparability and complementarity conditions
• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• scientific article; zbMATH DE number 2230929
• scientific article; zbMATH DE number 4075073
• Kleitman's conjecture about families of given size minimizing the number of \(k\)-chains

zbMATH Keywords

extremal set theoryAlon-Frankl conjecturecomparable pairstower of cubes

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• On a hypergraph Turán problem of Frankl
• On extremal problems of graphs and generalized graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a lemma of Littlewood and Offord
• Graph removal lemmas
• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• Title not available (Why is that?)
• The maximum number of disjoint pairs in a family of subsets
• On Kruskal's cascades and counting containments in a set of subsets
• Title not available (Why is that?)
• Supersaturation in the Boolean lattice
• Generating all subsets of a finite set with disjoint unions

Cited In (6)

• Several families with incomparability and complementarity conditions
• Kleitman's conjecture about families of given size minimizing the number of \(k\)-chains
• Comparing families of thin sets.
• Some properties of similar pairs
• Families in posets minimizing the number of comparable pairs
• Fitting sets pairs

This page was built for publication: Comparable pairs in families of sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490990)