이언배 연구노트

$n$ 개의 vertex가 있다고 했을 때,  edge가 있을 확률을 $p$라고 주자. 이 자체가 probability space야.Definition.$q_n$: property $Q$ 가 probability space $\Omega_n$ 내에서 성립할 확률. Property $Q$ 는 $\lim_{n \rightarrow \infty} q_n = 1$일 때 거의 (almost always) 성립probability space $G(n, p)$: $p$ 를 $n$에 대한 function 이라고 했을 때, edge가 $p$ 확률로 있을 확률 공간, independently at random. 그래프 자체를 하나의 probability space 로 본 것. 또, 이 probability space로 만..

선형대수와 그래프 이론을 요렇게 조렇게 막 섞어서 다양한 성질을 살펴보자.왜냐하면, graph 는 finite vertices 의 binary relation 이기 때문이다. Definition.The adjacency matrix $A_{i, j} = \begin{cases}1 & \textit{ if } ij \in E(G) \\ 0 & \textit{otherwise} \end{cases}$i랑 j 가 edge로 이어졌니?The incidence matrix $B_{i,e} = \begin{cases}1 & \textit{ if } i \in e \\ 0 & \textit{otherwise} \end{cases}$vertex $i$ 가 edge $j$ 안에 들어가있니? Degree matrix $D..

10.1. The extremal numbers. graph 의 parameter 와 structure. 그래프에 관련된 수 (엣지, 노드 갯수)와 그래프의 구조를 연결시키는 그래프 이론.예를 들면, n-vertex graph 의 엣지 갯수가 삼각형의 갯수를 어떻게 보장할까? 뭐 이런.심플하게 생각하면, edge가 많을수록 삼각형도 많겠지. no triangle이 되게 하는 엣지의 최대 갯수는 몇 개일까? 이런 질문들이 가능.Definitionextremal number, Turan number, $ex(n, F)$: n짜리 그래프가 $F$ 를 subgraph로 갖지 않는 최대의 엣지 갯수. 엣지는 최대한 그리는데, F는 없게.Turan graph, $T_r(n)$: balanced complete r-..

와 이젠 진짜 하나도 모르겠다...한계가 왔다... 9.1. Basic probabilistic method Definition.descrete probability space: 유한하거나 가산인 set $S$ 와 function $P$ 로 정의된 subsets of $S$ 에서$A \subseteq S$ 면 $0 \leq P(A) \leq 1$ 이다.$P(S) =1$ 이고$A_1, A_2, ..., $가 $S$의 pairwise disjoint subset이라면, $P(\cup A_i) = $\sum_{i=1}^{\infinity}P(A_i)$ 다. Theorem $R(k, k) > \frac{k2^{k/2}}{e\sqrt{2}}$\textit{Proof}$잘은 모르겠는데, $K_n$짜리 그래프의 e..

Organized patterns must appear in large chaotic system.엮자면 다 엮을 수 있다. Definitionhypergraph: edge 가 $V(H)$의 subset 인 그래프. 어떻게든 엮어본 vertex들끼리 이어보면 나오는 그래프. r-uniform: 모든 edge의 size가 r. 어떻게든 엮어본 그룹 사이즈가 다 r.complete r-uniform hypergraph: 모든 r-subset 에 edge 들로 구성된 그래프. 어떻게든 엮어본 그룹에 다 edge 있음Graph 는 2-uniform hypergraphs. 2개의 vertices 사이에 다 edge가 있잖아.hyper graph is simple: $e \subseteq e'$ 인데 $e, e' ..

7.3. Coloring planar graphs색칠 가능? Heawood proved planar graph 는 5-colorable 가능. Definitionk-critical: k-chromatic graph 의 모든 적당한 subgraph 가 $(k-1)$-colorable. edge를 하나 날려도 여전히 k-colorable? 또 날려도 k-colorable?? 그럼 k-1 될 떄 까지 날려! 하고 남은 graph. Fact.k-critical graph 는 $\delta(G) \geq k-1$을 만족해야 한다. Theorem 모든 planar graph $\Rightarrow$ 5-colorable.$\textit{Proof}$planar graph 의 subgraph 는 planar하다. 그..

5.4. Connectivity and independent paths Definition$x,y$-separating set: $S \subseteq V(G)-\{x, y\}$ 이고, $xy \notin E(G)$ 일 떄 $G-S$에 $x,y$-path가 없게 하는 vertex set. $x$에서 $y$로 가는 길을 끊으려면 필요한 vertex 모임$\kappa(x, y)$: minimum size of the $x,y$-seperating set. $x,y$ 로 가는 길 막으려면 최소 몇 개 vertex 뽑아야 함?Paths from x to y are independent: share no internal vertex , vertex 안겹치게 x에서 y로 가는 경로들$\lambda(x, y)$: m..

그래프가 "잘 연결되어있다", "더 연결되어있다" 란 무슨 의미일까. 5.1 Connectivity Definition.Seperating set, vertex cut: a set $S \subseteq V(G)$ that $G-S$가 하나 이상의 component를 갖게 하는. 빼면 component가 늘어나게 되는 애들.k-connected: $k$개보다 vertex가 많고, 모든 seperating set 이 사이즈가 최소 $k$다. 뭘 떼내려면 최소 $k$개 이상의 vertex는 뽑아야 한다.Connectivity of $G$ : G가 k-connected가 되게 하는 최대의 $k$.  Fact.$K_n$의 경우, separating set 이 없다. 뭘 뽑아도 다 연결되어있음. 하지만 maxim..