이언배 연구노트

$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-..