이언배 연구노트

와 이젠 진짜 하나도 모르겠다...한계가 왔다... 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..

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

그래프를 종이에 그릴 수 있겠니? 선이 겹치면 헷갈리잖아. 규칙을 몇 개 정해줄게. DefinitionDrawing a multigraph두 edge 를 crossing: 공통의 internal point 가진다는 것emdgedding: crossing 이 없는 drawingplanar: multigraph 가 plane 에 embed 가능plane multigraph: multigraph 를 planar embedding 하게 그린 예시"안겹치게 잘 그려봐" Proposition$K_5$ 랑 $K_{3, 3}$ 은 planar 그래프가 아니다.5개짜리 complete graph 랑 3대3 complete bigraph 는 안겹치고는 못 그린다.$\textit{Proof}$$C$ 라는 spanning c..