Intersecting families of sets and permutations: a survey

Abstract

A family $\mathcal{A}$ of sets is said to be \emph{$t$-intersecting} if any two sets in $\mathcal{A}$ have at least $t$ common elements. A central problem in extremal set theory is to determine the size or structure of a largest $t$-intersecting sub-family of a given family $\mathcal{F}$. We give a survey of known results, conjectures and open problems for various important families $\mathcal{F}$, namely, power sets, levels of power sets, hereditary families, families of signed sets, families of labeled sets, and families of permutations. We also provide some extensions and consequences of known results.

21 pages

Cited by in corpus (10)

• Cross-intersecting integer sequences
• On the Hilton-Spencer intersection theorems for unions of cycles
• Minimum saturated families of sets
• New bounds on even cycle creating Hamiltonian paths using expander graphs
• Intersecting integer partitions
• The maximum sum and maximum product of sizes of cross-intersecting families
• Star-specific Key-homomorphic PRFs from Learning with Linear Regression
• What is the minimal cardinal of a family which shatters all d-subsets of a finite set?
• On the largest subsets avoiding the diameter of $(0,\pm 1)$-vectors
• The maximum product of sizes of cross-$t$-intersecting uniform families