Intersecting family

A family of sets is intersecting when every two of its members have nonempty intersection.

This is a property of a set family, distinct from extremal theorems bounding its size.

For intersecting families of subsets of $[n]$, take each upward closure of a set family. It remains intersecting and contains at most one set in each complementary pair, so its complement as a family has density at least one half. Those complements are decreasing set families. Repeated Harris-Kleitman inequality gives intersection density at least $2^{-k}$, proving the displayed bound. For $k\le n$, the families of sets containing coordinate $i$, for $1\le i\le k$, attain equality.

On five points, the four sets $12,13,14,15$ are an intersecting family. The first four two-element sets in colexicographic order are $12,13,23,14$, containing the disjoint pair $23,14$. Thus replacing a family by an equally large colexicographic initial segment can destroy intersection, even though it minimizes the lower shadow.

For $1\le r\le n/2$, the Erdős-Ko-Rado theorem bounds an intersecting family by the displayed size. The first that many rank-$r$ sets in lexicographic order all contain coordinate one. Therefore the lexicographic initial segment of the same size as any intersecting family is also intersecting. This statement concerns ordinary one-element intersection and does not extend to higher intersection requirements.

A maximal intersecting family is an up-set. It cannot contain both a set and its complement. If neither were present, maximality would supply a member disjoint from the first set, and upward closure would then include its complement. Thus precisely one member of each complementary pair occurs, so the family has $2^{n-1}$ members for $n\ge 1$.

A set family is t-intersecting if every pair of its members has at least $t$ common elements. For $r$-sets on an $n$-point ground set, the whole level is t-intersecting when $n\le 2r-t$. Ordinary intersecting families are the case $t=1$.

On eight points, the rank-four Frankl family consisting of sets containing at least three of $1,2,3,4$ has seventeen members and is two-intersecting. The first fifteen rank-four sets in lexicographic order contain $1,2$, while the sixteenth is $1345$. The earlier set $1278$ meets it only at one. This disproves preservation of two-intersection by lexicographic replacement even when the rank is half the ground-set size.

For two-intersecting families on four points, all supersets of a fixed pair form a maximal family of size four: any set missing part of that pair fails its intersection test with the pair itself. The maximum instead has size five, attained by all sets of size at least three. Thus maximality and maximum cardinality diverge for intersection parameter two.

If $|A\cap B|\ge t$, then $|A△B|=|A\cup B|-|A\cap B|\le n-t$. The Kleitman diametric theorem therefore gives the sharp nonuniform intersection bound. For $n-t=2q$, all sets of size at least $n-q$ attain it. For $n-t=2q+1$, take all sets of size at least $n-q$, together with all $(n-q-1)$-sets avoiding one fixed point.

The maximum size of a t-intersecting family of $r$-sets on $[n]$ is the largest complete-intersection candidate family. In strict nontrivial intervals $n_{k+1}<n<n_k$, the maximizing index is $k$, where $n_k=(r-t+1)(2+(t-1)/k)$ and $n_0=\infty$. At admissible interior boundaries the consecutive candidates tie. If $n\le 2r-t$, the whole level is optimal. A proof uses left compression, the small-support generating lemma for extremal intersecting families for the original and complement families, and the compatibility bound for complementary generating families. The latter forces one generator family to have the candidate threshold size, placing the original family inside a candidate.

Complementing all members preserves cardinality and gives $|A^c\cap B^c|=n-2r+|A\cap B|$. Thus complementation bijects t-intersecting families of $r$-sets with $(n-2r+t)$-intersecting families of $(n-r)$-sets. It swaps left and right coordinate shifts of a set family. When the transformed intersection parameter is positive, extremal families and their generating-support lemmas can therefore be compared in opposite compression directions.

Two members of this uniform set family have at least $2(t+i)-(t+2i)=t$ common points in its distinguished prefix, so it is a t-intersecting family. Nonempty indices satisfy $0\le i\le r-t$. Consecutive-family size comparison reduces to the threshold $n_{i+1}=(r-t+1)(2+(t-1)/(i+1))$: gain sets contain both newly introduced coordinates and $t+i-1$ earlier points; loss sets contain neither and $t+i$ earlier points. Counting these sets with binomial coefficients proves increase below, equality at and decrease above this threshold.

A pairwise intersecting family of two-element sets is contained in a star graph or in the three edges of a triangle in a graph. If two members are $\{a,b\},\{a,c\}$ and a third avoids $a$, the third must be $\{b,c\}$. Every member meeting all three belongs to that triangle.

For an intersecting family of $r$-sets, some element $x$ is avoided by at most $(r-1{)}^2(\genfrac{}{}{0ex}{}{n-2}{r-2})$ members. If two members meet exactly at $x$, every member avoiding $x$ contains one element from each of their disjoint remainders. If no such pair exists, apply the pair-cover bound for a two-intersecting uniform family.

A set family is two-intersecting if $|A\cap B|\ge 2$ for all of its members, including $A=B$. In particular its members all have at least two elements. This is stronger than being an intersecting family.

Fix a member of size $r$. Every other member of a two-intersecting family contains a pair from that fixed member. Counting all $r$-sets containing these pairs gives $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{r}{2}\right)\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)$ for a uniform set family.

On an even ground set $n=2h$, a two-intersecting family has size at most ${\sum }_{j=h+1}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. On an odd ground set $n=2h+1$, the bound is $\left(\genfrac{}{}{0ex}{}{2h}{h+1}\right)+{\sum }_{j=h+2}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. Pair lower levels with complements of upper levels using the intersecting shadow lemma; apply the Erdős-Ko-Rado theorem to the remaining middle level in the odd case.

For an intersecting family of $r$-sets with $r\ge 1$, its lower shadow has at least as many members as the family. Apply elementary set shifts and then the ballot reflection injection to obtain this bound.

For odd $n$ and $w\ge 1$, an intersecting family contains at most one set from each complementary pair in the Boolean lattice. Choosing the larger member in every pair gives the displayed bound and is feasible, because all sets of size greater than $n/2$ intersect. For $w>1$ it is the unique maximizer; for $w=1$ other maximizing families can exist.

A family of words in $[k{]}^n$ is intersecting if any two words agree in some coordinate. For positive $n,k$, its maximum size is $k^{n-1}$: simultaneous cyclic shifts partition the words into classes in which distinct words never agree, and fixing one coordinate attains the resulting bound.

An exactly one-intersecting family satisfies $|A\cap B|=1$ for every two distinct members. It is nontrivial when the intersection of all its members is empty.

A finite linear space consists of finitely many points and proper subsets called lines such that every two points lie on exactly one line. The sets of family indices containing each ground point turn a nontrivial exactly one-intersecting family into a finite linear space.

It is a finite nontrivial instance of a Linear space.

If $r_x$ denotes the number of lines through $x$ in a nontrivial finite linear space on $v$ points, thenTo prove it, let $k_L$ be the line sizes. The inequalities $k_L\le r_x$ whenever $x\notin L$, counted at each integer threshold, givefor every $t\ge 1$. Summing in $t$ and using $\left(\genfrac{}{}{0ex}{}{s}{2}\right)={\sum }_{t\ge 1}(s-t{)}_{+}$ giveswhere the last identity counts pairs of points by their unique line.

A near-pencil on $v$ points has one line containing $v-1$ points and $v-1$ two-point lines joining the remaining point to each point of the large line.

This is a particular finite linear space configuration, rather than a synonym for every pencil of lines.

A finite projective plane of order $q$ has $q^2+q+1$ points and the same number of lines. Every line contains $q+1$ points, every point lies on $q+1$ lines, and every two points or two lines determine a unique line or intersection point respectively.

Two set families $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting when $A\cap B\ne \varnothing$ for every $A\in \mathcal{A}$ and $B\in \mathcal{B}$.

For cross-intersecting families $\mathcal{A},\mathcal{B}$ with member sizes at most $r,s$ respectively, there is a finite set $X$ with $|X|\le r{\sum }_{j=0}^s{r}^j$ such that $A\cap B\cap X\ne \varnothing$ for every $A\in \mathcal{A},B\in \mathcal{B}$. Take a bounded-size transversal kernel ${\mathcal{A}}_0$ preserving hitting sets of size at most $s$ and set $X={\bigcup }_{A\in {\mathcal{A}}_0}A$. For each $B$, the set $B\cap X$ is a hitting set for ${\mathcal{A}}_0$, hence for all of $\mathcal{A}$. This proves the assertion even for infinite set families; if either family is empty, take $X=\varnothing$.

The upward closure of $\mathcal{B}$ is $\overline{\mathcal{B}}=\{A:\text{some }B\in \mathcal{B}\text{ satisfies }B\subseteq A\}$.

For $0<p<1/2$ and $\epsilon >0$, every intersecting family is, up to ${\mu }_p$-measure $\epsilon$, contained in the upward closure of a set family generated by an intersecting family on a bounded set of coordinates.