Uniformly cross intersecting families

DOI10.1007/S00493-009-2332-6zbMATH Open1212.05260arXivmath/0608173OpenAlexW2003965933MaRDI QIDQ987560FDOQ987560

Authors: Noga Alon, Eyal Lubetzky 

Publication date: 13 August 2010

Published in: Combinatorica (Search for Journal in Brave)

Abstract: Let $mathcalA$ and $matchcalB$ denote two families of subsets of an $n$-element set. The pair $(mathcalA,mathcalB)$ is said to be $ell$-cross-intersecting iff $|AcapB|=ell$ for all $AinmathcalA$ and $BinmathcalB$. Denote by $P_{e}ll(n)$ the maximum value of $|mathcalA||mathcalB|$ over all such pairs. The best known upper bound on $P_{e}ll(n)$ is $Theta(2^n)$, by Frankl and R"{o}dl. For a lower bound, Ahlswede, Cai and Zhang showed, for all $ngeq2ell$, a simple construction of an $ell$-cross-intersecting pair $(mathcalA,mathcalB)$ with $$, and conjectured that this is best possible. Consequently, Sgall asked whether or not $P_{e}ll(n)$ decreases with $ell$. In this paper, we confirm the above conjecture of Ahlswede et al. for any sufficiently large $ell$, implying a positive answer to the above question of Sgall as well. By analyzing the linear spaces of the characteristic vectors of $mathcalA,mathcalB$ over $mathbbR$, we show that there exists some $el{l}_0>0$, such that $$ for all $ellgeqel{l}_0$. Furthermore, we determine the precise structure of all the pairs of families which attain this maximum.

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

Recommendations

• Exact bounds on cross-intersecting families
• Counting intersecting and pairs of cross-intersecting families
• On a restricted cross-intersection problem
• On cross-intersecting families of sets
• Sharp results concerning disjoint cross-intersecting families

zbMATH Keywords

intersecting families

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Forbidden Intersections
• Forbidding just one intersection
• Intersection theorems with geometric consequences
• A Remark on Stirling's Formula
• Intersection theorems for systems of finite sets
• Title not available (Why is that?)
• On a lemma of Littlewood and Offord
• On t-designs
• A short proof of Sperner's lemma
• Title not available (Why is that?)
• On a restricted cross-intersection problem
• A general 4-words inequality with consequences for 2-way communication complexity
• Bounds on pairs of families with restricted intersections

Cited In (21)

• How different can two intersecting families be?
• On sizes of 1-cross intersecting set pair systems
• How different can two intersecting families be?
• Nearly optimal NP-hardness of vertex cover on \(k\)-uniform \(k\)-partite hypergraphs
• Problems and results on 1-cross-intersecting set pair systems
• Cross-intersecting families of labeled sets
• Regular intersecting families
• Cross-intersecting families and primitivity of symmetric systems
• A bound for 1-cross intersecting set pair systems
• On cross-intersecting families of set partitions
• Uniform s-Cross-Intersecting Families
• Title not available (Why is that?)
• Fractional cross intersecting families
• Disjoint pairs in set systems with restricted intersection
• Circulant almost cross intersecting families
• Cross‐intersecting couples of graphs
• Octopuses in the Boolean cube: families with pairwise small intersections. II
• On a restricted cross-intersection problem
• Diversity of uniform intersecting families
• Exact bounds on cross-intersecting families
• Maximal fractional cross-intersecting families

This page was built for publication: Uniformly cross intersecting families

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