16 LINEARITY OF EXPECTATION so that EW=++=1 In applications we often use that there is a point in the probability space for which X>E[X]and a point for which X EX].We have selected results with a Theorem 2.1.1 There is a tournament T with n players and at least n!2-(n) Hamiltonian paths. the the number of paths.Foreach permutation let X be the indicator random variable for giving a Hamiltonian path:that is,satisfying(o(i),o(i+1)∈T'for 1≤i<n.Then X=∑X。and E[X]=>E[Xa]=n!2-(m-1) Thus some tournament has at least EX]Hamiltonian paths. Szele conjectured that the maximum possible number of Hamiltonian paths in a tournament on n players is at most n!/(2-o(1))".This was proved in Alon(1990a) and is presented in The Probabilistic Lens:Hamiltonian Paths(following Chapter 4). 2.2 SPLITTING GRAPHS Theorem 2.2.1 Let G=(V,E)be a graph with n vertices and e edges.Then G contains a bipartite subgraph with at least e2 edges Proof.Let T V be a random subset given by Pr[E T]=1/2,these choices being mutually independent.Set B=V-T.Call an edge {y}crossing if exactly one of,yis inT.Let X be the number of crossing edges.We decompose X=∑Xy, (r.v)EE where X is the indicator random variable for {,y}being crossing.Then E[X]=2 as two fair coin flips have probability 1/2 of being different.Then EW=∑EXl=5 （z,geE16 LINEARITY OF EXPECTATION so that E [X] = - + ... + - = 1. n n In applications we often use that there is a point in the probability space for which X > E \X] and a point for which X < E [X]. We have selected results with a purpose of describing this basic methodology. The following result of Szele (1943) is oftentimes considered the first use of the probabilistic method. Theorem 2.1.1 There is a toumament T with n players and at least n!2~(n_1) Hamiltonian paths. Proof. In the random toumament let X be the number of Hamiltonian paths. For each permutation a let Xa be the indicator random variable for a giving a Hamiltonian path; that is, satisfying {(r(i), <J(Í + 1)) € T for 1 < i < n. Then X = J2 Xa and E{X] =^E[X ( T ]=n!2" ( n - 1 ) . Thus some toumament has at least E [X] Hamiltonian paths. • Szele conjectured that the máximum possible number of Hamiltonian paths in a toumament on n players is at most n!/(2 — o(l)) n . This was proved in Alón (1990a) and is presented in The Probabilistic Lens: Hamiltonian Paths (following Chapter4). 2.2 SPLITTING GRAPHS Theorem 2.2.1 Let G = (V, E) be a graph with n vértices and e edges. Then G contains a bipartite subgraph with at least e/2 edges. Proof. Let T C V be a random subset given by Pr [IET ] = 1/2, these choices being mutually independent. Set B = V — T. Cali an edge {x, y} crossing if exactly one of x, y is in T. Let X be the number of crossing edges. We decompose X = 2_^ Xxy, {x,y}£E where Xxy is the indicator random variable for {x, y} being crossing. Then E [Xxy] = - as two fair coin flips have probability 1/2 of being different. Then {x,y}£E