Disjoint pairs in set systems with restricted intersection

DOI10.1016/J.EJC.2019.102998zbMATH Open1428.05304arXiv1706.06994OpenAlexW2968695731MaRDI QIDQ2011127FDOQ2011127

António Girão, Richard Snyder

Publication date: 28 November 2019

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The problem of bounding the size of a set system under various intersection restrictions has a central place in extremal combinatorics. We investigate the maximum number of disjoint pairs a set system can have in this setting. In particular, we show that for any pair of set systems $(mathcalA,mathcalB)$ which avoid a cross-intersection of size $t$, the number of disjoint pairs $(A,B)$ with $AinmathcalA$ and $BinmathcalB$ is at most $$. This implies an asymptotically best possible upper bound on the number of disjoint pairs in a single $t$-avoiding family $mathcalFsubsetmathcalP[n]$. We also study this problem when $mathcalA$, $mathcalBsubset[n{]}^{(r)}$ are both $r$-uniform, and show that it is closely related to the problem of determining the maximum of the product $|mathcalA||mathcalB|$ when $mathcalA$ and $mathcalB$ avoid a cross-intersection of size $t$, and $nge{n}_0(r,t)$.

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

Recommendations

• Sharp results concerning disjoint cross-intersecting families
• On families of weakly cross-intersecting set-pairs
• On two set-systems with restricted cross-intersections
• On a restricted cross-intersection problem
• A bound for 1-cross intersecting set pair systems

zbMATH Keywords

\(t\)-cross-avoiding set systemsmaximum number of disjoint pairs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Forbidden Intersections
• Forbidding just one intersection
• The complete intersection theorem for systems of finite sets
• Intersection theorems for systems of finite sets
• Title not available (Why is that?)
• A short proof that the extension complexity of the correlation polytope grows exponentially
• On hypergraphs without two edges intersecting in a given number of vertices
• The minimum number of disjoint pairs in set systems and related problems
• On the densities of cliques and independent sets in graphs
• Two-colorings with many monochromatic cliques in both colors
• The maximum number of disjoint pairs in a family of subsets
• Simple hypergraphs with maximal number of adjacent pairs of edges
• On the minimum number of disjoint pairs in a family of finite sets
• Set systems with few disjoint pairs
• Title not available (Why is that?)
• Invitation to intersection problems for finite sets
• On a restricted cross-intersection problem
• Bounds on pairs of families with restricted intersections
• Uniformly cross intersecting families

Cited In (3)

• Set systems with few disjoint pairs
• Atoms of set systems with a fixed number of pairwise unions
• Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations

This page was built for publication: Disjoint pairs in set systems with restricted intersection

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