## Thursday, July 31, 2008

### Forward: 一天變出二十五小時 (25 hours a day)

http://www.cw.com.tw/article/index.jsp?id=34895

• 考慮太多，優柔寡斷
• 完美主義
• 害怕失敗
• 挑簡單、喜歡的先做

## Friday, July 11, 2008

### Approximating the graph by empty graphs

Note that the Regularity Lemma is only meaningful for dense graphs, because for sparse graphs, the density of edges between the pieces of the partition tends to 0.

$\lim\limits_{n\to\infty}\frac{o(n^2)}{(\frac{n}{k})^2} = 0.$

## Monday, July 07, 2008

### Density of a regular pair is the average density of sub-pairs

$\{A_j\mid 1\leq j\leq l\}, \{B_j'\mid 1\leq j'\leq l\}$

$|A_1|=|A_2|=\ldots=|A_l|, \; |B_1|=|B_2|=\ldots=|B_l|$

$\sum\limits_{1\leq j,j'\leq l}d(A_j,B_{j'}) = \frac{\sum\limits_{1\leq j,j'\leq l}e(A_j,B_{j'})}{|A_1|\cdot |B_1|}$ .................... (*)

$d(A,B)=\frac{e(A,B)}{|A|\cdot |B|} = \frac{\sum\limits_{1\leq j,j'\leq l}e(A_j,B_{j'})}{|A|\cdot |B|}\\ = (*)\cdot\frac{|A_1|\cdot |B_1|}{|A|\cdot|B|}\\ =
\frac{\sum\limits_{1\leq j,j'\leq l}d(A_j,B_{j'})}{l^2}$

Theorem: Given a bipartite graph with classes A and B, then for all integers k < |A| and l < |B|, we have

$d(A,B) = \frac{\sum\limits_{X\subset A, Y\subset B,\\ |X| = k, |Y|=l} \quad d(X,Y)}{{|A|\choose k}{|B|\choose l}}$

## Thursday, July 03, 2008

### Additive Combinatorics and Computer Science

Mini-Course: August 23-24 at Princeton University

• Introduction and overview
• Szemerédi regularity lemma and Szemerédi's theorem for k = 3
• The sum-product theorem and its applications
• Proof of the sum-product theorem
• Proof of the regularity lemma
• Szemerédi's theorem for k = 3: Roth's proof
• Gowers uniformity norms and sketch of Gowers' proof of Szemerédi's theorem
• Applications: Direct Product Theorems
• Applications: PCPs and pseudorandomness

Also:
Luca Trevisan's Blog: in theory

## Tuesday, July 01, 2008

### Embedding Lemma & finding regular partitions of a graph

Theorem (Special form of Embedding Lemma).

Given $d> \epsilon > 0$, a graph R, and a positive integer m. Assume that |V(R)| = r and the maximum degree of R is Δ > 0.

Let us construct a graph G by
1. replacing every vertex of R by m (independent) vertices, and
2. replacing the edges of R with ε-regular pairs of density at least d.

If $\epsilon\leq (d-\epsilon)^{\Delta}/(2+\Delta)$, then $R\subset G$. In fact, the number of labelled copies of R in G is at least $(\epsilon m)^{r}$.

(*) Quotes of the Blow-up Lemma:
"... Regular pairs behave like complete bipartite graphs from the point of view of bounded-degree subgraphs. ..."

====================================================

Algorithmic version of the regularity lemma (Alon, Duke, Lefmann, Rödl and Yuster [FOCS'92]):
• Finding ε-regular partitions of a graph can be done in polynomial time.
• However, describe this partition to someone else, he or she cannot verify in polynomial time that this partition is really ε-regular.

J. Komlós, A. Shokoufandeh, M. Simonovits, and E. Szemerédi: The regularity lemma and its applications in graph theory. Theoretical Aspects of Computer Science, Lecture Notes Comput. Sci., Vol. 2292, pp. 84--112, 2002.