Randomized Algorithms (Spring 2010)/The probabilistic method: Difference between revisions
imported>WikiSysop |
imported>WikiSysop |
||
Line 2: | Line 2: | ||
=== Counting or sampling === | === Counting or sampling === | ||
;Ramsey number | |||
{|border="1" | {|border="1" | ||
Line 8: | Line 10: | ||
|} | |} | ||
;Circuit complexity | |||
{|border="1" | {|border="1" | ||
Line 14: | Line 18: | ||
|} | |} | ||
A set <math>T\subseteq | |||
;Blocking number | |||
Let <math>S</math> be a set. Let <math>2^{S}=\{A\mid A\subseteq S\}</math> be the power set of <math>S</math>, and let <math>{S\choose k}=\{A\mid A\subseteq S\mbox{ and }|A|=k\}</math> be the '''<math>k</math>-uniform''' of <math>S</math>. | |||
We call <math>\mathcal{F}</math> a '''set family''' (or a '''set system''') with '''ground set''' <math>S</math> if <math>\mathcal{F}\subseteq 2^{S}</math>. The members of <math>\mathcal{F}</math> are subsets of <math>S</math>. | |||
Given a set family <math>\mathcal{F}</math> with ground set <math>S</math>, | |||
a set <math>T\subseteq S</math> is a '''blocking set''' of <math>\mathcal{F}</math> if all <math>A\in\mathcal{F}</math> have <math>A\cap T\neq \emptyset</math>, i.e. <math>T</math> intersects (blocks) all member set of <math>\mathcal{F}</math>. | |||
{|border="1" | {|border="1" | ||
|'''Theorem''' | |'''Theorem''' | ||
: | :Given a set family <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>m=|\mathcal{F}|</math> and <math>n=|S|</math>, <math>\mathcal{F}</math> has a blocking set of size <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math>. | ||
|} | |} | ||
Revision as of 09:20, 16 April 2010
The Basic Idea
Counting or sampling
- Ramsey number
Theorem
|
- Circuit complexity
Theorem (Shannon)
|
- Blocking number
Let [math]\displaystyle{ S }[/math] be a set. Let [math]\displaystyle{ 2^{S}=\{A\mid A\subseteq S\} }[/math] be the power set of [math]\displaystyle{ S }[/math], and let [math]\displaystyle{ {S\choose k}=\{A\mid A\subseteq S\mbox{ and }|A|=k\} }[/math] be the [math]\displaystyle{ k }[/math]-uniform of [math]\displaystyle{ S }[/math].
We call [math]\displaystyle{ \mathcal{F} }[/math] a set family (or a set system) with ground set [math]\displaystyle{ S }[/math] if [math]\displaystyle{ \mathcal{F}\subseteq 2^{S} }[/math]. The members of [math]\displaystyle{ \mathcal{F} }[/math] are subsets of [math]\displaystyle{ S }[/math].
Given a set family [math]\displaystyle{ \mathcal{F} }[/math] with ground set [math]\displaystyle{ S }[/math], a set [math]\displaystyle{ T\subseteq S }[/math] is a blocking set of [math]\displaystyle{ \mathcal{F} }[/math] if all [math]\displaystyle{ A\in\mathcal{F} }[/math] have [math]\displaystyle{ A\cap T\neq \emptyset }[/math], i.e. [math]\displaystyle{ T }[/math] intersects (blocks) all member set of [math]\displaystyle{ \mathcal{F} }[/math].
Theorem
|
Linearity of expectation
Theorem
|
Theorem
|