이언배 연구노트

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

job assignment problem 을 생각해보자.총 n 개의 job 이 있고, set $A$ 만큼의 지원자가 있다고 하자.$A$ 중에서 $A_i$ 가 $i$ 번째 직종에 지원 가능하다고 했을 때, $A_1$ 부터 $A_n$ 까지 각각 한명씩 매칭시킨 $x_1$ 부터 $x_n$ 을 찾을 수 있다.이게 대표적인 system of distinct representatives 문제. Definition.A matching: a set of pairwise non-incident edges (independent edges): vertex가 안겹치는 edge 들의 set.matching covers the vertices: matching 에 포함되는 edge 들에 닿은 vertex 들.perfect m..

6.4. List coloring and Brooks' TheoremDefinitionlist assignment (L): a function on $V(G)$ such that $L(v)$ 가 $v$에게 'acceptable' 한 색상 set이다. $v$ 가 가질 수 있는 색상의 리스트 매핑L-coloring: $f(v) \in L(v)$ for all $v$. 모든 $v$ 가 가질 수 있는 색상 리스트 L 내에서 적절히 골라갈 수 있다.k-choosable : L-coloring whenever $|L(v)| \geq k$ for all $v$. 색상 리스트가 모두 $k$개 이상인 상태에서 L-coloring 이 가능.list chromatic number / choice number / choosa..

Definitionwalk: sequence $v_1v_2...v_k$  of vertices and a sequence of edges $v_iv_{i+1} \in E(G)$. edge 로 건너건너Closed walk: $v_1 =v+k$. 어찌되었건 건너건너 돌아옴trail: all edges are distinct. Edge 안겹치고 건너건너closed trail: Edge 안겹치고 건너건너 돌아옴path: all vertices are distinct. Vertex 안겹치고 건너건너Cycle: closed walk 인데 vertex 안겹치고 건너건너 돌아옴.Length of the walk: k-1 G is connected: all pairs $u, v \in V(G)$, there is a p..

Definition.Graph G: a pair (V, E)V(G): a set of verticesE(G): a multiset of edges$|G| = |V(G)|$: the order of G: order 은 vertex 갯수$e(G) = |E(G)|$: the size of G: size 는 edge 갯수Loop: an edge of size 1graph 가 simple 하다: loop 나 multiple edge가 없다 u 와 v 가 adjacent: $uv \in E(G)$. 둘 사이 edge가 있다v 와 e가 incident: $v \in e$, edge 중 하나에 포함된다e 와 e'가 incident: $e \cap e' \neq \emptyset$ e랑 e' 는 공통의 vertex를 가..