2.4 Pairs of Sets 16 2.4 Pairs of Sets Let k and e be fixed natural numbers.We are interested in the maximum n= n(k,)such that there exist sets A1,A2,...,An and B1,B2,...,Bn satisfying the following conditions (C0)A=k,Bl e for all i=1.2.....n. (C1)0 for all i=1,2.....n. (C2)AnB≠0 for all i≠j,i,j=1,2,n. An example shows that n(k,)():let A1,....An be all the k-element subsets of {1,2.....k+e}and let B:be the complement of A.An ingenious probabilistic argument shows that this is the best possible(note that at first sight,it is not at all obvious that n(,)is finite!). 2.4.1 Theorem.For any k,z 1,we have n(k,()= Before we prove this theore roblem.It is related to the tn her of s ntral iser in s.Recall that a set T C X is sal of a set system FC 2x if SnT for all SEF.The tra of the smallest mbin sversal of nsversal usually studies the ritical obiects.In alled c: tical)) (F)for question were re theoren mbe T-critica +1 11 d sversal of (C0)-(C2) Thus F≤n(k,). Proof of Theorem 2.4.1.Let X =U(A;UB:)be the ground set.Arrange the elements of x in a random linear order (all the lxl!orderings having the same probability).Let U:be the event"each element of A precedes each element ofB”.We have PU (9 and Uj cannot occur multan ously for i≠j nB≠≠AnB,we have max Ai2m Bj and max A.≥ oth U:and ecurred,then max Ai min Bi and max A min Bj,and we get a contradiction:max Ai>min B max Aj min Bi> max A;.Therefore 1≥P0叫=P0吲=药 i=1 and the theorem follows The same proof shows that if A1,A2.. An and Bi,B2....Bn are finite sets satisfying (C1)and (C2)then)1.This implics,among2.4 Pairs of Sets 16 2.4 Pairs of Sets Let k and ℓ be fixed natural numbers. We are interested in the maximum n = n(k, ℓ) such that there exist sets A1, A2, . . . , An and B1, B2, . . . , Bn satisfying the following conditions (C0) |Ai | = k, |Bi | = ℓ for all i = 1, 2, . . . , n. (C1) Ai ∩ Bi = ∅ for all i = 1, 2, . . . , n. (C2) Ai ∩ Bj 6= ∅ for all i 6= j, i, j = 1, 2, . . . , n. An example shows that n(k, ℓ) ≥ ￾ k+ℓ k
: let A1, . . . , An be all the k-element subsets of {1, 2, . . . , k + ℓ} and let Bi be the complement of Ai . An ingenious probabilistic argument shows that this is the best possible (note that at first sight, it is not at all obvious that n(k, ℓ) is finite!). 2.4.1 Theorem. For any k, ℓ ≥ 1, we have n(k, ℓ) = ￾k+ℓ k
. Before we prove this theorem, we explain a motivation for this (perhaps strange-looking) problem. It is related to the transversal number of set sys￾tems, one of the central issues in combinatorics. Recall that a set T ⊆ X is a transversal of a set system F ⊆ 2 X if S ∩ T 6= ∅ for all S ∈ F. The transversal number τ (F) is the size of the smallest transversal of F. In order to understand a combinatorial parameter, one usually studies the critical objects. In our case, a set system F is called τ -critical if τ (F \ {S}) < τ (F) for each S ∈ F. A question answered by the above theorem was the following: what is the maximum possible number of sets in a τ -critical system F, consisting of k-element sets and with τ (F) = ℓ+1? To see the connection, let F = {A1, A2, . . . , An}, and let Bi be an ℓ-element transversal of F \ {Ai}. Note that by the τ -criticality of F, the Bi exist and satisfy conditions (C0)–(C2). Thus |F| ≤ n(k, ℓ). Proof of Theorem 2.4.1. Let X = Sn i=1(Ai ∪Bi) be the ground set. Arrange the elements of X in a random linear order (all the |X|! orderings having the same probability). Let Ui be the event “each element of Ai precedes each element of Bi”. We have P[Ui ] = ￾ k+ℓ k
−1 . Crucially, we note that Ui and Uj cannot occur simultaneously for i 6= j. Indeed, since Ai ∩ Bj 6= ∅ 6= Aj ∩ Bi , we have max Ai ≥ min Bj and max Aj ≥ min Bi . If both Ui and Uj occurred, then max Ai < min Bi and max Aj < min Bj , and we get a contradiction: max Ai ≥ min Bj > max Aj ≥ min Bi > max Ai . Therefore 1 ≥ P  [n i=1 Ui  = Xn i=1 P[Ui ] = n ￾ k+ℓ k
and the theorem follows. ✷ The same proof shows that if A1, A2, . . . , An and B1, B2, . . . , Bn are finite sets satisfying (C1) and (C2) then Pn i=1 ￾|Ai|+|Bi| |Ai|
−1 ≤ 1. This implies, among