March 24, 2025

Turan's Theorem

Lecture Notes for CS477 combinatorics on 2025/03/24

flipping a coin

$p\in[0,1]$ 均匀随机，问100次恰有50次H的概率？

$$\int_0^1{100\choose50}p^{50}(1-p)^{50}\text{d} p={100\choose50}B(51,51)=\frac{1}{101}$$

另外一种：

$$\int_0^1{100\choose50}p^{50}(1-p)^{50}\text{d} p=\sum_{r=0}^{50}(-1)^r{100\choose50}{50\choose r}\frac{1}{51+r}=^?\frac{1}{101}$$

即证

$$\sum_{r=0}^{50}(-1)^r\frac{101!}{50!50!}\frac{50!}{r!(50-r)!}\frac{1}{51+r}=\sum_{r=0}^{50}(-1)^r{101\choose 51+r}{50+r\choose r}=^?1$$

induced subgraph

$G$ 没有诱导子图是 $P_3$ $\iff$ $G$ 的每个连通块都是团.

左推右.

归纳法，在连通块中先挑一个，它对其他总有一条边，将相应的点加入；直到选到所有连通块中的点.
连通块中任意两点必有路径，因此每个 $P_3$ 必须加边成三角形.
任何一个点，其邻居必定两两相邻. 因此 $v\cup N(v)$ 是一个团. 假设这连通块还有剩余的点，则 $x$ 到$N(v)$ 中某点相邻，那么 $x$ 和 $v$ 相邻.
用等价关系来考虑，简单无向图——对称性，无 induced $P_3$ ——传递性，再加上所有自环即可，由于等价关系$\iff$ 分划.

Turan 定理八股文

Thm. (Turan, 1941) n 阶图 $\omega\leq p$, 那么 $m\leq t(n,p)$, $t(n,p)$ 为完全 $p$ 部图 $T(n,p)$ 的边数.

January 14, 2025

Computation Theory - 0x00

…ようこそ。Ave Mujicaの世界へ

2025 冬休み

Chapter 1 正则语言

定义. 有限自动机，(deterministic) finite automaton (pl.-ta) (DFA)
有限自动机是一个五元组$(Q,\Sigma,\delta,q_0,F)$：
$Q$ - 有限状态集
$\Sigma$ - 有限字符集
$\delta:Q\times\Sigma\mapsto Q$ - 转移函数
$q_0\in Q$ - 初始状态
$F\subseteq Q$ - 接受状态集合

语言是字符串的集合，即 $\Sigma^*\cup\{\epsilon\}$ 的子集. 一个有限自动机所接受的所有字符串集合也是一个语言，记作 $L(M)$ . 需要特别注意语言 $\varnothing$ 和字符串 $\epsilon$ 的区别.

定义. 正则语言，regular language
对于语言 $A$，如果存在自动机 $M$ 使得 $L(M)=A$，那么 $A$ 是正则语言。

定义. 正则运算，regular operation
对语言 $A,B$，定义
$A\cup B=\{x:x\in A\text{ or }x\in B\}$,
$A\circ B=\{xy:x\in A\text{ and }y\in B\}$,
$A^*=\{x_1\dots x_k:k\geq 0, \forall i\;x_i\in A\}$

June 24, 2024

Untyped Lambda Calculus

Lambda Terms

An intuitive thought: for $x$, $x^2+1$ can be a function or merely a number.

Thus we distinguish them, by denoting the function by $\lambda x.x^2+1$.

Definition 1. Let $V$ be an infinite variable set $\{x,y,z,\dots\}$, $\Lambda$ be a set of Lambda terms.

(1) If $u\in V$, then $u\in \Lambda$.

(2)(juxtaposition for application) If $M,N\in \Lambda$, then $(M\;N)\in\Lambda$.

(3) If $x\in V$, $N\in \Lambda$, then $(\lambda x.N)\in\Lambda$.

Or in short, $\Lambda=V|(\Lambda\Lambda)|(\lambda V.\Lambda)$.

June 14, 2024

Measurable Functions

In Axiomization of probability.

i.e. Random variables

Notations

$\mathcal{L}^+_{b}(\mathcal{C})$: the set of all bounded measurable functions on $\mathcal{C}$.

Definition and Theorem of Approximation

Definition 1. 设$(\Omega,\mathcal{F})$和$(E,\mathcal{E})$是测度空间，$f:\Omega\to E$是一个映射，如果对于每一个$A\in\mathcal{E}$，$f^{-1}(A)\in\mathcal{F}$，则称$f$是$\mathcal{F}/\mathcal{E}$-可测映射.

Definition 2. 令$E=\overline{\mathbb{R}},\mathcal{E}=\mathcal{B}(\overline{\mathbb{R}})$，则称$f$为Borel可测函数.

Example 3. Let $\mathscr{F}$ be some collection of $f\in C(0,1)$. Then $\Phi(x)=\sup_{f\in\mathscr{F}} f$ and $\Psi(x)=\inf_{f\in\mathscr{F}} f$ is measurable.

Proof. Consider $E_t={\{x:\Phi(x)>t\}}$. Then $\Phi(x_0)>t$ implies that there exists $f_{x_0}\in\mathscr{F}$ such that $f_{x_0}(x_0)>t$. Since $f$ is continuous, there exists $\delta>0$ s.t. for all $x\in B_{\delta}(x_0)$, $f_{x_0}(x)>t$. Thus $B_{\delta}(x_0)\subseteq E_t$. Hence $E_t$ is open, and $\Phi$ is measurable.
$\blacksquare$

June 13, 2024

Measures

There is no way of measuring the importance of measure.

Definition 1.
Let $\mathcal{F}$ be a $\sigma$-algebra on $\Omega$. A function $\mu:\mathcal{F}\to[0,+\infty]$ is a measure if

$\mu(\emptyset)=0$.
$\mu(\bigcup_{n=1}^{\infty}A_n)=\sum_{n=1}^{\infty}\mu(A_n)$ for all $A_n\in\mathcal{F}$ where $A_i\cap A_j=\emptyset$ for $i\neq j$.

If $\mu(\Omega)\lt +\infty$, then $\mu$ is a finite measure.
If $\mu(\Omega)=1$, then $\mu$ is a probability measure.

Definition 2.
Let $\mu$ be a non-negatice set function over $\mathcal{C}$. Then $\mu$ is

finite addable, if $A_i\in\mathcal{C}$ are disjoint and $\sum_{i=1}^n A_i\in\mathcal{C}$, then $\mu(\sum_{i=1}^n A_i)=\sum_{i=1}^n\mu(A_i)$.
$\sigma$-addable, if $A_i\in\mathcal{C}$ are disjoint and $\sum_{i=1}^{+\infty} A_i\in\mathcal{C}$, then $\mu(\sum_{i=1}^{+\infty} A_i)=\sum_{i=1}^{+\infty}\mu(A_i)$.
downward continuous, if for $A_i\in\mathcal{C}$ and $A_n\uparrow A\in\mathcal{C}$, $\lim_{n\to\infty}\mu(A_n)=\mu(A)$.
upward continuous, if for $A_i\in\mathcal{C}$ and $\mu(A_0)\lt +\infty$, $A_n\downarrow A\in\mathcal{C}$, $\lim_{n\to\infty}\mu(A_n)=\mu(A)$.
continuous upon zero, if for $A_i\in\mathcal{C}$ and $\mu(A_0)\lt +\infty$,$A_n\downarrow\emptyset$, $\lim_{n\to\infty}\mu(A_n)=0$.

Theorem 3. Let $\mu$ be a finite addable non-negative set function over an algebra $\mathcal{C}$. Then $\mu$ is $\sigma$-addable $\Leftrightarrow$
$\mu$ is downward continuous $\Rightarrow$ $\mu$ is upward continuous $\Rightarrow$ $\mu$ is continuous upon zero.

April 26, 2024

Field Extensions

arima要学algebra，所以变成了algebraic-arima

Lemma 1. $[K:F]=[K:E][E:F]$，如果$K/E/F$是域扩张.

若 $[K:F]$ 有限，则称$K/F$是有限扩张.

构造

通过向域$F$中添加元素来扩张.

设 $K/F$, $S\subseteq K$，$S$是$K$的子集，$F(S)$表示$F$和$S$生成的最小扩张.

Lemma 2.
$F(S)=\{\frac{f(u_1,\dots,u_n)}{g(u_1,\dots,u_n)}: f,g\in F[x_1,\dots,x_n],g|_u\neq 0,u_i\in S\}$

若$S$有限，则称$F(S)$为$F$上的有限生成扩张.

Proof. 首先$RHS$是域.

最小$\Longrightarrow$
$F(S)\subseteq RHS$；

$RHS$是域，$F\subseteq RHS$，$S\subseteq RHS$，故$F(S)\subseteq RHS$. $\blacksquare$

Corollary 3.
如果$\alpha\in F(S)$，存在有限子集$S_0\subseteq S$，使得$\alpha\in F(S_0)$.

Lemma 4.
$F(S_1\cup S_2)=F(S_1)(S_2)=F(S_2)(S_1)$.

Proof. $F(S_1\cup S_2)$ 是
包含$F$和$S_1\cup S_2$的最小域，故$F(S_1\cup S_2)\subseteq F(S_1)(S_2)$.

$F(S_1)(S_2)$ 是包含$F(S_1)$ 和 $S_2$的最小域，故$F(S_1)(S_2)\subseteq F(S_1\cup S_2)$.
$\blacksquare$

Corollary 3 和 Lemma 4 说明，域扩张的构造是可交换的，
而且可以通过有限次的构造得到（?）.
总之，域扩张可归结为单扩张.

单扩域

$K/F$ 中至少有一个元素是超越的，则称$K/F$是超越扩域. 否则为代数扩域.
例如，域$F$上的有理函数域$F(x)=\{\frac{f}{g}:f,g\in F[x],g\neq 0\}$是超越扩域（不存在$f$使得$f(x)=0$）.