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,among
2.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 systems, 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
17 2.The Probabilistic Method others,the famous Sperner theorem:If F is a family of subsets of [m]with no
17 2. The Probabilistic Method others, the famous Sperner theorem: If F is a family of subsets of [m] with no two distinct sets A, B ∈ F satisfying A ⊂ B, then |F| ≤ m ⌊m/2⌋ . To see this, set F = {A1, A2, . . . , An} and Bi = [m] \ Ai , and use the fact that m k ≤ m ⌊m/2⌋ for all k = 0, 1, . . . , m
Linearity of Expectation 3.1 Computing Expectation Using Indicators The proofs in this chapter are based on the following lemma: 3.1.1 Lemma.The expectation is a linear operator;i.e.,for any two random variables X,Y and constants a,BR: E[oX+BY]=0E[X]+BE[Y] Proof.E laX+BY]=(aX +BY)dP =a o X dP+8o Y dP aE[X]+ BE [Y]. This implies that the expectation of a sum of random variables X=X1+ X2+…+Xn is equal to EX]=EKl+E[K2+…+E[Xl This fact is elementary dence or independence 3.1.2 Definition (Indicator variables).For an event A,we define the indi- cator variable IA: ·IA(u)=1ifw∈A,and ·IA(u)=0ifwA. 3.1.3 Lemma.For any event A,we have E[IA]=P[A] Proof. EA]=IA()dP=dP=P[A]. In expectation of a variable can be by expresing itof indicator variable X=IA1+IA2+…+IAn
3 Linearity of Expectation 3.1 Computing Expectation Using Indicators The proofs in this chapter are based on the following lemma: 3.1.1 Lemma. The expectation is a linear operator; i.e., for any two random variables X, Y and constants α, β ∈ R: E [αX + βY ] = αE [X] + βE [Y ] . Proof. E [αX + βY ] = R Ω (αX + βY ) dP = α R Ω X dP+β R Ω Y dP = αE [X]+ βE [Y ] . ✷ This implies that the expectation of a sum of random variables X = X1 + X2 + · · · + Xn is equal to E [X] = E [X1] + E [X2] + · · · + E [Xn] . This fact is elementary, yet powerful, since there is no restriction whatsoever on the properties of Xi , their dependence or independence. 3.1.2 Definition (Indicator variables). For an event A, we define the indicator variable IA: • IA(ω) = 1 if ω ∈ A, and • IA(ω) = 0 if ω /∈ A. 3.1.3 Lemma. For any event A, we have E [IA] = P[A]. Proof. E [IA] = Z Ω IA(ω) dP = Z A dP = P[A] . ✷ In many cases, the expectation of a variable can be calculated by expressing it as a sum of indicator variables X = IA1 + IA2 + · · · + IAn
19 3.Linearity of Expectation of certain events with known probabilities.Then E[X]P[A]+P[A]+...+P[An]. Example.Let us calculate the expected number of fixed points of a random permutation o on (1.n.If X(a)={()=l, we can express this as a sum of indicator variables: xo)=∑xXo) where Xi(a)=1 if a(i)=i and 0 otherwise.Then E即周=Pe0==月 and =+片+…+=1 So a random permutation has 1 fixed point (or "loop")on the average. 3.2 Hamiltonian Paths We expectation of X to estimate the minimum or ma there alwaysx mum value 2 for which X(u)≥ is an orientation of a complete graph (for any two vertices u,v,exactly one of the directed edges (u,) )and (v,u)is present A Hamilt path in a tournament is a directed d path passing through all vertices.The following result of Szele(1943)shows the existence of a tournament with very many Hamiltonian paths. 3.2.1 Theorem.There is a tournament on n vertices that has at least Hamiltonian paths Proof.Let us calculate the e cted number of Hamiltonian enautati0oorieutatio with bability ). sider t an X th t that an ith th +1 of diff erent edges is ch EXl=P[o(0,ai+)∈Tfor i=1,2n-1刂=2 The total number of Hamiltonian paths X equals the sum of these indicator variables over all potential Hamiltonian paths,i.e.permutations,and so EX]=∑EX=- So there is a tournament with at leastHamiltonian paths
19 3. Linearity of Expectation of certain events with known probabilities. Then E [X] = P[A1] + P[A2] + · · · + P[An] . Example. Let us calculate the expected number of fixed points of a random permutation σ on {1, . . . , n}. If X(σ) = |{i: σ(i) = i}|, we can express this as a sum of indicator variables: X(σ) = Xn i=1 Xi(σ) where Xi(σ) = 1 if σ(i) = i and 0 otherwise. Then E [Xi ] = P[σ(i) = i] = 1 n and E [X] = 1 n + 1 n + · · · + 1 n = 1. So a random permutation has 1 fixed point (or “loop”) on the average. 3.2 Hamiltonian Paths We can use the expectation of X to estimate the minimum or maximum value of X, because there always exists an elementary event ω ∈ Ω for which X(ω) ≥ E [X] and similarly, we have X(ω) ≤ E [X] for some ω ∈ Ω. We recall that a tournament is an orientation of a complete graph (for any two vertices u, v, exactly one of the directed edges (u, v) and (v, u) is present). A Hamiltonian path in a tournament is a directed path passing through all vertices. The following result of Szele (1943) shows the existence of a tournament with very many Hamiltonian paths. 3.2.1 Theorem. There is a tournament on n vertices that has at least n! 2n−1 Hamiltonian paths. Proof. Let us calculate the expected number of Hamiltonian paths in a random tournament T (every edge has a random orientation, chosen independently with probability 1 2 ). For a given permutation σ on {1, . . . , n}, consider the sequence {σ(1), σ(2), . . . , σ(n)} and denote by Xσ the indicator of the event that all the edges (σ(i), σ(i+ 1)) appear in T with this orientation. Because the orientation of different edges is chosen independently, E [Xσ] = P[(σ(i), σ(i + 1)) ∈ T for i = 1, 2, . . . , n − 1] = 1 2 n−1 . The total number of Hamiltonian paths X equals the sum of these indicator variables over all potential Hamiltonian paths, i.e. permutations, and so E [X] = X σ E [Xσ] = n! 2 n−1 . So there is a tournament with at least n! 2n−1 Hamiltonian paths. ✷
3.3 Splitting Graphs 20 3.3 Splitting Graphs The MAXCUT problem is the following important algorithmic problem:Given a graph G=(V,E),divide the vertex set into two classes A and B=V\A so that the number of edges going between A and B is maximized.This problem is computationally hard(NP-complete).The following simple result tells us that it is always possible to achieve at least half of the edges going between A and B. 3.3.1 Theorem.Any graph with m edges contains a bipartite subgraph with at least edges. Proof.Let G=(V E).and choose a random subset Tc V by inserting everv vertex into T independently with probability For a given edge e=fu.v},let X denote the indicator variable of the event that eractly one of the vertices of e is in T.Then we have E[XJ=P[(u∈T&vT)or(u生T&v∈T】=子+t=. If X denotes the number of edges having exactly one vertex in T,then EW=于EX=受
3.3 Splitting Graphs 20 3.3 Splitting Graphs The MAXCUT problem is the following important algorithmic problem: Given a graph G = (V, E), divide the vertex set into two classes A and B = V \ A so that the number of edges going between A and B is maximized. This problem is computationally hard (NP-complete). The following simple result tells us that it is always possible to achieve at least half of the edges going between A and B. 3.3.1 Theorem. Any graph with m edges contains a bipartite subgraph with at least m 2 edges. Proof. Let G = (V, E), and choose a random subset T ⊆ V by inserting every vertex into T independently with probability 1 2 . For a given edge e = {u, v}, let Xe denote the indicator variable of the event that exactly one of the vertices of e is in T. Then we have E [Xe] = P[(u ∈ T & v /∈ T) or (u /∈ T & v ∈ T)] = 1 4 + 1 4 = 1 2 . If X denotes the number of edges having exactly one vertex in T, then E [X] = X e∈E E [Xe] = m 2 . Thus for some T ⊆ V , there are at least m 2 edges crossing between T and V \T, forming a bipartite graph. ✷