pith. machine review for the scientific record. sign in

arxiv: 1701.04110 · v2 · pith:DZAP55CEnew · submitted 2017-01-15 · 🧮 math.CO · cs.DM

Counting intersecting and pairs of cross-intersecting families

classification 🧮 math.CO cs.DM
keywords intersectingfamiliesldotssubsetsasymptoticallycross-intersectingdeterminefamily
0
0 comments X
read the original abstract

A family of subsets of $\{1,\ldots,n\}$ is called {\it intersecting} if any two of its sets intersect. A classical result in extremal combinatorics due to Erd\H{o}s, Ko, and Rado determines the maximum size of an intersecting family of $k$-subsets of $\{1,\ldots, n\}$. In this paper we study the following problem: how many intersecting families of $k$-subsets of $\{1,\ldots, n\}$ are there? Improving a result of Balogh, Das, Delcourt, Liu, and Sharifzadeh, we determine this quantity asymptotically for $n\ge 2k+2+2\sqrt{k\log k}$ and $k\to \infty$. Moreover, under the same assumptions we also determine asymptotically the number of {\it non-trivial} intersecting families, that is, intersecting families for which the intersection of all sets is empty. We obtain analogous results for pairs of cross-intersecting families.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.