Counting intersecting and pairs of cross-intersecting families

DOI10.1017/S0963548317000529MaRDI QIDQ4601052zbMATH OpenOpenAlexFDO

Authors Peter Frankl, Andrey B. Kupavskii

Publication date 19 January 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

intersecting families of subsets

Mathematics Subject Classification ID

Extremal set theory (05D05)

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 ErdH{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 $nge2k+2+2sqrtklogk$ and $koinfty$. 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.

Recommendations

• Intersections and distinct intersections in cross-intersecting families
• Sharp results concerning disjoint cross-intersecting families
• Exact bounds on cross-intersecting families
• On the maximum number of distinct intersections in an intersecting family
• On cross-intersecting families

Cites work

• Erdős-Ko-Rado theorem with conditions on the maximal degree
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3370377 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• Intersecting families of discrete structures are typically trivial
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On generalized graphs
• Solution of a problem of A. Ehrenfeucht and J. Mycielski
• Some best possible inequalities concerning cross-intersecting families
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS

Cited in

(24)

• On the structure of large sum-free sets of integers
• Diversity of uniform intersecting families
• Regular bipartite graphs and intersecting families
• On hypergraphs without loose cycles
• Coloring cross-intersecting families
• Counting families of mutually intersecting sets
• A generalization of the Bollobás set pairs inequality
• On the maximum number of distinct intersections in an intersecting family
• A generalization of Kneser graphs
• Intersecting families of discrete structures are typically trivial
• On the independence numbers of some distance graphs with vertices in \(\{-1, 0, 1\}^n\)
• Degree versions of theorems on intersecting families via stability
• On the number of maximal intersecting \(k\)-uniform families and further applications of Tuza's set pair method
• Structure and supersaturation for intersecting families
• Almost intersecting families
• Circulant almost cross intersecting families
• Cross-Intersecting Families of Partial Permutations
• Diversity
• Intersecting families of sets are typically trivial
• On the intersecting family process
• \(K_r\)-saturated graphs and the two families theorem
• The number of colorings of the middle layers of the Hamming cube
• Enumeration of intersecting families
• Uniformly cross intersecting families

This page was built for publication: Counting intersecting and pairs of cross-intersecting families

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