Luận văn Phương pháp xác suất để giải một số bài toán khác nhau

t ®iÓm t¹i ®ã X ≤ E[X]. Ta nªu c¸c kÕt qu¶ víi môc ®Ých bµy tá ph­¬ng ph¸p c¬ b¶n nµy. KÕt qu¶ sau cña Szele (1943) nhiÒu lÇn ®­îc xem lµ c¸ch dïng ®Çu tiªn cña ph­¬ng ph¸p x¸c suÊt. §Þnh lý 3.1.1 Cã mét gi¶i ®Êu T víi n ng­êi ch¬i vµ Ýt nhÊt n! 12n−1 ®­êng Hamilton. Chøng minh. Trong mét gi¶i ®Êu ngÉu nhiªn gäi X lµ sè ®­êng Hamilton. Víi mçi phÐp thÕ σ gäi Xσ lµ biÕn ngÉu nhiªn chØ sè mµ σ ®­a ®Õn mét 32 ®­êng Hamilton, tøc lµ tho¶ m·n (σ(i), σ(i+ 1)) ∈ T víi mäi 1 ≤ i < n. ThÕ th× X = ∑ Xσ vµ E[X] = ∑ E[Xσ] = n!2 −(n−1). V× vËy, mét gi¶i ®Êu nµo ®ã cã Ýt nhÊt E[X] ®­êng Hamilton.  3.2 C¸c ®å thÞ t¸ch §Þnh lý 3.2.1 Cho G = (V,E) lµ mét ®å thÞ cã n ®Ønh vµ e c¹nh. ThÕ th× G chøa mét ®å thÞ hai nh¸nh víi Ýt nhÊt e/2 c¹nh. Chøng minh. Gäi T ⊆ V lµ mét tËp con ngÉu nhiªn cho bëi Pr[x ∈ T ] = 1/2, c¸c c¸ch chän nµy lµ ®éc lËp. §Æt S = V − T . Gäi mét c¹nh {x, y} lµ c¾t ngang nÕu cã ®óng mét trong hai ®Ønh x, y ë trong T . Gäi X lµ sè c¸c c¹nh c¾t ngang, ta ph©n tÝch X = ∑ {x,y}∈E Xxy víi Xxy lµ biÕn ngÉu nhiªn chØ sè mµ {x, y} lµ c¾t ngang. ThÕ th× E[Xxy] = 1/2 nªn E[X] = ∑ {x,y}∈E E[Xxy] = e/2. VËy X ≥ e/2 víi mét T nµo ®ã vµ tËp c¸c c¹nh c¾t ngang t¹o nªn mét ®å thÞ hai nh¸nh.  Mét kh«ng gian x¸c suÊt chÆt chÏ h¬n ®­a ®Õn mét c¶i tiÕn nhá. §Þnh lý 3.2.2 NÕu G lµ mét ®å thÞ cã 2n ®Ønh vµ e c¹nh th× nã chøa mét ®å thÞ hai nh¸nh víi Ýt nhÊt en 2n−1 c¹nh. NÕu G lµ mét ®å thÞ víi 2n + 1 ®Ønh vµ e c¹nh th× nã chøa mét ®å thÞ con hai nh¸nh víi Ýt nhÊt e(n+1) 2n+1 c¹nh. Chøng minh. Khi G cã 2n ®Ønh lÊy T ®­îc chän ®Òu tõ trong c¸c tËp con 33 n-phÇn tö cña V . C¹nh tïy ý {x, y} cã x¸c suÊt n2n−1 ®Ó lµ c¾t ngang vµ phÇn cuèi cña chøng minh nh­ tr­íc. Khi G cã 2n+ 1 phÇn tö chøng minh t­¬ng tù b¼ng c¸ch chän T ®Òu tõ c¸c tËp con n phÇn tö cña V .  §©y lµ mét vÝ dô phøc t¹p h¬n. Gäi V = V1 ∪ . . . ∪ Vk víi Vi lµ c¸c c¸c tËp rêi nhau cì n. Gäi h : [V ]k → {−1,+1} lµ c¸ch t« hai mµu c¸c k-tËp. Mét k-tËp E lµ c¾t ngang nÕu nã chøa ®óng mét ®iÓm tõ mçi Vi. Cho S ⊆ V ®Æt h(S) = ∑ h(E), tæng quÐt hÕt c¸c k-tËp E ⊆ S. §Þnh lý 3.2.3 Gi¶ sö h(E) = +1 víi mäi tËp c¾t ngang E. ThÕ th× cã mét S ⊆ V mµ |h(S)| ≥ cknk, ë ®©y ck lµ h»ng sè d­¬ng, ®éc lËp víi n. Bæ ®Ò 3.2.4 Gäi Pk kÝ hiÖu tËp tÊt c¶ c¸c ®a thøc thuÇn nhÊt f(p1, . . . , pk) bËc k mµ c¸c hÖ sè cã gi¸ trÞ tuyÖt ®èi nhiÒu nhÊt lµ mét, p1p2 . . . pk cã hÖ sè 1. ThÕ th× víi mäi f ∈ Pk, tån t¹i p1, . . . , pk ∈ [0, 1] víi |f(p1, . . . , pk)| ≥ ck, ë ®©y ck d­¬ng vµ ®éc lËp víi f . Chøng minh. §Æt M(f) = max p1,...,pk∈[0,1] |f(p1, . . . , pk)|. Cho f ∈ Pk,M(f) > 0 khi f kh«ng lµ ®a thøc kh«ng. V× Pk lµ compact vµ M : Pk → R lµ liªn tôc,M ph¶i cã gi¸ trÞ nhá nhÊt ck. Chøng minh [§Þnh lý 3.2.3] X¸c ®Þnh ngÉu nhiªn S ⊆ V b»ng c¸ch: Pr[x ∈ S] = pi, x ∈ Vi, nh÷ng c¸ch chän nµy lµ ®éc lËp, pi ®· biÕt. §ÆtX = h(S). Víi mçi k-tËp E ®Æt XE = { h(E) nÕu E ⊆ S 0 nÕu kh¸c. 34 Nãi E cã kiÓu (a1, . . . , ak) nÕu |E ∩ Vi| = ai, 1 ≤ i ≤ k. Víi nh÷ng E nµy E[XE] = h(E) Pr[E ⊆ S] = h(E)pa11 . . . pakk . KÕt hîp c¸c sè h¹ng bëi kiÓu: E[X] = ∑ a1+...+ak=k pa11 . . . p ak k . ∑ E cã kiÓu (a1,...,ak) h(E). Khi a1 = . . . = ak = 1 mäi h(E) = 1 bëi gi¶ thiÕt nªn∑ E cã kiÓu (1,...,1) h(E) = nk. Víi nh÷ng kiÓu kh¸c cã Ýt h¬n nk sè h¹ng, mçi c¸i ±1, nªn | ∑ E cã kiÓu (a1,...,ak) h(E)| ≤ nk. VËy E[X] = nkf(p1, . . . , pk), ë ®©y f ∈ Pk, nh­ ®Þnh nghÜa trong Bæ ®Ò 3.2.4. B©y giê chän p1, . . . , pn ∈ [0, 1] víi |f(p1, . . . , pk)| ≥ ck. ThÕ th× E[|X|] ≥ E[X] ≥ cknk. Gi¸ trÞ cô thÓ nµo ®ã cña |X| sÏ v­ît qu¸ hoÆc b»ng kú väng cña nã. VËy cã mét tËp cô thÓ S ⊆ V mµ |X| = |h(S)| ≥ cknk.  3.3 Hai kÕt qu¶ nhanh §Þnh lý 3.3.1 Cã mét c¸ch t« hai mµu cñaKn víi nhiÒu nhÊt( n a ) 21−( a 2) 35 ®¬n mµuKa. Chøng minh [gîi ý] LÊy mét c¸ch t« mµu ngÉu nhiªn. Gäi X lµ sè c¸c ®¬n mµu Ka vµ t×m E[X]. Víi c¸ch t« mµu nµo ®ã gi¸ trÞ cña X nhiÒu nhÊt kú väng nµy.  §Þnh lý 3.3.2 Cã mét c¸ch t« hai mµu cñaKm,n víi nhiÒu nhÊt( m a )( n b ) 21−ab c¸c ®¬n mµuKa,b. Chøng minh [gîi ý] LÊy mét c¸ch t« mµu ngÉu nhiªn. Gäi X lµ sè c¸c ®¬n mµuKa,b vµ t×m E[X]. Víi X nµo ®ã sÏ lín nhÊt lµ kú väng nµy.  3.4 Vect¬ c©n b»ng Sau ®©y |v| lµ chuÈn Euclide th«ng th­êng. §Þnh lý 3.4.1Cho v1, . . . , vn ∈ Rn, mäi |vi| = 1. ThÕ th× tån t¹i e1, . . . , en = ±1 sao cho |e1v1 + . . .+ envn| ≤ √ n, vµ còng tån t¹i e1, . . . , en = ±1 sao cho |e1v1 + . . .+ envn| ≥ √ n. Chøng minh. LÊy e1, . . . , en ®­îc chän ®Òu vµ ®éc lËp tõ {−1,+1}. §Æt X = |e1v1 + . . .+ envn|2 ThÕ th× X = n∑ i=1 n∑ j=1 eiejvi.vj. 36 V× vËy E[X] = n∑ i=1 n∑ j=1 vi.vjE[eiej]. Khi i 6= j,E[eiej] = E[ei].E[ej] = 0. Khi i = j, e2i = 1 nªnE[e2i ] = 1. VËy E[X] = n∑ i=1 vi.vi = n. VËy cã nh÷ng e1, . . . , en = ±1 cô thÓ ®Ó X ≥ n vµ X ≤ n. LÊy c¨n bËc hai hoµn thµnh chøng minh.  KÕt qu¶ sau bao gåm §Þnh lý 3.4.1 øng víi tr­êng hîp p1 = . . . = pn = 1/2. §Þnh lý 3.4.2 Cho v1, . . . , vn ∈ Rn, mäi |vi| ≤ 1. LÊy p1, . . . , pn ∈ [0, 1] tuú ý vµ ®Æt ω = p1v1 + . . . + pnvn. ThÕ th× tån t¹i e1, . . . , en ∈ {0, 1} ®Ó, víi v = e1v1 + . . .+ envn, ta cã |ω − v| ≤ √ n 2 . Chøng minh. Chän c¸c ei ®éc lËp víi Pr[ei = 1] = pi,Pr[ei = 0] = 1− pi. Chän ngÉu nhiªn ei ®­a ®Õn v ngÉu nhiªn vµ biÕn ngÉu nhiªn X = |ω − v|2 Ta t­êng minh X = | n∑ i=1 (pi − ei)vi|2 = n∑ i=1 n∑ j=1 vi.vj(pi − ei)(pj − ej) nªn cã E[X] = n∑ i=1 n∑ j=1 vi.vj‘E[(pi − ei)(pj − ej)] 37 Cho i 6= j, E[(pi − ei)(pj − ej)] = E[pi − ei]E[pj − ej] = 0. Cho i = j, E[(pi − ei)2] = pi(pi − 1)2 + (1− pi)p2i = pi(1− pi) ≤ 1 4 , (E[(pi − ei)2] = Var[ei]). VËy E[X] = n∑ i=1 pi(1− pi)|vi|2 ≤ 1 4 n∑ i=1 |vi|2 ≤ n 4 vµ chøng minh tiÕp tôc nh­ §Þnh lý 3.4.1.  3.5 §Ìn nhÊp nh¸y §Þnh lý 3.5.1 Cho aij = ±1 víi mäi 1 ≤ i, j ≤ n. ThÕ th× tån t¹i xi, yj = ±1, 1 ≤ i, j ≤ n sao cho n∑ i=1 n∑ j=1 aijxixj ≥ (√ 2 pi + o(1) ) n3/2. KÕt qu¶ nµy cã mét øng dông thó vÞ. Cho mét m¶ng n×n c¸c bãng ®Ìn ®­îc chän, mçi c¸i hoÆc bËt (aij = +1) hoÆc t¾t (aij = −1). Gi¶ sö mçi dßng vµ mçi cét cã mét sù chuyÓn sao cho nÕu sù chuyÓn ®­îc x¶y ra (xi = −1 cho dßng i vµ yj = −1 cho cét j) tÊt c¶ ®Ìn ë hµng nµy sÏ chuyÓn: bËt thµnh t¾t vµ t¾t thµnh bËt. ThÕ th× cã thêi ®iÓm sè ®Ìn bËt trõ ®i sè ®Ìn t¾t Ýt nhÊt lµ ( √ 2 pi + o(1))n3/2. Chøng minh [§Þnh lý 3.5.1] Quªn c¸c x. LÊy y1, . . . , yn = ±1 ®­îc chän ®éc lËp, ®Òu vµ ®Æt Ri = n∑ j=1 aijyj, 38 R = n∑ i=1 |Ri|. Cè ®Þnh i. Gi¸ trÞ cña aijyj lµ +1 hoÆc −1 víi x¸c suÊt 1/2 vµ gi¸ trÞ cña chóng (quÐt qua j) lµ ®éc lËp. VËy Ri cã ph©n phèi Sn - ph©n phèi cña tæng n biÕn ngÉu nhiªn {−1,+1} ®Òu, ®éc lËp - nªn E[|Ri|] = E[|Sn|] = (√ 2 pi + o(1) ) √ n. TiÖm cËn nµy t×m b»ng c¸ch ­íc l­îng Sn bëi √ nN , N lµ ph©n phèi chuÈn th«ng th­êng theo ®Þnh lý giíi h¹n trung t©m vµ dïng tÝnh to¸n s¬ cÊp. (MÆt kh¸c, cã thÓ: E[|Sn|] = n21−n ( n− 1 b(n− 1)/2c ) vµ dïng c«ng thøc Stirling). B©y giê ¸p dông sù tuyÕn tÝnh cña kú väng cho R, E[R] = n∑ i=1 E[|Ri|] = (√ 2 pi + o(1) ) n3/2. Cã tån t¹i y1, . . . , yn = ±1 ®Ó R ®¹t Ýt nhÊt gi¸ trÞ nµy. Cuèi cïng, lÊy xi víi dÊu gièng nh­ Ri ®Ó cã n∑ i=1 xi n∑ j=1 aijyj = n∑ i=1 xiRi = n∑ i=1 |Ri| = R ≥ (√ 2 pi + o(1) ) n3/2.  39 Ch­¬ng 4 Bæ®Ò®Þaph­¬ng 4.1 Bæ ®Ò Trong chøng minh kiÓu x¸c suÊt cña mét kÕt qu¶ tæ hîp, ta th­êng ph¶i chØ ra r»ng x¸c suÊt cña mét sù kiÖn nµo ®ã lµ d­¬ng. Tuy nhiªn, nhiÒu chøng minh cho thÊy x¸c suÊt ®Ó c¸c sù kiÖn ®ang xÐt x¶y ra kh«ng chØ d­¬ng mµ cßn lín. Thùc tÕ, nhiÒu chøng minh x¸c suÊt cho thÊy c¸c sù kiÖn ®óng víi x¸c suÊt cao, x¸c suÊt dÇn tíi mét khi sè chiÒu cña bµi to¸n t¨ng. Ch¼ng h¹n, xÐt x¸c suÊt cho trong ch­¬ng 1 r»ng cho mçi k ≤ 1 cã mét gi¶i ®Êu trong ®ã cho mäi tËp k ng­êi ch¬i cã mét ng­êi ®¸nh b¹i tÊt c¶ ng­êi ®ã. Chøng minh chØ râ r»ng cho mçi k cè ®Þnh nÕu sè ng­êi ch¬i n ®ñ lín th× th× hÇu hÕt c¸c gi¶i ®Êu cña n ng­êi ch¬i tháa m·n tÝnh chÊt nµy; nghÜa lµ, x¸c suÊt ®Ó mét gi¶i ®Êu ngÉu nhiªn víi n ng­êi ch¬i cã tÝnh chÊt mong muèn dÇn tíi 1 khi n dÇn tíi v« cïng. MÆt kh¸c, cã mét tr­êng hîp tÇm th­êng trong ®ã ta cã thÓ chØ ra sù kiÖn nµo ®ã x¶y ra víi x¸c suÊt d­¬ng, dï rÊt nhá. Thùc vËy, nÕu chóng ta cã n sù kiÖn ®éc lËp lÉn nhau vµ mçi sù kiÖn ®óng víi x¸c suÊt Ýt nhÊt p > 0, th× x¸c suÊt ®Ó tÊt c¶ c¸c sù kiÖn ®óng hiÓn nhiªn Ýt nhÊt lµ pn, nã lµ d­¬ng dï cã lÏ lµ lòy thõa nhá víi sè mò n. ThËt tù nhiªn ®Ó dù ®o¸n r»ng tõ tr­êng hîp ®éc lËp cã thÓ tæng qu¸t cho nh÷ng tr­êng hîp mµ sù phô thuéc lµ hiÕm, vµ ®­a ra mét c¸ch tæng qu¸t h¬n ®Ó chøng minh r»ng c¸c sù kiÖn nµo ®ã lµ ®óng víi x¸c suÊt d­¬ng, dï nhá. Mét c¸ch tæng qu¸t nh­ thÕ lµ, thùc sù, cã thÓ, vµ ®­îc ph¸t biÓu trong bæ ®Ò sau, gäi lµ Bæ ®Ò §Þa ph­¬ng Lov¸sz. Bæ ®Ò ®¬n gi¶n nµy, ®­îc chøng minh ®Çu tiªn trong Erdos vµ Lov¸sz (1975), lµ mét c«ng cô m¹nh hµng ®Çu, v× nã cung cÊp mét c¸ch ®Ó ®èi phã víi c¸c sù kiÖn hiÕm. 40 Bæ ®Ò 4.1.1 [Bæ ®Ò ®Þa ph­¬ng; Tr­êng hîp tæng qu¸t] Cho A1, A2, . . . , An lµ c¸c sù kiÖn cña mét kh«ng gian x¸c suÊt tïy ý. Mét ®å thÞ cã h­íng D = (V,E) trªn tËp c¸c ®Ønh V = {1, 2, . . . , n} ®­îc gäi lµ ®å thÞ cã h­íng phô thuéc vµo c¸c sù kiÖnA1, A2, . . . , An nÕu cho mçi i, 1 ≤ i ≤ n, sù kiÖn Ai lµ ®éc lËp víi mäi sù kiÖn {Aj : (i, j) /∈ E}. Gi¶ sö r»ngD = (V,E) lµ ®å thÞ cã h­íng phô thuéc vµo c¸c sù kiÖn nªu trªn vµ gi¶ sö r»ng cã c¸c sè thùc x1, x2, . . . , xn sao cho 0 ≤ xi < 1 vµ Pr(Ai) ≤ xi ∏ (i,j)∈E(1− xj) víi mäi 1 ≤ i ≤ n. ThÕ th× Pr(∧ni=1Ai) ≥ ∏ni=1(1 − xi). §Æc biÖt, víi x¸c suÊt d­¬ng, kh«ng cã sù kiÖn Ai nµo ®óng. Chøng minh. Tr­íc hÕt chóng ta chøng minh, b»ng quy n¹p cho s, r»ng cho S ⊆ {1, 2, . . . , n}, |S| = s < n nµo ®ã vµ i /∈ S nµo ®ã, Pr(Ai| ∧ j∈S Aj) ≤ xi. (8) §iÒu nµy ch¾c ch¾n ®óng cho s = 0. Gi¶ sö r»ng nã ®óng cho mäi s′ < s, chóng ta chøng minh nã cho s. §Æt S1 = {j ∈ S : (i, j) ∈ E}, S2 = S \ S1. ThÕ th× Pr(Ai| ∧ j∈S Aj) = Pr(Ai ∧ ( ∧ j∈S1 Aj)| ∧ l∈S2 Al) Pr( ∧ j∈S1 Aj)| ∧ l∈S2 Al) . (9) §Ó ®¸nh gi¸ tö thøc nhËn xÐt r»ng do Ai lµ ®éc lËp víi c¸c sù kiÖn {Al : l ∈ S2}, Pr(Ai ∧ ( ∧ j∈S1 Aj)| ∧ l∈S2 Al) ≤ Pr(Ai| ∧ l∈S2 Al) = Pr(Ai) ≤ xi ∏ (i,j)∈E (1− xj). (10) MÉu thøc, mÆt kh¸c, cã thÓ ®­îc ®¸nh gi¸ dùa theo gi¶ thiÕt quy n¹p. Thùc vËy, gi¶ sö S1 = {j1, j2, . . . , jr}. NÕu r = 0 th× mÉu thøc lµ 1 vµ dÉn ®Õn 41 (8). Tr­êng hîp kh¸c Pr(Aj1 ∧Aj2 ∧ . . . ∧Ajr| ∧ l∈S2 Al) = (1− Pr(Aj1| ∧ l∈S2 Al)).(1− Pr(Aj2|Aj1 ∧ ∧ l∈S2 Al)). . . . . . . .(1− Pr(Ajr|Aj1 ∧Aj2 ∧ . . . ∧Ajr−1 ∧ ∧ l∈S2 Al)) ≥ (1− xj1)(1− xj2) . . . (1− xjr) ≥ ∏ (i,j)∈E (1− xj). (11) KÕt hîp (10) vµ (11) vµo (8), chóng ta kÕt luËn r»ngPr(Ai| ∧ j∈S Aj) ≤ xi, hoµn thµnh chøng minh quy n¹p. B©y giê dÔ dµng suy ra kh¼ng ®Þnh cña Bæ ®Ò 4.1.1, v× Pr( n∧ i=1 Ai) = (1− Pr(A1)).(1− Pr(A2|A1)). . . . . . . .(1− Pr(An| n−1∧ i=1 Ai)) ≥ n∏ i=1 (1− xi), (12) hoµn thµnh chøng minh.  HÖ qu¶ 4.1.2 [Bæ ®Ò §Þa ph­¬ng; Tr­êng hîp ®èi xøng] Cho c¸c sù kiÖn A1, A2, . . . , An trong mét kh«ng gian x¸c suÊt tïy ý. Gi¶ sö r»ng mçi sù kiÖn Ai lµ ®éc lËp víi tËp tÊt c¶ c¸c sù kiÖnAj kh¸c ngo¹i trõ nhiÒu nhÊt d, vµ r»ng Pr(Ai) ≤ p cho mäi 1 ≤ i ≤ n. NÕu ep(d+ 1) ≤ 1 (13) th× Pr( ∧n i=1Ai) > 0. Chøng minh. NÕu d = 0 th× kÕt qu¶ lµ tÇm th­êng. NÕu kh¸c, theo gi¶ thiÕt cã mét ®å thÞ cã h­íngD = (V,E) phô thuéc vµo c¸c sù kiÖnA1, A2, . . . , An trong ®ã cho mçi i, |{j : (i, j) ∈ E}| ≤ d. B©y giê kÕt qu¶ suy ra tõ Bæ ®Ò 4.1.1 b»ng c¸ch lÊy xi = 1/(d+ 1)(< 1) cho mäi i vµ tÝnh chÊt cho d ≥ 1 nµo ®ã, (1− 1 d+1) d > 1/e.  42 Nh­ ®­îc chØ ra bëi Shearer vµo 1985, ®¸ng ®Ó chó ý r»ng h»ng sè 'e' lµ tèt nhÊt cã thÓ trong bÊt ®¼ng thøc (13). Còng chó ý r»ng chøng minh cña Bæ ®Ò 5.1.1 chØ ra r»ng kÕt luËn vÉn cßn ®óng nÕu thay c¸c gi¶ thiÕt Ai ®éc lËp víi c¸c {Aj : (i, j) /∈ E} vµ Pr(Ai) ≤ xi ∏ (i,j)∈E(1 − xj) bëi gi¶ thiÕt yÕu h¬n Pr(Ai| ∧ j∈S2 Aj) ≤ xi ∏ (i,j)∈E(1 − xj), cho mçi i vµ mçi S2 ⊂ {1, 2, . . . , n} \ {j : (i, j) ∈ E}, ®iÒu nµy cã Ých trong mét sè ¸p dông. Trong c¸c môc sau chóng ta giíi thiÖu c¸c ¸p dông kh¸c nhau cña Bæ ®Ò §Þa ph­¬ng ®Ó nhËn mét sè kÕt qu¶ tæ hîp. Kh«ng cã chøng minh cña kÕt qu¶ nµo mµ kh«ng sö dông Bæ ®Ò §Þa ph­¬ng. 4.2 TÝnh chÊt B vµ c¸c tËp ®a s¾c cña c¸c sè thùc Nh¾c l¹i r»ng mét siªu ®å thÞH = (V,E) cã tÝnh chÊtB (tøc lµ hai s¾c), nÕu cã mét c¸ch t« mµu cho V b»ng hai mµu sao cho kh«ng cã c¹nh f ∈ E nµo lµ ®¬n mµu. §Þnh lý 4.2.1 Cho H = (V,E) lµ mét siªu ®å thÞ trong ®ã mçi c¹nh cã Ýt nhÊt k phÇn tö, vµ gi¶ sö r»ng mçi c¹nh cñaH giao víi nhiÒu nhÊt d c¹nh kh¸c. NÕu e(d+ 1) ≤ 2k−1 th×H cã tÝnh chÊt B. Chøng minh. T« mµu mçi ®Ønh v cña H , ®éc lËp vµ ngÉu nhiªn, hoÆc xanh hoÆc ®á (víi x¸c suÊt b»ng nhau). Cho mçi c¹nh f ∈ E, ®Æt Af lµ sù kiÖn r»ng f lµ ®¬n mµu. Râ rµng Pr(Af) = 2/2 |f | ≤ 1/2k−1. H¬n n÷a, râ rµng lµ mçi sù kiÖn Af lµ ®éc lËp víi tÊt c¶ c¸c sù kiÖn Af ′ kh¸c cho mäi c¹nh f ′ mµ kh«ng giao f . B©y giê kÕt qu¶ suy ra tõ HÖ qu¶ 4.1.2.  §Þnh lý 4.2.2 Chom vµ k lµ hai sè nguyªn d­¬ng tháa m·n e(m(m− 1) + 1)k(1− 1 k )m ≤ 1. (14) ThÕ th×, cho mäi tËp S cñam sè thùc nµo ®ã cã mét k-c¸ch t« mµu sao cho mçi phÐp tÞnh tiÕn x+ S (cho x ∈ R) lµ ®a s¾c. Chó ý r»ng (14) ®óng mçi khim > (3 + o(1))k log k. 43 Chøng minh. Chóng ta tr­íc hÕt cè ®Þnh mét tËp h÷u h¹n X ⊆ R vµ chØ ra sù tån t¹i cña mét k-c¸ch t« mµu sao cho mçi phÐp tÞnh tiÕn x + S (cho x ∈ X) lµ ®a s¾c. §©y lµ mét hÖ qu¶ dÔ cña Bæ ®Ò §Þa ph­¬ng. ThËt vËy, ®Æt Y = ∪x∈X(x + S) vµ cho c : Y → {1, 2, . . . , k} lµ mét c¸ch t« k mµu cña Y nhËn ®­îc theo c¸ch chän, cho mçi y ∈ Y , ®éc lËp vµ ngÉu nhiªn, c(y) ∈ {1, 2, . . . , k} theo ph©n phèi ®Òu trªn {1, 2, . . . , k}. Cho mçi x ∈ X , lÊy Ax lµ sù kiÖn r»ng x + S lµ kh«ng ®a s¾c (øng víi c). Râ rµng Pr(Ax) ≤ k(1 − 1k)m. H¬n n÷a, mçi sù kiÖn Ax lµ ®éc lËp víi tÊt c¶ c¸c sù kiÖn Ax′ kh¸c trõ ra nh÷ng sù kiÖn mµ (x + S) ∩ (x′ + S) 6= ∅. V× cã nhiÒu nhÊt m(m − 1) sù kiÖn nh­ vËy, kÕt qu¶ mong muèn suy ra tõ HÖ qu¶ 4.1.2. B©y giê chóng ta cã thÓ chØ ra sù tån t¹i cña mét c¸ch t« mµu cña tËp gåm tÊt c¶ c¸c sè thùc víi tÝnh chÊt mong muèn, bëi mét lËp luËn compact chuÈn. Do mét kh«ng gian rêi r¹c víi k ®iÓm lµ compact (tÇm th­êng), §Þnh lý Tikhonov (c¸i mµ t­¬ng ®­¬ng víi tiªn ®Ò chän) chøng tá r»ng mét tÝch tïy ý cña c¸c kh«ng gian nh­ thÕ lµ compact. §Æc biÖt, kh«ng gian cña tÊt c¶ c¸c hµm tõ R vµo {1, 2, . . . , k}, víi tÝch t«p« th«ng th­êng, lµ compact. Trong kh«ng gian nµy cho mäi x ∈ R cè ®Þnh, tËp Cx cña tÊt c¶ c¸c c¸ch t« mµu c, sao cho x + S lµ ®a s¾c, lµ ®ãng. (Thùc tÕ, nã lµ võa ®ãng võa më, do mét c¬ së cña c¸c tËp më lµ tËp cña tÊt c¶ c¸c c¸ch t« mµu mµ gi¸ trÞ cña chóng lµ trong mét sè h÷u h¹n cña c¸c vÞ trÝ). V× chóng ta ®· chøng minh ë trªn, giao cña mét sè h÷u h¹n c¸c tËp Cx nµo ®ã lµ kh¸c rçng. V× vËy suy ra, tõ tÝnh compact, r»ng giao cña tÊt c¶ c¸c tËp Cx lµ kh«ng rçng. Mét c¸ch t« mµu nµo ®ã trong giao nµy cã tÝnh chÊt nh­ trong kÕt luËn cña §Þnh lý 4.2.2.  4.3 CËn d­íi cho c¸c sè Ramsey T×m ra cËn d­íi cho c¸c sè Ramsey bëi Erdos vµo 1947 lµ mét trong nh÷ng ¸p dông ®Çu tiªn cña ph­¬ng ph¸p x¸c suÊt. Bæ ®Ò §Þa ph­¬ng cung cÊp mét c¸ch ®Ó c¶i tiÕn nh÷ng cËn d­íi nµy. Chóng ta nhËn ®­îc, tr­íc tiªn, cËn d­íi cho sè Ramsey chÐoR(k, k). XÐt mét c¸ch t« hai mµu c¸c c¹nh cñaKn. Cho mçi tËp S cña k ®Ønh cña Kn, gäi AS lµ sù kiÖn r»ng ®å thÞ ®Çy ®ñ trªn S lµ ®¬n mµu. Râ rµng Pr(AS) = 2 1−(k2) . HiÓn nhiªn mçi AS lµ ®éc lËp víi c¸c 44 sù kiÖn AT , trõ khi chóng tháa m·n |S ∩T | ≥ 2, do Ýt nhÊt th× c¸c ®å thÞ ®Çy ®ñ t­¬ng øng cã chung mét c¹nh. Do ®ã chóng ta cã thÓ ¸p dông HÖ qu¶ 4.1.2 víi p = 21−( k 2) vµ d = (k 2 )( n k−2 ) ®Ó kÕt luËn: MÖnh ®Ò 4.3.1 NÕu e( (k 2 )( n k−2 ) + 1).21−( k 2) n. Mét tÝnh to¸n ng¾n ®­a ®Õn R(k, k) > √ 2 e (1 + o(1))k2k/2, chØ c¶i tiÕn mét nh©n tö 2 so víi ¸p dông ph­¬ng ph¸p x¸c suÊt trùc tiÕp. Dï c¶i tiÕn nµy lµ nhá nh­ng ®iÒu ®ã kh«ng khiÕn ph¶i b¨n kho¨n; Bæ ®Ò §Þa ph­¬ng lµ c«ng cô m¹nh nhÊt cho nh÷ng tr­êng hîp sù phô thuéc gi÷a c¸c sù kiÖn lµ hiÕm, ®iÒu kh«ng x¶y ra víi tr­êng hîp ®ang xÐt. Thùc vËy, tæng sè c¸c sù kiÖn ®ang xÐt lµ K = (n k ) , vµ bËc ngoµi lín nhÊt d trong ®å thÞ cã h­íng phô thuéc lµ(k 2 )( n k−2 ) . Cho k lín vµ n lín h¬n nhiÒu, ta cã d > K1−O(1/k), nh­ thÕ sù phô thuéc lµ nhiÒu. MÆt kh¸c, nÕu ta xÐt nh÷ng tËp S nhá, ch¼ng h¹n, nh÷ng tËp cã cì 3, chóng ta nhËn thÊy r»ng mçi c¸i trong tæng sè K = (n 3 ) cña chóng chung nhau mét c¹nh víi chØ 3(n − 3) ≈ K1/3. §iÒu nµy cho biÕt r»ng Bæ ®Ò §Þa ph­¬ng cã lÏ ®¸ng chó ý h¬n ®Ó c¶i tiÕn cho c¸c sè Ramsey kh«ng chÐo R(k, l), ®Æc biÖt khi mét tham sè lµ nhá. TÊt nhiªn ë ®©y chóng ta ph¶i ¸p dông d¹ng kh«ng ®èi xøng cña Bæ ®Ò §Þa ph­¬ng. Chóng ta xÐt mét vÝ dô, theo Spencer (1977), sè Ramsey R(k, 3). Chóng ta t« hai mµu c¸c c¹nh cña Kn ®éc lËp vµ ngÉu nhiªn, mçi c¹nh ®­îc t« mµu xanh víi x¸c suÊt p. Cho mçi tËp T ba ®Ønh, gäi AT lµ sù kiÖn r»ng tam gi¸c trªn T lµ mµu xanh. T­¬ng tù, cho mçi tËp k ®Ønh S, gäi BS lµ sù kiÖn ®å thÞ ®Çy ®ñ trªn S mµu ®á. Râ rµng Pr(AT ) = p 3 vµ Pr(BS) = (1− p)( k 2) . X©y dùng mét ®å thÞ cã h­íng phô thuéc vµo c¸c sù kiÖn AT vµ BS b»ng c¸ch nèi hai ®Ønh b»ng c¸c c¹nh, víi c¶ hai h­íng, nÕu vµ chØ nÕu ®å thÞ ®Çy ®ñ t­¬ng øng chung mét c¹nh. Râ rµng, mçi AT -nót cña ®å thÞ phô thuéc lµ kÒ víi 3(n − 3) < 3n AT ′-nót vµ víi nhiÒu nhÊt lµ (n k ) BS-nót. T­¬ng tù, mçi BS-nót lµ kÒ víi(k 2 ) (n− k) < k2n/2 AT -nót vµ víi nhiÒu nhÊt (n k ) BS′-nót. Ta suy ra tõ Bæ ®Ò §Þa ph­¬ng (Bæ ®Ò 4.1.1) r»ng nÕu ta cã thÓ t×m thÊy mét 0 < p < 1 vµ hai sè thùc 0 ≤ x < 1 vµ 0 ≤ y < 1 sao cho p3 ≤ x(1− x)3n(1− y)(nk) 45 vµ (1− p)(k2) ≤ y(1− x)k2n/2(1− y)(nk) th× R(k, 3) > n. VÊn ®Ò cña chóng ta lµ t×m sè lín nhÊt cã thÓ k = k(n) ®Ó cã mét c¸ch chän p, x vµ y nh­ thÕ. Mét tÝnh to¸n s¬ cÊp chØ ra r»ng c¸ch chän lµ tèt nhÊt khi p = c1n −1/2, k = c2n1/2 logn, x = c3/n3/2 vµ y = c4 en 1/2 log2 n . §iÒu nµy ®­a ®Õn R(k, 3) > c5k 2/ log2 k. LËp luËn t­¬ng tù ®­a ®Õn R(k, 4) > k5/2+o(1). C¶ hai tr­êng hîp ®Òu yªu cÇu mét khèi l­îng tÝnh to¸n lín. Tuy nhiªn, g¸i cã c«ng chång ch¼ng phô; ®¸nh gi¸ R(k, 3) > c5k 2/ log2 k tèt h¬n so víi cËn d­íi cña Erdos (1961) víi nh÷ng lËp luËn rÊt phøc t¹p. C¸i nµy ®­îc c¶i tiÕn bëi Kim (1995) tíi R(k, 3) > c6k 2/ log k. §¸nh gi¸ bªn trªn cho R(k, 4) lµ tèt nhÊt so víi tÊt c¶ c¸c ®¸nh gi¸ kh¸c ®­îc biÕt mµ kh«ng dïng Bæ ®Ò §Þa ph­¬ng. 4.4 Mét kÕt qu¶ h×nh häc Mét hä c¸c h×nh cÇu ®¬n vÞ më F trong kh«ng gian Euclide ba chiÒu R3 ®­îc gäi lµ mét phñ c¬ sè k cña R3 nÕu mét ®iÓm tïy ý x ∈ R3 thuéc Ýt nhÊt k h×nh cÇu. Mét phñ c¬ sè 1 ®­îc gäi ®¬n gi¶n lµ mét phñ. Mét phñ c¬ sè k F ®­îc gäi lµ t¸ch ®­îc nÕu cã mét ph©n ho¹ch thµnh (c¸c hä ®«i mét rêi nhau) F1 vµ F2, mçi hä lµ mét phñ cña R3. Mani-Levitska vµ Pach (1988) x©y dùng mét phñ c¬ sè k kh«ng t¸ch ®­îc, cho sè nguyªn k ≥ 1 tïy ý, bëi c¸c h×nh cÇu ®¬n vÞ më. MÆt kh¸c chóng ta chøng minh ®­îc r»ng mét phñ c¬ sè k cña R3 trong ®ã kh«ng cã ®iÓm nµo bÞ phñ bëi nhiÒu h¬n c2k/3 h×nh cÇu lµ t¸ch ®­îc. §iÒu nµy tiÕt lé mét tÝnh chÊt thó vÞ: khã t¸ch c¸c phñ mµ phñ c¸c ®iÓm nµo ®ã cña R3 nhiÒu lÇn h¬n lµ t¸ch c¸c phñ mµ mçi ®iÓm bÞ phñ bëi cïng mét sè h×nh cÇu. Ph¸t biÓu chÝnh x¸c cña §Þnh lý Mani-Levitska vµ Pach lµ nh­ sau. §Þnh lý 4.4.1 Cho F = {Bi}i∈I lµ mét phñ c¬ sè k cña mét kh«ng gian Euclide ba chiÒu bëi c¸c h×nh cÇu ®¬n vÞ më. Gi¶ sö, thªm n÷a, r»ng kh«ng cã ®iÓm nµo cña R3 ®­îc chøa trong nhiÒu h¬n t thµnh viªn cña F. NÕu e.t3218/2k−1 ≤ 1 th× F lµ t¸ch ®­îc. 46 Chøng minh. X¸c ®Þnh mét siªu ®å thÞ v« h¹nH = (V (H), E(H)) nh­ sau. TËp c¸c ®Ønh cñaH , V (H), ®¬n gi¶n lµ F = {Bi}i∈I . Cho mçi x ∈ R3 ®Æt Ex lµ tËp cña c¸c h×nh cÇu Bi ∈ F mµ chøa x. TËp c¸c c¹nh cñaH , E(H), ®¬n gi¶n lµ tËp c¸c Ex, víi c¸ch hiÓu r»ng khi Ex = Ey c¹nh chØ lÊy mét lÇn. Chóng ta kh¼ng ®Þnh r»ng mçi c¹nh Ex giao víi Ýt h¬n t 3218 c¹nh Ey kh¸c cña H . NÕu x ∈ Bi t©m cña Bi lµ trong kho¶ng c¸ch mét tõ x. B©y giê nÕu Bj ∩ Bi 6= ∅ t©m cña Bj lµ trong kho¶ng c¸ch ba tõ x nªn Bj n»m hoµn toµn trong h×nh cÇu b¸n kÝnh bèn t©m t¹i x. Mét Bj nh­ thÕ phñ ®óng 4−3 = 2−6 thÓ tÝch cña h×nh cÇu ®ã. V× kh«ng cã ®Ønh nµo bÞ phñ nhiÒu h¬n t lÇn cã thÓ cã nhiÒu nhÊt 26t h×nh cÇu nh­ thÕ. Kh«ng khã ®Ó kiÓm tra r»ngm h×nh cÇu trong R3 c¾t R3 thµnh Ýt h¬nm3 thµnh tè liªn th«ng do ®ã cã nhiÒu nhÊt (26t)3 Ey ph©n biÖt giao víi Ex. B©y giê, xÐt, siªu ®å thÞ con h÷u h¹n L nµo ®ã cña H . Mçi c¹nh cña L cã Ýt nhÊt k ®Ønh, vµ nã giao víi nhiÒu nhÊt d < t3218 c¹nh kh¸c cña L. Do, theo gi¶ thiÕt, e(d + 1) ≤ 2k−1, §Þnh lý 4.2.1 (c¸i mµ lµ mét hÖ qu¶ ®¬n gi¶n cña bæ ®Ò ®Þa ph­¬ng), chøng tá r»ng L lµ hai s¾c. §iÒu nµy cã nghÜa lµ ta cã thÓ t« mµu c¸c ®Ønh cña L xanh vµ ®á sao cho kh«ng cã c¹nh nµo cña L lµ ®¬n mµu. Do ®iÒu nµy ®óng cho L h÷u h¹n nµo ®ã, mét lËp luËn vÒ sù compact, lËp luËn nh­ trong §Þnh lý 4.2.2, chØ ra r»ng H lµ hai s¾c. Cho mét c¸ch t« hai mµu cña H mµ kh«ng cã c¹nh nµo ®¬n mµu, chóng ta ®¬n gi¶n lÊy F1 lµ tËp tÊt c¶ c¸c h×nh cÇu mµu xanh, vµ F2 lµ tËp tÊt c¶ c¸c h×nh cÇu mµu ®á. Râ rµng, mçi Fi lµ mét phñ cña R3, hoµn thµnh chøng minh ®Þnh lý.  4.5 Sè arboricity tuyÕn tÝnh cña ®å thÞ Mét rõng tuyÕn tÝnh lµ mét rõng (tøc lµ mét ®å thÞ kh«ng cã vßng) trong ®ã mçi thµnh phÇn liªn th«ng lµ mét ®­êng. Sè arboricity tuyÕn tÝnh la(G) cña ®å thÞ G lµ sè nhá nhÊt c¸c rõng tuyÕn tÝnh trong G, mµ hîp cña chóng lµ tËp cña tÊt c¶ c¸c c¹nh cña G. Kh¸i niÖm nµy ®­îc giíi thiÖu bëi Harary. Gi¶ thuyÕt sau, biÕt ®Õn nh­ lµ Gi¶ thuyÕt sè arboricity tuyÕn tÝnh, ®­îc n¶y sinh trong Akiyama, Exoo vµ Harary (1981). Gi¶ thuyÕt 4.5.1 [Gi¶ thuyÕt sè arboricity tuyÕn tÝnh] Sè arboricity tuyÕn tÝnh 47 cña mäi ®å thÞ d-chÝnh quy lµ d(d+ 1)/2e. Chó ý r»ng mçi ®å thÞ ®Çy ®ñ d-chÝnh quy cã nd/2 c¹nh, vµ mçi rõng tuyÕn tÝnh trong nã cã nhiÒu nhÊt n− 1 c¹nh, cã ngay bÊt ®¼ng thøc la(G) ≥ nd 2(n− 1) > d 2 . Do la(G) lµ mét sè nguyªn nã ®­a ®Õn la(G) ≥ d(d+ 1)/2e. §iÒu khã cña Gi¶ thuyÕt 4.5.1 n»m ë bÊt ®¼ng thøc ng­îc l¹i: la(G) ≤ d(d+ 1)/2e. Còng chó ý r»ng mçi ®å thÞ G víi bËc lín nhÊt ∆ lµ mét ®å thÞ con cña mét ®å thÞ ∆-chÝnh quy (c¸i mµ cã thÓ cã nhiÒu ®Ønh còng nh­ c¹nh h¬n G), Gi¶ thuyÕt sè arboricity tuyÕn tÝnh t­¬ng ®­¬ng víi ph¸t biÓu r»ng sè arboricity tuyÕn tÝnh cña mäi ®å thÞ bËc lín nhÊt ∆ nhiÒu nhÊt lµ d(∆ + 1)/2e. MÆc dï Gi¶ thuyÕt nµy nhËn ®­îc sù quan t©m lín, kÕt qu¶ tæng qu¸t tèt nhÊt liªn quan ®Õn nã, ®­îc chøng minh mµ kh«ng dïng lËp luËn x¸c suÊt, lµ la(G) ≤ d3∆/5e cho ∆ ch½n vµ la(G) ≤ d(3∆ + 2)/5e cho ∆ lÎ. Trong phÇn nµy chóng ta chøng minh r»ng cho mçi  > 0 cã mét ∆0 = ∆0() sao cho cho mäi ∆ ≥ ∆0(), sè arboricity tuyÕn tÝnh cña mäi ®å thÞ víi bËc lín nhÊt ∆ nhá h¬n lµ (12 + )∆. KÕt qu¶ nµy xuÊt hiÖn trong Alon (1988) vµ chøng minh cña nã liªn quan mËt thiÕt ®Õn Bæ ®Ò §Þa ph­¬ng. Tõ kÕt qu¶ cho ®å thÞ cã h­íng chuyÓn sang ®å thÞ v« h­íng lµ rÊt tiÖn lîi. Mét ®å thÞ cã h­íng d-chÝnh quy lµ mét ®å thÞ cã h­íng trong ®ã bËc trong vµ bËc ngoµi cña mäi ®Ønh ®óng lµ d. Mét rõng cã h­íng tuyÕn tÝnh lµ mét rõng trong ®ã mäi thµnh tè liªn th«ng lµ mét ®­êng cã h­íng. Sè arboricity tuyÕn tÝnh cã h­íng dla(G) cña mét ®å thÞ cã h­íng G lµ sè nhá nhÊt c¸c rõng cã h­íng tuyÕn tÝnh cñaG. B¶n cã h­íng cña Gi¶ thuyÕt sè arboricity tuyÕn tÝnh, ®­îc ph¸t biÓu ®Çu tiªn trong Nakayama vµ Peroche (1987) lµ: Gi¶ thuyÕt 4.5.2 Cho mäi ®å thÞ cã h­íng d-chÝnh quyD, dla(D) = d+ 1. Chó ý r»ng do c¸c c¹nh cña mét ®å thÞ v« h­íng 2d-chÝnh quy (liªn th«ng) tïy ý G cã thÓ ®­îc ®Þnh h­íng däc theo mét vßng Euler, sao cho ®å thÞ ®Þnh 48 h­íng kÕt qu¶ lµ d-chÝnh quy, sù ®óng ®¾n cña Gi¶ thuyÕt 4.5.2 cho d sÏ chuyÓn sang Gi¶ thuyÕt 4.5.1 cho 2d. DÔ dµng chøng minh ®­îc mét ®å thÞ tïy ý víi n ®Ønh vµ bËc lín nhÊt d chøa mét tËp ®éc lËp víi cì Ýt nhÊt lµ n/(d+ 1). Chóng ta cã MÖnh ®Ò sau. MÖnh ®Ò 4.5.3 Cho H = (V,E) lµ mét ®å thÞ víi bËc lín nhÊt d, vµ cho V = V1 ∪ V2 ∪ . . . ∪ Vr lµ mét ph©n ho¹ch cña V thµnh r c¸c tËp ®«i mét rêi nhau. Gi¶ sö mçi tËp Vi cã lùc l­îng |Vi| ≥ 2ed, ë ®©y e lµ c¬ sè cña logarithm tù nhiªn. ThÕ th× cã mét tËp c¸c ®Ønh ®éc lËpW ⊆ V (tøc lµ då thÞ c¶m sinh cña V trªnW kh«ng cã c¹nh nµo), mµ chøa mét ®Ønh tõ mçi Vi. Chøng minh. Râ rµng ta cã thÓ gi¶ sö r»ng mçi tËp Vi cã lùc l­îng lµ ®óng g = d2ede (nÕu kh¸c, ®¬n gi¶n thay mçi Vi bëi tËp con cã lùc l­îng g cña nã, vµ thayH bëi ®å thÞ con c¶m sinh cña nã trªn hîp cña r c¸c tËp míi nµy). Chóng ta lÊy ®éc lËp vµ ngÉu nhiªn tõ mçi Vi mét ®Ønh ®¬n theo ph©n phèi ®Òu. LÊy W lµ tËp ngÉu nhiªn cña c¸c ®Ønh ®­îc lÊy. §Ó hoµn thµnh chøng minh chóng ta chØ ra r»ng víi x¸c suÊt d­¬ngW lµ mét tËp c¸c ®Ønh ®éc lËp trongH . Cho mçi c¹nh f cñaH , ®ÆtAf lµ sù kiÖn r»ngW chøa c¶ hai ®Ønh cuèi cña f . Râ rµng, Pr(Af) ≤ 1/g2. H¬n n÷a, nÕu c¸c ®Ønh cuèi cña f n»m trong Vi vµ trong Vj , th× sù kiÖnAf lµ ®éc lËp víi tÊt c¶ c¸c sù kiÖn t­¬ng øng víi c¸c c¹nh mµ c¸c ®Ønh cuèi cña chóng kh«ng n»m trong Vi∪Vj . Tõ ®ã, cã mét ®å thÞ cã h­íng phô thuéc vµo c¸c sù kiÖn trªn trong ®ã bËc lín nhÊt lµ Ýt h¬n 2gd, vµ do e.2gd.(1/g2) = 2ed/g < 1, theo HÖ qu¶ 4.1.2, chóng ta kÕt luËn r»ng víi x¸c suÊt d­¬ng kh«ng cã sù kiÖn Af nµo ®óng. Nh­ng ®iÒu nµy chøng tá r»ngW lµ mét tËp ®éc lËp chøa mét ®Ønh tõ mçi Vi, hoµn thµnh chøng minh.  §Þnh lý 4.5.4 Cho G = (U, F ) lµ mét ®å thÞ cã h­íng d-chÝnh quy, chu vi cã h­íng g ≥ 8ed. ThÕ th× dla(G) = d+ 1. Chøng minh. Nh­ ®· biÕt, F cã thÓ ph©n ho¹ch thµnh d ®å thÞ con dÉn xuÊt 1-chÝnh quy ®«i mét rêi nhau F1, F2, . . . , Fd cña G. [§©y lµ mét hÖ qu¶ dÔ 49 cña §Þnh lý Hall-Konig; cho H lµ mét ®å thÞ hai nh¸nh mµ hai líp ®Ønh cña nã A,B lµ hai b¶n sao cña U , trong ®ã u ∈ A nèi víi v ∈ B nÕu vµ chØ nÕu (u, v) ∈ F . Do H lµ d-chÝnh quy c¸c c¹nh cña nã cã thÓ ph©n chia thµnh d c¸c t­¬ng xøng hoµn h¶o, c¸i mµ t­¬ng øng víi d ®å thÞ con dÉn xuÊt 1-chÝnh quy cña G.] Mçi Fi lµ mét hîp cña c¸c vßng cã h­íng c¸c ®Ønh rêi nhau Ci1, Ci2, . . . , Ciri. Gäi V1, V2, . . . , Vr lµ c¸c tËp cña c¸c c¹nh cña tÊt c¶ c¸c vßng {Cij : 1 ≤ i ≤ d, 1 ≤ j ≤ ri}. Râ rµng c¸c tËp V1, V2, . . . , Vr lµ mét ph©n ho¹ch cña tËp F chøa tÊt c¶ c¸c c¹nh cña G, vµ do ®iÒu kiÖn chu vi, |Vi| ≥ g ≥ 8ed cho mäi 1 ≤ i ≤ r. Gäi H lµ ®å thÞ ®­êng cña G, nghÜa lµ, ®å thÞ mµ tËp ®Ønh cña nã lµ tËp F gåm c¸c c¹nh cña G, trong ®ã hai c¹nh lµ kÒ nhau nÕu vµ chØ nÕu chóng cã chung mét ®Ønh trong G. Râ rµng H lµ (4d− 2)-chÝnh quy. V× lùc l­îng cña mçi Vi Ýt nhÊt lµ 8ed ≥ 2e(4d− 2), nªn cã, theo MÖnh ®Ò 4.5.3, mét tËp ®éc lËp cña H mµ chøa mét thµnh viªn tõ mçi Vi. Nh­ng ®iÒu nµy cã nghÜa lµ cã mét t­¬ng xøngM trong G, chøa Ýt nhÊt mét c¹nh tõ mçi vßng Cij cña c¸c 1-nh©n tè F1, F2, . . . , Fd. Do ®ã M,F1 \M,F2 \M, . . . , Fd \M lµ d+ 1 c¸c rõng cã h­íng trongG (mçi mét trong ®ã lµ mét t­¬ng xøng) mµ phñ tÊt c¶ c¸c c¹nh cña nã. VËy dla(G) ≤ d+ 1. V× G cã |U |.d c¹nh vµ mçi rõng tuyÕn tÝnh cã h­íng cã thÓ cã nhiÒu nhÊt lµ |U | − 1 c¹nh, dla(G) ≥ |U |d/(|U | − 1) > d. V× vËy dla(G) = d+ 1, hoµn thµnh chøng minh.  Bæ ®Ò 4.5.5 Cho G = (V,E) lµ mét ®å thÞ cã h­íng d-chÝnh quy, vµ p lµ mét sè nguyªn tháa m·n 10 √ d ≤ p ≤ 20√d. ThÕ th×, cã mét c¸ch t« p mµu c¸c ®Ønh cña G bëi c¸c mµu 0, 1, . . . , p − 1 víi tÝnh chÊt sau; cho mçi c¹nh v ∈ V vµ mçi mµu i, sè N+v,i = |{(v, u) ∈ E : u cã mµu i}| vµ N−v,i = |{(u, v) ∈ E : u cã mµu i}| tháa m·n: |N+(v, i)− d p | ≤ 3 √ d p √ log d, |N−(v, i)− d p | ≤ 3 √ d p √ log d. (15) 50 Chøng minh. Gäi f : V → {0, 1, . . . , p − 1} lµ mét c¸ch t« p mµu ngÉu nhiªn c¸c ®Ønh cña V bëi p mµu, ë ®©y cho mçi v ∈ V , f(v) ∈ {0, 1, . . . , p − 1} ®­îc chän theo ph©n phèi ®Òu. Cho mçi ®Ønh v ∈ V vµ mçi mµu i, 0 ≤ i < p, gäi A+v,i lµ sù kiÖn r»ng sèN+v,i cña c¸c l©n cËn cña v trong G mµ mµu cña nã lµ i sÏ kh«ng tháa m·n bÊt ®¼ng thøc (15). Râ rµng, N+v,i lµ mét biÕn ngÉu nhiªn NhÞ thøc víi kú väng d/p vµ ph­¬ng sai chuÈn√ d p (1− d p ) < √ d p . VËy, theo ­íc l­îng chuÈn cho ph©n phèi NhÞ thøc, cho mäi v ∈ V vµ 0 ≤ i < p, Pr(A+v,i) < 1/d 4. T­¬ng tù, nÕu gäi A−v,i lµ sù kiÖn sè N − v,i vi ph¹m (15) th× Pr(A−v,i) < 1/d 4. Râ rµng, mçi sù kiÖnA+v,i hoÆcA − v,i lµ ®éc lËp víi tÊt c¶ c¸c sù kiÖnA + u,j hoÆc A−u,j cho mäi ®Ønh u ∈ V mµ kh«ng cã l©n cËn chung víi v trong G. Do ®ã, cã mét ®å thÞ cã h­íng phô thuéc vµo tÊt c¶ c¸c sù kiÖn cña chóng ta ë trªn víi bËc lín nhÊt ≤ (2d)2.p. Do e 1 d4 ((2d)2p + 1) < 1, HÖ qu¶ 4.1.2 (d¹ng ®èi xøng cña Bæ ®Ò §Þa ph­¬ng) chøng tá r»ng víi x¸c suÊt d­¬ng kh«ng sù kiÖn A+v,i hoÆc A − v,i nµo ®óng, nghÜa lµ cã mét c¸ch t« p mµu tháa m·n (15) cho mäi v ∈ V vµ 0 ≤ i < p, hoµn thµnh chøng minh.  B©y giê chóng ta ®· s½n sµng ®Ó ®èi phã víi ®å thÞ cã h­íng chÝnh quy tæng qu¸t. Gäi G = (V,E) lµ mét ®å thÞ cã h­íng d-chÝnh quy tïy ý. Trong suèt c¸c lËp luËn chóng ta gi¶ sö, mçi khi cÇn ®Õn, r»ng d lµ ®ñ lín. LÊy p lµ mét sè nguyªn tè tháa m·n 10 √ d ≤ p ≤ 20√d (®· biÕt lu«n cã mét sè nguyªn tè n»m gi÷a n vµ 2n víi mäi n). Theo Bæ ®Ò 4.5.5 cã mét c¸ch t« mµu c¸c ®Ønh f : V → {0, 1, . . . , p − 1} tháa m·n (15). Cho mçi i, 0 ≤ i < p, gäi Gi = (V,Ei) lµ ®å thÞ con cã h­íng dÉn xuÊt cña G x¸c ®Þnh bëi Ei = {(u, v) ∈ E : f(v) ≡ f(u) + i (mod p)}. Theo bÊt ®¼ng thøc (15) bËc trong lín nhÊt ∆−i vµ bËc ngoµi lín nhÊt ∆ + i trong mçi Gi nhiÒu nhÊt lµ d p + 3 √ d p √ log d. H¬n n÷a, cho mçi i > 0, ®é dµi cña mäi vßng cã h­íng trongGi chia hÕt cho p. Nh­ vËy, chu vi cã h­íng gi cñaGi Ýt nhÊt lµ p. Do mçiGi cã thÓ trë thµnh, do thªm vµo c¸c ®Ønh vµ c¹nh, ®å thÞ cã 51 h­íng ∆i-chÝnh quy víi cïng chu vi gi vµ bËc ∆i = max(∆ + i ,∆ − i ), vµ do gi > 8e∆i (cho tÊt c¶ d ®ñ lín), chóng ta kÕt luËn, theo §Þnh lý 4.5.4, r»ng dlaGi ≤ ∆i + 1 ≤ dp + 3 √ d p √ log d + 1 cho mäi 1 ≤ i < p. Cho G0, chóng ta chØ cÇn ¸p dông bÊt ®¼ng thøc tÇm th­êng dlaG0 ≤ 2∆0 ≤ 2 d p + 6 √ d p √ log d nhËn b»ng c¸ch, ch¼ng h¹n, nhóngG0 nh­ mét ®å thÞ con cña ®å thÞ∆0-chÝnh quy, t¸ch c¸c c¹nh cña ®å thÞ nµy vµo ∆0 c¸c ®å thÞ con 1-chÝnh quy, vµ ph¸ mçi ®å thÞ con dÉn xuÊt 1-chÝnh quy nµy thµnh hai rõng cã h­íng liªn th«ng. Hai bÊt ®¼ng thøc cuèi, kÕt hîp víi gi¶ thiÕt r»ng 10 √ d ≤ p ≤ 20√d, chøng tá dla(G) ≤ d+ 2d p + 3 √ pd √ log d+ 3 √ d p √ log d+ p− 1 ≤ d+ c.d3/4(log d)1/2. Nh­ vËy chóng ta võa chøng minh: §Þnh lý 4.5.6 Cã mét h»ng sè tuyÖt ®èi c > 0 sao cho víi mäi ®å thÞ cã h­íng d-chÝnh quy G, dla(G) ≤ d+ c.d3/4(log d)1/2. §Þnh lý 4.5.7 Cã mét h»ng sè tuyÖt ®èi c > 0 sao cho víi mäi ®å thÞ v« h­íng d-chÝnh quy G, dla(G) ≤ d 2 + c.d3/4(log d)1/2. 4.6 B­íc chuyÓn Latin Trong môc nµy chóng ta tr×nh bµy mét ¸p dông thó vÞ, theo Erdos vµ Spencer (1991). Gäi A = (aij) lµ mét ma trËn cÊp n × n víi c¸c phÇn tö nguyªn. 52 Mét phÐp thÕ pi ®­îc gäi lµ mét b­íc chuyÓn Latin cña A nÕu c¸c phÇn tö aipi(i) (1 ≤ i ≤ n) ®Òu ph©n biÖt víi nhau. §Þnh lý 4.6.1 Gi¶ sö k ≤ (n−1)/(4e) vµ gi¶ sö kh«ng cã sè nguyªn nµo xuÊt hiÖn trong nhiÒu h¬n k phÇn tö cña A, ThÕ th× A cã mét B­íc chuyÓn Latin. Chøng minh. Gäi pi lµ mét phÐp thÕ ngÉu nhiªn cña {1, 2, . . . , n}, ®­îc chän theo ph©n phèi ®Òu trong sè tÊt c¶ n! phÐp thÕ. KÝ hiÖu bëi T tËp tÊt c¶ c¸c bé bèn cã thø tù (i, j, i′, j′) tháa m·n i < i′, j 6= j′ vµ aij = ai′j′. Cho mçi (i, j, i′, j′) ∈ T , kÝ hiÖu Aiji′j′ lµ sù kiÖn pi(i) = j vµ pi(i′) = j′. Sù tån t¹i cña B­íc chuyÓn Latin t­¬ng ®­¬ng víi ph¸t biÓu r»ng kh«ng cã sù kiÖn nµo trong sè c¸c sù kiÖn nµy lµ ®óng víi x¸c suÊt d­¬ng. Chóng ta x¸c ®Þnh mét ®å thÞ cã h­íng ®èi xøng G trªn tËp ®Ønh T b»ng c¸ch t¹o (i, j, i′, j′) kÒ víi (p, q, p′, q′) nÕu vµ chØ nÕu {i, i′} ∩ {p, p′} 6= ∅ hoÆc {j, j′} ∩ {q, q′} 6= ∅ hoÆc aj = apq. Nh­ vËy, hai bé bèn mµ kh«ng kÒ nhau nÕu vµ chØ nÕu bèn « {i, i′}, {p, p′}, {j, j′}, {q, q′} n»m ë bèn hµng vµ bèn cét ph©n biÖt cña A vµ aj 6= apq. BËc lín nhÊt cña G lµ nhá h¬n 4nk; thùc vËy, víi mét (i, j, i′, j′) ∈ T ®· cho cã nhiÒu nhÊt 4n c¸ch chän (s, t) víi hoÆc s ∈ {i, i′} hoÆc t ∈ {j, j′}, vµ víi mçi c¸ch chän (s, t) nµy cã Ýt h¬n k c¸ch chän cho (s′, t′) 6= (s, t) víi ast = as′t′. Mçi bé bèn (s, t, s′, t′) nh­ thÕ cã thÓ viÕt duy nhÊt d¹ng (p, q, p′, q′) víi p < p′. Do e.4nk. 1 n(n−1) ≤ 1, kÕt qu¶ mong muèn suy ra tõ chó ý ®èi víi b¶n ®èi xøng cña Bæ ®Ò §Þa ph­¬ng, nÕu chóng ta chØ ra ®­îc Pr(Aiji′j′| ∧ S Apqp′q′) ≤ 1 n(n− 1) (16) cho (i, j, i′, j′) ∈ T tïy ý vµ tËp S tïy ý cña c¸c thµnh viªn cña T mµ kh«ng kÒ víi (i, j, i′, j′) trong G. Bëi ®èi xøng, chóng ta cã thÓ gi¶ sö r»ng i = j = 1, i′ = j′ = 2 vµ c¸c gi¸ trÞ cña p vµ q kh«ng lµ 1 hoÆc 2. Chóng ta gäi mét phÐp thÕ pi tèt nÕu nã tháa m·n ∧ S Apqp′q′, vµ gäi Sij lµ tËp tÊt c¶ c¸c phÐp thÕ tèt pi tháa m·n pi(1) = i vµ pi(2) = j. Chóng ta kh¼ng ®Þnh r»ng |S12| ≤ |Sij| cho tÊt c¶ i 6= j. Thùc vËy, tr­íc hÕt gi¶ sö r»ng i, j > 2. Cho mçi pi ∈ S12 tèt x¸c ®Þnh mét phÐp thÕ pi∗ nh­ sau. Gi¶ sö pi(x) = i, pi(y) = j. ThÕ th× x¸c ®Þnh pi∗(1) = i, pi∗(2) = j, pi∗(x) = 1, 53 pi∗(y) = 2 vµ pi∗(t) = pi(t) cho tÊt c¶ t 6= 1, 2, x, y. Chóng ta cã thÓ kiÓm tra dÔ dµng r»ng pi∗ lµ tèt, do c¸c « (1, i), (2, j), (x, 1), (y, 2) kh«ng lµ thµnh phÇn cña (p, q, p′, q′) ∈ S. Nh­ vËy pi∗ ∈ Sij , vµ do ¸nh x¹ pi → pi∗ lµ ®¬n ¸nh |S12| ≤ |Sij|, nh­ ®· kh¼ng ®Þnh. T­¬ng tù chóng ta cã thÓ x¸c ®Þnh mét ®¬n ¸nh chØ ra r»ng |S12| ≤ |Sij| thËm chÝ khi {1, 2} ∩ {i, j} 6= ∅ . Nã suy ra r»ng Pr(A1122 ∧ ∧ S Apqp′q′) ≤ Pr(A1i2j ∧ ∧ S Apqp′q′) cho tÊt c¶ i 6= j vµ nh­ thÕ Pr(A1122| ∧ S Apqp′q′) ≤ 1 n(n− 1). Bëi tÝnh ®èi xøng, ®iÒu nµy chøng tá (16) vµ hoµn thµnh chøng minh.  4.7 KhÝa c¹nh gi¶i thuËt Cho (n, d) lµ nh÷ng sè nguyªn d­¬ng. Chóng ta m« t¶ bµi to¸n (n, d) nh­ sau: cho c¸c tËp A1, . . . , AN ⊆ Ω víi mäi |Ai| = n, sao cho kh«ng cã tËp Ai nµo giao víi nhiÒu h¬n d tËp Aj kh¸c, t×m mét c¸ch t« hai mµu cña Ω sao cho kh«ng cã tËp Ai nµo ®¬n mµu. Khi e(d + 1) < 2 n−1 , §Þnh lý 4.2.1 kh¼ng ®Þnh bµi to¸n cã lêi gi¶i. Chóng ta cã thÓ t×m mét c¸ch t« mµu trong sè lÇn ®a thøc (cña N khi n, d cè ®Þnh)? Beck ®­a ra c©u tr¶ lêi kh¼ng ®Þnh víi mét sè gi¶ thiÕt nghiªm ngÆt h¬n. Chóng ta gi¶ sö Ω cã d¹ng Ω = {1, . . . ,m},m ≤ Nn, vµ danh s¸ch c¸c cÊu tróc d÷ liÖu ban ®Çu bao gåm danh s¸ch c¸c phÇn tö cña c¸c tËp Ai vµ danh s¸ch cho mçi i c¸c j mµ j ∈ Ai. Chóng ta gäi G kÝ hiÖu ®å thÞ phô thuéc víi c¸c ®Ønh lµ c¸c tËp Ai vµ Ai, Aj kÒ nhau nÕu chóng giao nhau. §Þnh lý 4.7.1 Cho n, d nh­ thÕ, ®Æt D = d(d − 1)3 cã tån t¹i mét ph©n tÝch n = n1 + n2 + n3 víi 16D(1 + d) < 2n1, 16D(1 + d) < 2n2, 2e(1 + d) < 2n3. 54 ThÕ th× cã mét gi¶i thuËt ngÉu nhiªn víi sè lÇn ch¹y trung b×nh O(N(lnN)c) cho bµi to¸n (n, d), ë ®©y c lµ mét h»ng sè (chØ phô thuéc vµo n vµ d). Chøng minh. B­íc Mét. Trong suèt b­íc nµy, c¸c ®iÓm hoÆc ®á, xanh, kh«ng mµu hoÆc gi÷ l¹i. Chóng ta xÕp c¸c ®iÓm j ∈ Ω thµnh d·y, t« mµu chóng ®á hoÆc xanh ngÉu nhiªn, tung mét ®ång xu. Sau khi mçi j ®­îc t« mµu chóng ta kiÓm tra tÊt c¶ Ai 3 j. NÕu b©y giê Ai cã n1 ®iÓm trong mét mµu vµ kh«ng cã ®iÓm nµo trong mµu kh¸c ta gäiAi lµ nguy hiÓm. TÊt c¶ c¸c k ∈ Ai kh«ng mµu b©y giê ®­îc xem lµ gi÷ l¹i. Khi c¸c ®iÓm gi÷ l¹i k ®­îc chän trong d·y chóng sÏ kh«ng bÞ t« mµu mµ ®¬n gi¶n lµ bá qua. Khi kÕt thóc B­íc Mét c¸c ®iÓm lµ ®á, xanh hay gi÷ l¹i. Chóng ta nãi mét tËp Ai sèng sãt nÕu chóng kh«ng chøa c¸c ®iÓm c¶ xanh vµ ®á. KÝ hiÖu S ⊆ G tËp ngÉu nhiªn cña c¸c tËp sèng sãt. Kh¼ng ®Þnh 4.7.2 TÊt c¶ c¸c thµnh tè C cña G|S cã cì O(lnN), hÇu ch¾c ch¾n. Chøng minh. Mét Ai ∈ S cã thÓ lµ nguy hiÓm hay, cã thÓ, nhiÒu ®iÓm cña nã ®­îc gi÷ l¹i v× tËp c¸c l©n cËn cña nã ®· nguy hiÓm. X¸c suÊt ®Ó mét Ai cô thÓ trë thµnh nguy hiÓm nhiÒu nhÊt lµ 2 1−n1 do khi t« mµu n1 ®iÓm ®Çu tiªn th× chóng ph¶i cïng mµu. (Chóng ta cã bÊt ®¼ng thøc do n1 ®iÓm cña Ai ph¶i ®­îc t« mµu tr­íc khi chóng bÞ gi÷ l¹i.) Gäi V lµ mét tËp ®éc lËp trong G; nghÜa lµ, tËp mµ c¸c Ai lµ ®«i mét rêi nhau. ThÕ th× x¸c suÊt ®Ó tÊt c¶ c¸c Ai ∈ V trë thµnh nguy hiÓm nhiÒu nhÊt lµ (21−n1)|V |. B©y giê lÊy V ⊆ G nh­ vËy mµ kho¶ng c¸ch cña tÊt c¶ c¸c Ai ∈ V Ýt nhÊt lµ bèn, kho¶ng c¸ch ®­îc tÝnh lµ ®é dµi ®­êng ng¾n nhÊt trong G. Chóng ta kh¼ng ®Þnh r»ng Pr[V ⊆ S] ≤ (d+ 1)|V |(21−n1)|V |. §©y lµ v× cho mçi Ai ∈ V cã nhiÒu nhÊt d + 1 c¸ch chän cho mét l©n cËn nguy hiÓmAi′, ®­a ®Õn (d+ 1) |V | c¸ch chän choAi′. V× c¸cAi c¸ch nhau Ýt nhÊt bèn nªn Ai′ kh«ng thÓ lµ kÒ vµ cã x¸c suÊt ®Ó tÊt c¶ chóng lµ nguy hiÓm nhiÒu nhÊt lµ (21−n1)|V |, nh­ ®· kh¼ng ®Þnh. Gäi T ⊆ G lµ mét 4-c©y nÕu kho¶ng c¸ch gi÷a tÊt c¶ c¸cAi ∈ T víi nhau lµ Ýt nhÊt bèn vµ sao cho, vÏ mét cung gi÷aAi, Aj vµ nÕu kho¶ng c¸ch gi÷a chóng 55 ®óng lµ bèn th× ®å thÞ kÕt qu¶ lµ liªn th«ng. Chóng ta tr­íc hÕt ®¸nh gi¸ sè c¸c 4-c©y cã cì u. §å thÞ kho¶ng c¸nh bèn x¸c ®Þnh trªn T ph¶i chøa mét c©y. Cã Ýt h¬n 4j c©y (theo nghÜa ®¼ng cÊu) trªn j ®Ønh, b©y giê cè ®Þnh mét c¸i. Chóng ta cã thÓ d¸n nh·n c©y 1, . . . , u sao cho mçi j > 1 lµ kÒ víi mét i < j nµo ®ã. B©y giê xÐt sè c¸c (A1, . . . , Au) mµ ®å thÞ kho¶ng c¸ch bèn cña nã t­¬ng øng víi c©y nµy. Cã N c¸ch chän cho A1. Víi Ai ®· chän cho tÊt c¶ i < j tËp Aj ph¶i cã kho¶ng c¸ch bèn tõ Ai trong G vµ cã nhiÒu nhÊt D ®iÓm nh­ vËy. VËy sè c¸c 4-c©y cã cì u nhiÒu nhÊt lµ 4uNDu−1 < N(4D)u. Cho 4-c©y T cô thÓ nµo ®ã chóng ta cã Pr[T ⊆ S] ≤ [(d + 1)21−n1]u. VËy sè k× väng c¸c 4-c©y T ⊆ S nhiÒu nhÊt lµ N [8D(d+ 1)2−n1]u. V× sè h¹ng trong ngoÆc nhá h¬n 1/2 theo gi¶ thiÕt, cho u = c1 lnN sè h¹ng nµy lµ o(1). Nh­ vËy G|S sÏ kh«ng chøa 4-c©y cã cì lín h¬n c1 lnN hÇu ch¾c ch¾n. Chóng ta ®ang muèn ®¸nh gi¸ cì cña c¸c thµnh tè C trong G|S. Mét 4-c©y T trong mét thµnh tè C ph¶i cã tÝnh chÊt r»ng mçi Ai ∈ C n»m trong kho¶ng c¸ch ba cña mét Aj ∈ T . Cã Ýt h¬n d3 (mét h¾ng sè) Ai trong kho¶ng c¸ch ba cñaAj nµo ®ã d· cho sao cho c1 lnN ≥ |T | ≥ |C|d−3 nªn, |C| ≤ c2 lnN chøng minh kh¼ng ®Þnh. Trong sè thêi gian tuyÕn tÝnh trung b×nh B­íc Mét sÏ thµnh c«ng. B©y giê cè ®Þnh c¸c ®iÓm ®á hoÆc xanh. Bá qua c¸c tËp chøa c¶ c¸c ®iÓm mµu ®á vµ mµu xanh. Cho mçi Ai sèng sãt cè dÞnh mét tËp con Bi gåm n − n1 ®iÓm gi÷ l¹i. B©y giê t« mµu c¸c ®iÓm gi÷ l¹i sao cho kh«ng cã Bi nµo ®¬n mµu lµ xong. Bi t¸ch vµo c¸c thµnh tè cã cì O(lnN) vµ t« mµu mçi thµnh tè nµy riªng biÖt lµ xong. Trong B­íc Hai chóng ta ¸p dông ph­¬ng ph¸p cña B­íc Mét ®èi víi mçi thµnh tè cña Bi. B©y giê chóng ta gäi mét tËp Bi lµ nguy hiÓm nÕu nã chøa ®óng n2 ®iÓm cïng mét mµu vµ c¸c ®iÓm kh¸c ®­îc gi÷ l¹i. B­íc Hai tèn thêi gian trung b×nh O(lnM) ®Ó t« mµu mét thµnh tè cìM , vËy mét thêi gian trung b×nh O(N) ®Ó t« mµu tÊt c¶ c¸c thµnh tè. (§Ó thµnh c«ng chóng ta yªu cÇu r»ng mét thµnh tè cìM bÞ ph¸ thµnh c¸c thµnh tè cì c2 lnM . §Ó tr¸nh tÇm th­êng, nÕuM < ln lnN th× chóng ta bá qua B­íc Hai víi thµnh tè t­¬ng øng.) Khi kÕt thóc B­íc Hai (vÉn trong thêi gian tuyÕn 56 tÝnh!) cã mét hä c¸c tËp sèng sãt hai lÇn Ci ⊂ Bi ⊂ Ai cã cì n3, thµnh tè lín nhÊt cña chóng cã cì O(ln lnN). Chóng ta vÉn cÇn t« mµu O(N) thµnh tè cì O(ln lnN) nµy, mçi thµnh tè cã cì n3. Theo Bæ ®Ò §Þa Ph­¬ng (hay trùc tiÕp theo §Þnh lý 4.2.1), mçi thµnh tè nµy cã thÓ lµ hai s¾c. Chóng ta ®· t×m ®­îc mét c¸ch t« hai mµu b»ng c¸ch t« mµu nhiÒu chÆng! KiÓm tra tÊt c¶ c¸c c¸ch t« hai mµu cña mét thµnh tè cã cìM tèn O(M2nM) lÇn, øng víi O((lnN)c) trong tr­êng hîp cña chóng ta. Lµm ®iÒu nµy cho tÊt c¶ c¸c thµnh tè tèn O(N(lnN)c) lÇn. §Õn ®©y hoµn thµnh c¸ch t« mµu.  57 Ch­¬ng 5 Chøngminh®ÞnhlýWeierstrasstheoph­¬ngph¸px¸csuÊt Trong gi¶i tÝch c¬ së ta biÕt nÕu mét hµm sè thùc f(x) cã ®¹o hµm mäi cÊp trong l©n cËn cña ®iÓm x = 0 th× cã thÓ biÓu diÔn nã thµnh chuçi lòy thõa d¹ng ∑∞ n=0 anx n . Gäi K lµ b¸n kÝnh héi tô cña chuçi lòy thõa nµy th× chuçi héi tô víi mäi |x| ≤ R, (0 0 cho tr­íc, ta cã thÓ lÊy mét tæng riªng ®ñ lín cña chuçi lµ Pn(x) = ∑n k=0 akx k (lµ mét ®a thøc bËc n) sao cho |Pn(x)− f(x)| < , |x| ≤ R. Tuy nhiªn nÕu f kh«ng cã ®¹o hµm mäi cÊp th× kh«ng tån t¹i biÓu diÔn cña f thµnh d¹ng chuçi lòy thõa nh­ trªn. Nh­ng víi f lµ hµm liªn tôc trªn [a, b] ta vÉn cã thÓ xÊp xØ ®Òu f bëi c¸c ®a thøc trªn ®o¹n [a, b] mét c¸ch tïy ý gÇn. Kh¼ng ®Þnh nµy lµ mét kÕt qu¶ cña mét ®Þnh lý c¬ së quan träng trong gi¶i tÝch: §Þnh lý xÊp xØ Weierstrass. Ch­¬ng nµy tr×nh bµy ph­¬ng ph¸p chøng minh ®Þnh lý quan träng ®ã theo c«ng cô x¸c suÊt vµ còng cho mét ®¸nh gi¸ vÒ tèc ®é héi tô cña xÊp xØ. Xin chó ý r»ng c¸ch dïng x¸c suÊt ë ®©y kh¸c víi ph­¬ng ph¸p x¸c suÊt tr×nh bµy trong nh÷ng ch­¬ng tr­íc. 5.1 Mét sè kiÕn thøc x¸c suÊt c¬ së chuÈn bÞ Trong toµn bé ch­¬ng nµy ta gi¶ sö (Ω,F,Pr) lµ kh«ng gian x¸c suÊt vµ c¸c biÕn ngÉu nhiªn xÐt ®Õn lµ x¸c ®Þnh trªn Ω vµ nhËn gi¸ trÞ trong R. BiÕn ngÉu nhiªn nhÞ thøc BiÕn ngÉu nhiªn X gäi lµ nhÞ thøc B(n, p), p ∈ [0, 1] (chÝnh x¸c lµ biÕn ngÉu nhiªn cã ph©n phèi nhÞ thøc B(n, p)) nÕu nh­ ph©n bè x¸c suÊt cña nã 58 cã d¹ng Pr(X = k) = ∫ {ω:X(ω)=k} Pr(dω) = ( n k ) pk(1− p)n−k, trong ®ã k = 0, 1, . . . , n. Hµm ®Æc tr­ng cña biÕn ngÉu nhiªn nhÞ thøc Cho X lµ biÕn ngÉu nhiªn, hµm ®Æc tr­ng ϕ(t) cña X ®­îc ®Þnh nghÜa nh­ sau: ϕ(t) = E[eitX], t ∈ R (kú väng lÊy theo ®é ®o x¸c suÊt Pr). VíiX lµ biÕn ngÉu nhiªn nhÞ thøc ta cã ϕ(t) = E[eitX] = n∑ k=0 eitk Pr(X = k) = n∑ k=0 eitk ( n k ) pk(1− p)n−k = n∑ k=0 ( n k ) (peit)k(1− p)n−k = [peit + (1− p)]n. VËy hµm ®Æc tr­ng cña biÕn ngÉu nhiªn nhÞ thøc lµ ϕ(t) = [peit + q]n, q = 1− p. (17) NÕu X1, . . . , Xn lµ c¸c biÕn ngÉu nhiªn ®éc lËp vµ cã cïng ph©n phèi nhÞ thøc B(1, p) th× ∑n k=1Xk lµ biÕn ngÉu nhiªn nhÞ thøc B(n, p). ThËt vËy, ®Æt Sn = n∑ k=1 Xk, ta cã hµm ®Æc tr­ng cña Sn lµ ϕSn(t) = E[e itSn] = E[eit ∑n k=1Xk] = E[eitX1 . . . eitXn] = E[eitX1] . . . E[eitXn] = (peit + q)n 59 (biÕn ®æi sau cïng ë trªn lµ do c¸c Xi ®éc lËp vµ cã cïng ph©n phèi). Tõ ®ã suy ra Sn cã ph©n phèi nhÞ thøc B(n, p). C¸c sè ®Æc tr­ng cña biÕn ngÉu nhiªn nhÞ thøc Cho X lµ biÕn ngÉu nhiªn nhÞ thøc B(n, p), ta cã ϕ(t) = E[eitX] = (peit + q)n ≡ ϕn(t) ϕ′(t) = E[iXeitX] = npieit(peit + q)n−1 = npieitϕn−1(t) Suy ra ϕ′(0) = iE[X] = inp nªn E[X] = np. TiÕp tôc lÊy ®¹o hµm cÊp hai, ta ®­îc ϕ′′(t) = E[(iX)2eitX] = −npeit[ϕn−1(t) + (n− 1)peitϕn−2(t)] do ®ã ϕ′′(0) = −E[X2] = −np[1 + (n− 1)p] Suy ra E[X2] = np+ n(n− 1)p2. Tõ ®ã tÝnh ®­îc ph­¬ng sai cña X lµ Var[X] = E[X2]− [EX]2 = np+ n(n− 1)p2 − (np)2 = np(1− p) = npq. VËy kú väng vµ ph­¬ng sai cña X cho bëi E[X] = np,Var[X] = npq. TÊt nhiªn ta còng cã thÓ tÝnh trùc tiÕp c«ng thøc trªn theo ®Þnh nghÜa kú väng vµ ph­¬ng sai. 60 5.2 §Þnh lý xÊp xØ Trong môc con nµy ta chøng minh ®Þnh lý xÊp xØ b»ng ph­¬ng ph¸p x¸c suÊt. KÝ hiÖu: C([a, b],R) lµ kh«ng gian c¸c hµm thùc liªn tôc trªn [a, b], P([a, b],R) lµ kh«ng gian c¸c ®a thøc thùc trªn [a, b], vµ chuÈn sö dông trªn chóng lµ chuÈn ®Òu ||.||u, tøc lµ ||f ||u = sup x∈[a,b] f(x) = max x∈[a,b] f(x), víi f ∈ C([a, b],R). Cã thÓ thÊy P([a, b],R) ⊂ C([a, b],R). §Þnh lý xÊp xØ ph¸t biÓu nh­ sau. §Þnh lý 5.2.1 (xÊp xØ Weierstrass) Cho f ∈ C([a, b],R) vµ  > 0. Khi ®ã tån t¹i ®a thøc P ∈ P([a, b],R) sao cho ||P − f ||u = max x∈[a,b] |P (x)− f(x)| < . §Þnh lý xÊp xØ còng cã thÓ ph¸t biÓu d¹ng: Kh«ng gian P([a, b],R) lµ trï mËt trong C([a, b],R). Chøng minh. Kh«ng mÊt tæng qu¸t ta chØ cÇn chøng minh ®Þnh lý trong tr­êng hîp ®o¹n [a, b] lµ [0, 1]. V× nÕu kh«ng chØ cÇn sö dông phÐp ®æi biÕn t = x− a b− a , x ∈ [a, b]. Cho f ∈ C([0, 1],R). V× f liªn tôc trªn [0, 1] nªn nã liªn tôc ®Òu vµ bÞ chÆn trªn [0, 1]. Tõ ®ã víi mçi  > 0, tån t¹i δ > 0 sao cho ∀x, x′ ∈ [0, 1], |x− x′| < δ : |f(x)− f(x′)| <  2 vµ tån t¹iM > 0 dÓ ||f ||u = max x∈[0,1] |f(x)| ≤M. 61 Víi mçi x ∈ [0, 1], gäi Bxn lµ biÕn ngÉu nhiªn nhÞ thøc B(n, x), n ∈ N. Tõ bÊt ®¼ng thøc Chebyschev ta cã víi mçi n, Pr(|Bxn − E[Bxn]| > n2/3) ≤ x(1− x) n1/3 < 1 n1/3 nªn víi  vµ δ ë trªn, tån t¹i n ∈ N sao cho Pr(|Bxn − E[Bxn]| > n2/3) <  4M (18) vµ 1 n1/3 < δ. (19) §Æt bn(x) ≡ E[f( Bxn n )] = n∑ k=0 f( k n ) ( n k ) xk(1− x)n−k, x ∈ [0, 1]. (20) Khi ®ã |bn(x)− f(x)| = |E[f( Bxn n )− f(x)]| ≤ E[|f(B x n n )− f(x)|] = ∫ {ω:|Bxn−nx|≤n2/3} |f(B x n(ω) n )− f(x)|Pr(dω) + ∫ {ω:|Bxn−nx|>n2/3} |f(B x n(ω) n )− f(x)|Pr(dω) ≤ ∫ {ω:|Bxn−nx|≤n2/3} |f(B x n(ω) n )− f(x)|Pr(dω) +2M Pr(|Bxn − nx| > n2/3). §Ó ý (19) ta cã {ω : |Bxn − nx| ≤ n2/3} = {ω : | Bxn(ω) n − x| ≤ 1 n1/3 < δ}. 62 KÕt hîp víi (18) suy ra |bn(x)− f(x)| <  2 Pr(|Bxn − nx| ≤ n2/3) +  2 ≤ . Do ®ã ||bn − f ||u = max x∈[0,1] |bn(x)− f(x)| < . §©y lµ ®iÒu ph¶i chøng minh.  Chó ý r»ng ®a thøc x¸c ®Þnh theo c«ng thøc (20) gäi lµ ®a thøc Bernstein bËc n cña f(x). Tõ ®Þnh lý trªn ta thÊy víi f ∈ C([0, 1],R) th× d·y c¸c ®a thøc {bn(x)}∞n=1 ⊂ P([0, 1],R) lµ héi tô theo chuÈn ®Òu ®Õn f , nghÜa lµ P([0, 1],R) lµ trï mËt trong C([0, 1],R). Tõ ®iÒu nµy th× E[f( Bxn n )]→ f(x), n→∞ ®Òu theo x ∈ [0, 1]. Ngoµi ra, cã thÓ thÊy f( Bxn n )→ f(x), n→∞ (h.c.c). ThËt vËy, tiÕn hµnh n phÐp thö ®éc lËp. Gäi biÕn ngÉu nhiªn Xxi = { 1, nÕu phÐp thö thø i thµnh c«ng 0, nÕu phÐp thö thø i thÊt b¹i th× Xxi lµ biÕn ngÉu nhiªn nhÞ thøc B(1, x) vµ khi ®ã cã thÓ xem Bxn = n∑ i=1 Xxi thÓ hiÖn cho sè lÇn thµnh c«ng trong n lÇn thùc hiÖn ®ã vµ Bxn lµ biÕn ngÉu nhiªn nhÞ thøc B(n, x). Do ®ã theo luËt m¹nh sè lín ta cã 1 n n∑ i=1 Xxi = Bxn n → E[Xx1 ], n→∞ (h.c.c). Trong ®ã E[Xx1 ] = Pr(X x 1 = 1) = x. 63 V× thÕ víi f ∈ C([0, 1],R), x ∈ [0, 1], ta cã f( Bxn n )→ f(x), n→∞ (h.c.c) 5.3. Mét ®¸nh gi¸ vÒ tèc ®é héi tô cña ®a thøc Bernstein §Þnh lý xÊp xØ Weierstrass cña d·y hµm {bn(x)}∞n=1 vÒ hµm liªn tôc f ∈ C([0, 1],R) ®Òu trªn [0, 1] kh«ng cho ta th«ng tin vÒ tèc ®é héi tô. Môc con nµy cho ta mét ®¸nh gi¸ vÒ tèc ®é héi tô. Cho f ∈ C([a, b],R). Khi ®ã, víi bÊt kú δ > 0, m«®un liªn tôc cña f trªn [a, b] lµ ®¹i l­îng ω(δ) ≡ sup |x−x′|<δ |f(x)− f(x′)|, x, x′ ∈ [a, b]. Chóng ta cã ®Þnh lý sau vÒ m«®un liªn tôc. §Þnh lý 5.3.1 (a) NÕu 0 < δ1 ≤ δ2 th× ω(δ1) ≤ ω(δ2). (b) §iÒu kiÖn cÇn vµ ®ñ ®Ó f liªn tôc ®Òu trªn [a, b] lµ lim δ→0 ω(δ) = 0. (c) ∀λ > 0, ω(λδ) ≤ (λ+ 1)ω(δ). Chøng minh. ThÊy r»ng (a) vµ (b) lµ hiÓn nhiªn. Víi λ > 0 ®· cho, tån t¹i n ∈ N : n ≤ λ < n+ 1. Tõ tÝnh chÊt (a) suy ra ω(λδ) ≤ ω[(n+ 1)δ]. LÊy x, x′ ∈ [a, b] sao cho x < x′ vµ |x − x′| ≤ (n + 1)δ. Chia ®o¹n [x, x′] thµnh n + 1 phÇn b»ng nhau, ®é dµi mçi phÇn lµ x ′−x n+1 víi c¸c ®iÓm chia yi = x+ i x′ − x n+ 1 , i = 0, 1, . . . , n+ 1. 64 Khi ®ã |f(x)− f(x′)| = | n∑ i=0 [f(yi+1)− f(yi)]| ≤ n∑ i=0 |[f(yi+1)− f(yi)]| ≤ (n+ 1)ω(δ), (v× |yi+1 − yi| = 1n+1|x′ − x| ≤ δ, i = 0, 1, . . . , n). Suy ra ω[(n+ 1)δ] = sup |x−x′|≤(n+1)δ |f(x)− f(x′)| ≤ (n+ 1)ω(δ). Tõ ®ã ω(λδ) ≤ ω[(n+ 1)δ] ≤ (n+ 1)ω(δ). ≤ (λ+ 1)ω(δ).  TiÕp theo lµ kÕt qu¶ vÒ tèc ®é héi tô cña ®a thøc Bernstein. §Þnh lý 5.3.2 Cho f ∈ C([0, 1],R) vµ bn(x) lµ ®a thøc Bernstein cña f . Khi ®ã ||bn − f ||u = max x∈[0,1] |bn(x)− f(x)| ≤ 3 2 ω( 1√ n ), víi ω(δ) lµ m«®un liªn tôc cña f trªn [0, 1]. Chøng minh. Ta cã |bn(x)− f(x)| = |E[f( Bxn n )− f(x)]| ≤ E[|f(B x n n )− f(x)|] = n∑ k=0 |f(k n )− f(x)| ( n k ) xk(1− x)n−k ≤ n∑ k=0 ω(|x− k n |) ( n k ) xk(1− x)n−k. 65 ¸p dông §Þnh lý 5.3.1(c), ω(|x− k n |) = ω(n1/2|x− k n |n−1/2) ≤ (1 + n1/2|x− k n |)ω(n−1/2). V× thÕ |bn(x)− f(x)| ≤ n∑ k=0 (1 + n1/2|x− k n |)ω(n−1/2) ( n k ) xk(1− x)n−k ≤ ω(n−1/2)[1 + n1/2 n∑ k=0 |x− k n | ( n k ) xk(1− x)n−k]. Sö dông bÊt ®¼ng thøc Cauchy-Schwarz ta cã n∑ k=0 |x− k n | ( n k ) xk(1− x)n−k = n∑ k=0 |x− k n |( ( n k ) xk(1− x)n−k)1/2( ( n k ) xk(1− x)n−k)1/2 ≤( n∑ k=0 (x− k n )2 ( n k ) xk(1− x)n−k)1/2( n∑ k=0 ( n k ) xk(1− x)n−k)1/2 =( x(1− x) n )1/2 ≤ ( 1 4n )1/2. Suy ra |bn(x)− f(x)| ≤ ω(n−1/2)(1 + n1/2( 1 4n )1/2), nªn |bn(x)− f(x)| ≤ 3 2 ω(n−1/2), ∀x ∈ [0, 1].  HÖ qu¶ 5.3.3 NÕu f lµ mét hµm liªn tôc Lipschitz Lip(K, α) trªn [0, 1] (nghÜa lµ |f(x)− f(x′)| ≤ K|x− x′|α, ∀x, x′ ∈ [0, 1], α > 0) th× |bn(x)− f(x)| ≤ 3 2 Kn−α/2. 66 Chøng minh. Tõ ®iÒu kiÖn Lipschitz ta cã ω(δ) ≤ Kδα. Sö dông §Þnh lý 5.3.2 suy ra |bn(x)− f(x)| ≤ 3 2 Kn−α/2, ∀x ∈ [0, 1].  §Ó kÕt thóc, ta nªu mét vÝ dô. Ta cã hµm f(x) = √ x lµ Lip(1, 1/2) víi x ≥ 0. Tõ HÖ qu¶ 5.3.3 trªn suy ra |bn(x)− √ x| ≤ 3 2n1/4 , ∀x ∈ [0, 1]. trong ®ã bn(x) = n∑ k=0 ( k n )1/2 ( n k ) xk(1− x)n−k, x ∈ [0, 1]. 67 KÕt luËn LuËn v¨n ®· lµm ®­îc nh÷ng viÖc sau: • Tr×nh bµy c¬ së vÒ ®å thÞ. • Gi¶i mét sè bµi to¸n b»ng Ph­¬ng ph¸p X¸c suÊt c¬ b¶n ®Ó lµm râ vÒ ph­¬ng ph¸p. • Tr×nh bµy Ph­¬ng ph¸p X¸c suÊt kÕt hîp víi tÝnh chÊt cña kú väng cña c¸c biÕn ngÉu nhiªn. • Tr×nh bµy vÒ kÜ thuËt ¸p dông Bæ ®Ò §Þa ph­¬ng. • Dïng kÜ thuËt X¸c suÊt ®Ó chøng minh ®Þnh lý Weierstrass. Mét sè vÊn ®Ò cÇn tiÕp tôc nghiªn cøu: • T×m lêi gi¶i cho c¸c bµi to¸n thuéc nhiÒu lÜnh vùc kh¸c nhau. • Nh÷ng øng dông thùc tÕ cña Ph­¬ng ph¸p X¸c suÊt, ch¼ng h¹n nh­ trong Khoa häc M¸y tÝnh, trong ®ã ®Æc biÖt quan t©m ®Õn viÖc x©y dùng c¸c gi¶i thuËt ®Ó t×m c¸c cÊu tróc cã tÝnh chÊt mong muèn. 68 Tµi liÖu tham kh¶o [1] Noga Alon, Joel H. Spencer (2000), The Probabilistic Method, John Wiley & Sons Inc, New York. [2] BÐla Bollob¸s (1998), Modern Graph Theory, Springer, New York. [3] NguyÔn ViÕt Phó, NguyÔn Duy TiÕn (2004), C¬ së Lý thuyÕt X¸c suÊt, Nhµ xuÊt b¶n §¹i häc Quèc gia Hµ Néi, Hµ Néi. [4] NguyÔn Duy TiÕn, Vò ViÕt Yªn (2006), Lý thuyÕt X¸c suÊt, Nhµ xuÊt b¶n Gi¸o dôc, ViÖt Nam. [5] §Æng Hïng Th¾ng (2008), Thèng kª vµ øng dông, Nhµ xuÊt b¶n Gi¸o dôc, ViÖt Nam. [6] NguyÔn H¾c H¶i (2007), X¸c suÊt & Thèng kª, Bé Gi¸o dôc vµ §µo t¹o (Gi¸o tr×nh ®iÖn tö), Hµ Néi. [7] NguyÔn H÷u Ngù (2001), Lý thuyÕt §å thÞ, Nhµ xuÊt b¶n §¹i häc Quèc gia Hµ Néi, Hµ Néi. 69