Disjoint pairs in set systems with restricted intersection

DOI10.1016/J.EJC.2019.102998MaRDI QIDQ2011127zbMATH OpenOpenAlexFDO

Authors António Girão, Richard Snyder

Publication date 28 November 2019

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

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)$.

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

Cites work

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

Cited in

(4)

• Set systems with few disjoint pairs
• Atoms of set systems with a fixed number of pairwise unions
• The minimum number of disjoint pairs in set systems and related problems
• 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)