imported>WikiSysop |
imported>WikiSysop |
Line 14: |
Line 14: |
| |} | | |} |
|
| |
|
| | A set <math>T\subseteq[n]</math> is a blocking set if <math>T</math> intersects all <math>S\in\mathcal{E}</math>. |
|
| |
|
| {|border="1" | | {|border="1" |
| |'''Theorem''' | | |'''Theorem''' |
| :Let <math>\mathcal{F}\subseteq{[n]\choose k}</math> and let <math>m=|\mathcal{F}|</math>. <math>\mathcal{F}</math> has a blocking set of size <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math>. That is, there exists a set <math>T\subseteq[n]</math> of size <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math> such that <math>T</math> intersects all <math>S\in\mathcal{E}</math>. | | :Let <math>\mathcal{F}\subseteq{[n]\choose k}</math> and let <math>m=|\mathcal{F}|</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 08:50, 16 April 2010
The Basic Idea
Counting or sampling
Theorem
- If [math]\displaystyle{ {n\choose k}\cdot 2^{1-{k\choose 2}}\lt 1 }[/math] then it is possible to color the edges of [math]\displaystyle{ K_n }[/math] vertices with two colors so that there is no monochromatic [math]\displaystyle{ K_k }[/math] subgraph.
|
Theorem (Shannon)
- There is a boolean function [math]\displaystyle{ f:\{0,1\}^n\rightarrow \{0,1\} }[/math] with circuit complexity greater than [math]\displaystyle{ \frac{2^n}{3n} }[/math].
|
A set [math]\displaystyle{ T\subseteq[n] }[/math] is a blocking set if [math]\displaystyle{ T }[/math] intersects all [math]\displaystyle{ S\in\mathcal{E} }[/math].
Theorem
- Let [math]\displaystyle{ \mathcal{F}\subseteq{[n]\choose k} }[/math] and let [math]\displaystyle{ m=|\mathcal{F}| }[/math]. [math]\displaystyle{ \mathcal{F} }[/math] has a blocking set of size [math]\displaystyle{ \left\lceil\frac{n\ln m}{k}\right\rceil }[/math].
|
Linearity of expectation
Theorem
- Given an undirected graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m }[/math] edges, there is a cut of size at least [math]\displaystyle{ \frac{m}{2} }[/math].
|
Theorem
- For any set of [math]\displaystyle{ m }[/math] clauses, there is a truth assignment that satisfies at least [math]\displaystyle{ \frac{m}{2} }[/math] clauses.
|
Alterations
Tools
The Lovász Local Lemma