On the union of intersecting families

DOI10.1017/S096354831900004XzbMATH Open1436.05108arXiv1610.03027MaRDI QIDQ5222559FDOQ5222559

Authors: David Ellis, Noam Lifshitz 

Publication date: 6 April 2020

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: A family of sets is said to be emph{intersecting} if any two sets in the family have nonempty intersection. In 1973, ErdH{o}s raised the problem of determining the maximum possible size of a union of $r$ different intersecting families of $k$-element subsets of an $n$-element set, for each triple of integers $(n,k,r)$. We make progress on this problem, proving that for any fixed integer $rgeq2$ and for any $kleq(frac12-o(1))n$, if $X$ is an $n$-element set, and $mathcalF=mathcal{F}_{1}cupmathcal{F}_{2}cupldotscupmathcal{F}_r$, where each $mathcal{F}_i$ is an intersecting family of $k$-element subsets of $X$, then $|mathcalF|leqnchoosek-n-rchoosek$, with equality only if $mathcalF=SsubsetX:|S|=k,ScapReqemptyset$ for some $RsubsetX$ with $|R|=r$. This is best possible up to the size of the $o(1)$ term, and improves a 1987 result of Frankl and F"uredi, who obtained the same conclusion under the stronger hypothesis $k<(3-sqrt5)n/2$, in the case $r=2$. Our proof utilises an isoperimetric, influence-based method recently developed by Keller and the authors.

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

Recommendations

• The maximum size of intersecting and union families of sets
• Multiply intersecting families of sets
• Intersecting families in \(\begin{pmatrix}[m]\\ \ell\end{pmatrix}\cup\begin{pmatrix}[n]\\ k\end{pmatrix}\)
• Some results on intersecting families of subsets
• Size and structure of large \((s,t)\)-union intersecting families

zbMATH Keywords

influence-based method

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• Contributions to the geometry of Hamming spaces
• Title not available (Why is that?)
• Correlation inequalities on some partially ordered sets
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Thresholds and Expectation Thresholds
• The size of a hypergraph and its matching number
• Title not available (Why is that?)
• Extremal problems concerning Kneser-graphs
• Improved bounds for Erdős' matching conjecture
• Families of Non-disjoint subsets
• An approximate zero-one law
• Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
• On a biased edge isoperimetric inequality for the discrete cube

Cited In (29)

• Intersecting families with minimum volume
• Enumeration of intersecting families
• Compressions and probably intersecting families
• Title not available (Why is that?)
• Intersecting families in a subset of Boolean lattices
• Intersecting families of sets are typically trivial
• Intersecting families in \(\begin{pmatrix}[m]\\ \ell\end{pmatrix}\cup\begin{pmatrix}[n]\\ k\end{pmatrix}\)
• Size and structure of large \((s,t)\)-union intersecting families
• Intersecting Families are Essentially Contained in Juntas
• Multiply union families in \(\mathbb{N}^n\)
• Title not available (Why is that?)
• Sharp bounds for the chromatic number of random Kneser graphs
• On the size of maximal intersecting families
• The structure of large intersecting families
• Title not available (Why is that?)
• Brace-Daykin type inequalities for intersecting families
• On the arithmetic mean of the size of cross-union families
• Trivial colors in colorings of Kneser graphs
• Stabilities for non-uniform \(t\)-intersecting families
• Chain intersecting families
• Intersecting families in symmetric unions of direct products of set families
• Maximum degree and diversity in intersecting hypergraphs
• On shadows of intersecting families
• The random walk method for intersecting families
• The unbalance of set systems
• Union-intersecting set systems
• Some exact results for multiply intersecting families
• Diversity of uniform intersecting families
• Non-trivially intersecting multi-part families

This page was built for publication: On the union of intersecting families

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