Back to Search
Start Over
Uniform s-Cross-Intersecting Families
- Source :
- Combinatorics, Probability and Computing. 26:517-524
- Publication Year :
- 2017
- Publisher :
- Cambridge University Press (CUP), 2017.
-
Abstract
- In this paper we study a question related to the classical Erd\H{o}s-Ko-Rado theorem, which states that any family of $k$-element subsets of the set $[n] = \{1,\ldots,n\}$ in which any two sets intersect, has cardinality at most ${n-1\choose k-1}$. We say that two non-empty families are $\mathcal A, \mathcal B\subset {[n]\choose k}$ are {\it $s$-cross-intersecting}, if for any $A\in\mathcal A,B\in \mathcal B$ we have $|A\cap B|\ge s$. In this paper we determine the maximum of $|\mathcal A|+|\mathcal B|$ for all $n$. This generalizes a result of Hilton and Milner, who determined the maximum of $|\mathcal A|+|\mathcal B|$ for nonempty $1$-cross-intersecting families.<br />Comment: This article was previously a portion of arXiv:1603.00938v1, which has been split
- Subjects :
- FOS: Computer and information sciences
Statistics and Probability
Discrete Mathematics (cs.DM)
Applied Mathematics
The Intersect
010102 general mathematics
0102 computer and information sciences
01 natural sciences
Theoretical Computer Science
Combinatorics
Set (abstract data type)
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Computational Theory and Mathematics
010201 computation theory & mathematics
FOS: Mathematics
ComputingMethodologies_DOCUMENTANDTEXTPROCESSING
Mathematics - Combinatorics
Cardinality (SQL statements)
Combinatorics (math.CO)
0101 mathematics
Element (category theory)
Computer Science - Discrete Mathematics
Mathematics
Subjects
Details
- ISSN :
- 14692163 and 09635483
- Volume :
- 26
- Database :
- OpenAIRE
- Journal :
- Combinatorics, Probability and Computing
- Accession number :
- edsair.doi.dedup.....3298a7efc10ce34204fa569117e0aed4