kaist
Posts in "kaist"
Courses on Discrete Math / Graph Theory at KAIST on Spring 2026
Here is a list of some courses related to discrete mathematics and graph theory in the spring semester of 2026 at KAIST. MAS59903 Advanced Discrete Topology Mon/Wed 13:00-14:15 Andreas Holmsen Convex polytopes are fundamental geometric objects which appear in a wide variety of mathematical disciplines. In this course we give an introduction to basic methods and modern tools of polytope theory, focusing on combinatorial aspects. We will learn important examples and constructions (e.g. zonotopes, Minkowski sums, non-rational polytopes, fiber polytopes, and the Lawrence construction) and discuss important results and concepts such as Steinitz’ theorem, f-vectors, h-vectors, the upper bound theorem, and oriented matroids.
KAIST에서 2025년 가을에 열리는 이산수학/그래프이론 관련 교과목
예전에 이산수학/그래프이론 관련 교과목을 정리해서 올린 적이 있었습니다. 타 학과 특강으로 개설된 교과목을 눈여겨 보지 않을 가능성이 있어서 정리해봅니다. MAS.40077 Introduction to Graph Theory 그래프이론개론 화목 13:00-14:15 김재훈 (Jaehoon Kim) 매년 가을마다 열리는 과목입니다. MAS275나 CS204 등 이산수학 과목을 먼저 수강한 후에 듣는 것을 추천합니다. CS.49900 Special Topics in Computer Science <Algorithmic Graph Structure Theory> 월수 13:00-14:15 Sebastian Wiederrecht 그래프의 Tree-width, Branch-width, Tree-Independence Number, Clique-width, Rank-width, Directed Tree-width 등을 다룹니다. 실라버스를 보니 제 논문에 있는 Rank-width 관련 알고리듬도 다룰 듯 합니다.
KAIST에서 2025년 봄에 열리는 이산수학/그래프이론 관련 교과목
예전에 이산수학/그래프이론 관련 교과목을 정리해서 올린 적이 있었습니다. 타 학과 특강으로 개설된 교과목을 눈여겨 보지 않을 가능성이 있어서 정리해봅니다. MAS583 Advanced Graph Theory 화목 14:30-15:45 김재훈 Extremal graph theory 최신 연구에 접근할 수 있는 내용을 강의하실 걸로 생각합니다. 2020년 같은 과목 강의하실 때의 강의 노트 및 영상이 김재훈 교수님 홈페이지에 올라와 있습니다만 아마도 강의 내용은 변화가 있지 않을까 추측해봅니다. CS492C Selected Topics in Computer Science <Graph Classes, Algorithms and Logic> 화목 10:30-11:45, 김은정 그래프이론과 관련이 깊은 finite model theory 관련 내용도 배울 수 있고 sparse graph에 관한 비교적 최신 연구 내용도 소개하시는 것 같습니다. Syllabus에 언급된 주요 내용은 아래와 같습니다.
My course MAS275 Discrete Mathematics at KAIST in Spring 2022 will be moved to online (Zoom) for the first few weeks
I’ve decided to move MAS275 Discrete Mathematics online to Zoom for the first few weeks. If you are one of the registered students, then please check the Zoom link at the KLMS.
Department of Mathematical Sciences at KAIST invites applications for a tenured and tenure-track faculty position beginning from Spring 2022 to Spring 2023.
Professorships at KAIST The Department of Mathematical Sciences at KAIST invites applications for a tenured and tenure-track faculty position beginning from Spring 2022 to Spring 2023. In recent years, KAIST, one of the top research universities in Korea, has been recruiting distinguished scholars of both Korean and foreign nationalities. KAIST is located in Daejeon, a city with a population of 1.5 million, and its operation is financially supported by the Korean government. Most of the courses at KAIST are taught in English.
Non-Tenure Track Assistant Professorship at KAIST (Due: May 17) (KAIST 수리과학과 초빙교수 채용 공고)
FYI: The following advertisement is copied from the department website as well as the KMS website. The Department of Mathematical Sciences at KAIST invites applications for a non-tenure track faculty position beginning from September 1, 2019. In recent years, KAIST, one of the top research universities in Korea, has been recruiting distinguished scholars of both Korean and foreign nationalities. KAIST is located in Daejeon, a city with a population of 1.5 million, and its operation is financially supported by the Korean government. Most of the courses at KAIST are taught in English.
KAIST에서 2017년 가을에 열리는 이산수학/그래프이론 관련 교과목
2017년 가을학기 교과목 수강신청기간을 맞이하여 지난 학기에 하였던 것처럼 이번 2017년 가을학기에 열릴 이산수학/그래프이론 관련 교과목 및 기타 흥미로운 교과목을 정리해봅니다. MAS477 Introduction to Graph Theory (그래프이론개론). 월수 13:00~14:15, 엄상일 (네, 아시다시피 제가 하는 과목입니다.) 보통 매년 가을학기에 열렸으며 제가 연구년을 갔던 2013년에는 Andreas Holmsen 교수님이 강의를 하셨었고 작년에는 대수적 그래프이론 전공한 Brendan Rooney 교수님이 강의를 하였습니다. 2년만에 다시 하게 되었습니다. 그래프이론의 다양한 부분을 다룹니다. 보통 많이 생각하는 기초적인(?) 해밀턴 회로 오일러 회로 같은건 다루지 않습니다. 주요 내용을 언급하면 아래와 같습니다. 그래프 connectedness: 그래프가 얼마나 잘 연결되었는지, 그리고 한 점에서 다른 점으로 몇 개의 서로 겹치지 않가 있는지와 같은 Menger 정리 등. 그래프의 매칭: 남녀 학생을 짝지울때 써먹는(?) 홀의 결혼정리와 König의 정리, 그리고 남녀가 아닌 일반적인 그래프의 perfect matching에 관한 Tutte의 정리, 그리고 그래프의 maximum matching이 어떤 구조인지 설명하는 Gallai-Edmonds Structure 정리와 함께 Edmonds의 유명한 다항식 시간에 maximum matching 찾는 알고리듬을 다룹니다. 평면그래프: 이산수학 시간에는 정리만 배웠던 Kuratowski 정리를 엄밀하게 증명합니다. 오일러 공식 및 dual에 대해 다룹니다. 채색 문제: 4색정리5색정리를 증명합니다. List Coloring도 배우며 이를 통해 Thomassen의 다른 방식의 5색 정리 증명도 배웁니다. 그리고 perfect graph에 관한 성질도 배웁니다. Flow 문제: 채색문제의 dual이라고 할 수 있는 nowhere-zero flow에 관해 배우고 관련된 Tutte의 유명한 추측들을 다룹니다. 그외 시간에 따라 다룰 가능성이 있는 주제: Turan 정리, Hadwiger 추측, Szemeredi의 Regularity lemma, Higman의 lemma, Kruskal의 well-quasi-ordering 정리, Robertson과 Seymour의 그래프 마이너 정리 교재: 매년 R. Diestel 교수의 그래프 이론 GTM 책(http://diestel-graph-theory.com)을 교재로 지정하였으나, 올해는 참고도서로만 지정하였습니다. 책 값이 비싸다는 불평들이 있었고, 사실 수업 내용은 평행우주를 달린다는 평도 있었기에… KAIST 교내에서는 책을 온라인으로 볼 수 있습니다. https://doi.org/10.1007/978-3-662-53622-3 Syllabus MAS583C Topics in Analytic Combinatorics (해석조합론), 화목 10:30-11:45, 김동수 교수님 예전에 1학점 특강으로 잠깐 개설된 적이 있던 주제인데 이번에 처음 3학점 특강 과목으로 개설되었습니다. 학부 고년차나 대학원생의 경우 학부때 배우는 복소 과목이 어떻게 조합론에서 쓰일 수 있나 알아보는 기회가 되겠습니다. 특히 어떤 조합적 대상의 수를 asymptotic하게 새는 도구들을 배우게 된다고 보시면 됩니다. 과목을 마치게 되면 생성함수를 잘 다루게 될 것이고, 생성함수를 복소평면 위에서의 함수로 이해한 다음 singular point들을 찾아서 분석하는 기술을 습득하게 될 겁니다. 그 외에 다른 재미있는 주제가 있을 것 같습니다. 교재: 참고도서만 지정되어 있습니다. Analytic Combinatorics, Philippe Flajolet and Robert Sedgewick, Cambridge University Press, 2009 810페이지짜리 두꺼운 책입니다. 저는 16만원 넘게 주고 산 책인데, 이 책의 홈페이지에서 PDF로 다운받을 수 있습니다. Analytic Combinatorics in Several Variables, Robin Pemantle and Mark C. Wilson, 2013 역시 책의 홈페이지에서 draft 버젼의 PDF를 살펴볼 수 있습니다. 아래는 그 외에 눈 여겨 본 과목들입니다. 일부 내용은 실라버스에서 발췌한 것입니다.
Theorems covered in MAS575 Combinatorics Spring 2017
This post will give an incomplete list of theorems covered in MAS575 Combinatorics Fall 2017. This post will be continuously updated throughout this semester. (Last update: April 5, 2017.) 2017년 봄학기 MAS575 조합론 과목에서 다룬 정리들을 정리하였습니다. 빠진 것도 있습니다. 강의가 진행되면서 내용을 업데이트 하겠습니다. Graham and Pollak (1971). Proof by Tverberg (1982) The edge set E(Kn)E(K_n) of the complete graph cannot be partitioned into less than n−1n-1 copies of the edge sets of complete bipartite subgraphs. Lindström and Smet (1970). Let A1,A2,…,An+1⊆[n]A_1,A_2,\ldots,A_{n+1}\subseteq [n]. Then there exist subsets II and JJ of [n+1][n+1] such that I∪J≠∅,I∩J=∅, and ⋃i∈IAi=⋃j∈JAj. I\cup J\neq \emptyset, I\cap J=\emptyset, \text{ and }\bigcup_{i\in I}A_i =\bigcup_{j\in J} A_j. Lindström (1993) Let A1,A2,…,An+2⊆[n]A_1,A_2,\ldots,A_{n+2}\subseteq [n]. Then there exist subsets II and JJ of [n+2][n+2] such that I∪J≠∅I\cup J\neq \emptyset, I∩J=∅I\cap J=\emptyset, and ⋃i∈IAi=⋃j∈JAj and ⋂i∈IAi=⋂j∈JAj.\bigcup_{i\in I} A_i=\bigcup_{j\in J}A_j\text{ and }\bigcap_{i\in I}A_i=\bigcap_{j\in J}A_j. Larman, Rogers, and Seidel (1977) [New in 2017] Every two-distance set in Rn\mathbb R^n has at most (n+22)+n+1\binom{n+2}{2}+n+1 points. (A set of points is a two-distance set if the set of distances between distinct points has at most two values.) Blokhuis (1984) [New in 2017] Every two-distance set in Rn\mathbb R^n has at most (n+22)\binom{n+2}{2} points. Erdős (1963) Let C1,C2,…,CmC_1,C_2,\ldots,C_m be the list of clubs and each club has at least kk members. If m<2k−1m< 2^{k-1}, then such an assignment of students into two lecture halls is always possible. Erdős, Ko, and Rado (1961). Proof by Katona (1972) Let k≤n/2k\le n/2. Let F\mathcal F be a kk-uniform intersecting family of subsets of an nn-set. Then ∣F∣≤(n−1k−1).\lvert \mathcal F\rvert\le\binom{n-1}{k-1}. Fisher (1940), extended by Bose (1949). Related to de Brujin and Erdős (1948) Let kk be a positive integer. Let F\mathcal F be a family on an nn-set SS such that ∣X∩Y∣=k\lvert X\cap Y\rvert=k whenever X,Y∈FX,Y\in \mathcal F and X≠YX\neq Y. Then ∣F∣≤n\lvert \mathcal F\rvert\le n. Corollary due to de Brujin and Erdős (1948): Suppose that nn points are given on the plane so that not all are on one line. Then there are at least nn distinct lines through at least two of the nn points. Frankl and Wilson (1981). Proof by Babai (1988). If a family F\mathcal F of subsets of [n][n] is LL-intersecting and ∣L∣=s\lvert L\rvert=s, then ∣F∣≤∑i=0s(ni).\lvert \mathcal F\rvert\le \sum_{i=0}^s \binom{n}{i}. Ray-Chaudhuri and Wilson (1975). Proof by Alon, Babai, and Suzuki (1991). If a family F\mathcal F of subsets of [n][n] is uniform LL-intersecting and ∣L∣=s\lvert L\rvert=s, then ∣F∣≤(ns).\lvert \mathcal F\rvert\le \binom{n}{s}. (A family of sets is \emph{uniform} if all members have the same size.) Deza, Frankl, and Singhi (1983) Let pp be a prime. Let L⊆{0,1,2,…,p−1}L\subseteq\{0,1,2,\ldots,p-1\} and ∣L∣=s\lvert L\rvert=s.If (i) ∣A∣∉L+pZ\lvert A\rvert\notin L+p\mathbb Z for all A∈FA\in \mathcal F, (ii) ∣A∩B∣∈L+pZ\lvert A\cap B\rvert\in L+p\mathbb Z for all A,B∈FA,B\in \mathcal F, A≠BA\neq B, then ∣F∣≤∑i=0s(ni).\lvert \mathcal F\rvert\le \sum_{i=0}^s \binom{n}{i}. Alon, Babai, and Suzuki (1991) Let pp be a prime. Let kk be an integer. Let L⊆{0,1,2,…,p−1}L\subseteq \{0,1,2,\ldots,p-1\} and ∣L∣=s\lvert L\rvert=s. Assume s+k≤ns+k\le n. If (i) ∣A∣≡k∉L+pZ\lvert A\rvert\equiv k \notin L+p\mathbb Z for all A∈FA\in \mathcal F, (ii) ∣A∩B∣∈L+pZ\lvert A\cap B\rvert\in L+p\mathbb Z for all A,B∈FA,B\in \mathcal F, A≠BA\neq B, then ∣F∣≤(ns).\lvert \mathcal F\rvert\le \binom{n}{s}. Grolmusz and Sudakov (2002) [New in 2017] Let pp be a prime. Let L⊆{0,1,…,p−1}L\subseteq\{0,1,\ldots,p-1\} with ∣L∣=s\lvert L\rvert=s and k≥2k\ge 2. Let F\mathcal F be a family of subsets of [n][n] such that (i) ∣A∣∉L+pZ\lvert A\rvert\notin L+p\mathbb Z for all A∈FA\in \mathcal F and (ii) ∣A1∩A2∩⋯∩Ak∣∈L+pZ\lvert A_1\cap A_2\cap \cdots \cap A_k\rvert\in L+p\mathbb Z for every collection of kk distinct members A1,A2,…,AkA_1,A_2,\ldots,A_k of F\mathcal F. Then ∣F∣≤(k−1)∑i=0s(ni).\lvert \mathcal F\rvert\le (k-1)\sum_{i=0}^s \binom{n}{i}. Grolmusz and Sudakov (2002) [New in 2017] Let ∣L∣=s\lvert L\rvert=s and k≥2k\ge 2. Let F\mathcal F be a family of subsets of [n][n] such that ∣A1∩A2∩⋯∩Ak∣∈L\lvert A_1\cap A_2\cap \cdots \cap A_k\rvert\in L for every collection of kk distinct members A1,A2,…,AkA_1,A_2,\ldots,A_k of F\mathcal F. Then ∣F∣≤(k−1)∑i=0s(ni).\lvert \mathcal F\rvert\le (k-1)\sum_{i=0}^s \binom{n}{i}. Sperner (1928) If F\mathcal F is an antichain of subsets of an nn-set, then ∣F∣≤(n⌊n/2⌋). \lvert \mathcal F\rvert\le \binom{n}{\lfloor n/2\rfloor}. Lubell (1966), Yamamoto (1954), Meschalkin (1963) If F\mathcal F is an antichain of subsets of an nn-element set, then ∑A∈F1(n∣A∣)≤1. \sum_{A\in \mathcal F} \frac1{\binom{n}{\lvert A\rvert}}\le 1. Bollobás (1965) Let A1A_1, A2A_2, …\ldots, AmA_m, B1B_1, B2B_2, …\ldots, BmB_m be subsets on an nn-set such that (a) Ai∩Bi=∅A_i\cap B_i=\emptyset for all i∈[m]i\in[m], (b) Ai∩Bj≠∅A_i\cap B_j\neq\emptyset for all i≠ji\neq j. Then∑i=1m1(∣Ai∣+∣Bi∣∣Ai∣)≤1.\sum_{i=1}^m \frac1{\binom{\lvert A_i\rvert+\lvert B_i\rvert}{\lvert A_i\rvert}} \le 1. Bollobás (1965), extending Erdős, Hajnal, and Moon (1964) If each family of at most (r+sr)\binom{r+s}{r} edges of an rr-uniform hypergraph can be covered by ss vertices, then all edges can also be covered by ss vertices. Lovász (1977) Let A1A_1, A2A_2, …\ldots, AmA_m, B1B_1, B2B_2, …\ldots, BmB_m be subsets such that ∣Ai∣=r\lvert A_i\rvert=r and ∣Bi∣=s\lvert B_i\rvert=s for all ii and (a) Ai∩Bi=∅A_i\cap B_i=\emptyset for all i∈[m]i\in[m], (b) Ai∩Bj≠∅A_i\cap B_j\neq\emptyset for all i<ji<j. Then m≤(r+sr)m\le \binom{r+s}{r}. Let WW be a vector space over a field F\mathbb F. Let U1,U2,…,Um,V1,V2,…,VmU_1,U_2,\ldots,U_m,V_1,V_2,\ldots,V_m be subspaces of WW such that dim(Ui)=r\dim(U_i)=r and dim(Vi)=s\dim(V_i)=s for each i=1,2,…,mi=1,2,\ldots,m and (a) Ui∩Vi={0}U_i\cap V_i=\{0\} for i=1,2,…,mi=1,2,\ldots,m; (b) Ui∩Vj≠{0}U_i\cap V_j\neq\{0\} for 1≤i<j≤m1\le i<j\le m. Then m≤(r+sr)m\le \binom{r+s}{r}. Füredi (1984) Let U1,U2,…,Um,V1,V2,…,VmU_1,U_2,\ldots,U_m,V_1,V_2,\ldots,V_m be subspaces of a vector space WW over a field F\mathbb F. If dim(Ui)=r\dim(U_i)=r, dim(Vi)=s\dim(V_i)=s for all i∈{1,2,…,m}i\in\{1,2,\ldots,m\} and for some t≥0t\ge 0, (a) dim(Ui∩Vi)≤t\dim(U_i\cap V_i)\le t for all i∈{1,2,…,m}i\in\{1,2,\ldots,m\}, (b) dim(Ui∩Vj)>t\dim(U_i\cap V_j)>t for all 1≤i<j≤m1\le i<j\le m, then m≤(r+s−2tr−t)m\le \binom{r+s-2t}{r-t}. Frankl and Wilson (1981) The chromatic number of the unit distance graph of Rn\mathbb R^n is larger than 1.2n1.2^n for sufficiently large nn. Kahn and Kalai (1993) (Borsuk’s conjecture is false) Let f(d)f(d) be the minimum number such that every set of diameter 11 in Rd\mathbb R^d can be partitioned into f(d)f(d) sets of smaller diameter. Then f(d)>(1.2)df(d)> (1.2)^{\sqrt d} for large dd. Mehlhorn and Schmidt (1982) [New in 2017] For a matrix C, 2κ(C)≥rank(C)2^{\kappa(C)}\ge \operatorname{rank}(C). (Let κ(C)\kappa(C) be the minimum number of rounds in order to partition CC into almost homogeneous matrices, if in each round we can split each of the current submatrices into two either vertically or horizontally. This is a parameter related to the communication complexity.) Lovász and Saks (1993) κ(C)≤rk(C)\kappa(C)\le \operatorname{rk}(C). ? There exists a randomized protocol to decide the equality of two strings of length nn using O(logn)O(\log n) bits. The probablity of outputting an incorrect answer is less than 1/n1/n. Dvir (2009) [New in 2017] Let f∈F[x1,…,xn]f\in \mathbb F[x_1,\ldots,x_n] be a polynomial of degree at most q−1q-1 over a finite field F\mathbb F with q=∣F∣q=\lvert F\rvert elements. Let KK be a Kakeya set. If f(x)=0f(x)=0 for all x∈Kx\in K, then ff is a zero polynomial. If K⊆FnK\subseteq\mathbb F^n is a Kakeya set, then ∣K∣≥(∣F∣+n−1n)≥∣F∣nn .\lvert K\rvert\ge \binom{\lvert \mathbb F\rvert+n-1}{n} \ge \frac{\lvert F\rvert^n}{n\!}. Ellenberg and Gijswijt (2017) [New in 2017] If AA is a subset of F3n\mathbb F_3^n with no three-term arithmetic progression, then ∣A∣≤3N\lvert A\rvert\le 3N where N=∑a,b,c≥0;a+b+c=n;b+2c≤2n/3n a b c .N=\sum_{a,b,c\ge 0; a+b+c=n; b+2c\le 2n/3} \frac{n\!}{a\! b\! c\!}.Furthermore 3N≤o(2.756n)3N\le o(2.756^n). Tao (2016) [New in 2017] Let k≥2k\ge 2 and let AA be a finite set and F\mathbb F be a field. Let f:Ak→Ff:A^k\to \mathbb F be a function such that if f(x1,x2,…,xk)≠0f(x_1,x_2,\ldots,x_k)\neq 0, then x1=x2=⋯=xkx_1=x_2=\cdots=x_k. Then the slice rank of ff is equal to ∣{x:f(x,x,…,x)≠0}∣\lvert\{x: f(x,x,\ldots,x)\neq 0\}\rvert. Erdős and Rado (1960) [New in 2017] There is a function f(k,r)f(k,r) on positive integers kk and rr such that every family of kk-sets with more than f(k,r)f(k,r) members contains a sunflower of size rr. Naslund and Sawin (2016) [New in 2017] Let F\mathcal F be a family of subsets of [n][n] having no sunflower of size 33. Then ∣F∣≤3(n+1)∑k≤n/3(nk).\lvert \mathcal F\rvert\le 3(n+1)\sum_{k\le n/3}\binom{n}{k}. Alon and Tarsi (1992) Let F\mathbb F be a field and let f∈F[x1,x2,…,xn]f\in \mathbb F[x_1,x_2,\ldots,x_n]. Suppose that deg(f)=d=∑i=1ndi\deg(f)=d=\sum_{i=1}^n d_i and the coefficient of ∏i=1nxidi\prod_{i=1}^n x_i^{d_i} is nonzero. Let L1,L2,…,LnL_1,L_2,\ldots,L_n be subsets of F\mathbb F such that ∣Li∣>di\lvert L_i\rvert>d_i. Then there exist a1∈L1a_1\in L_1, a2∈L2a_2\in L_2, …\ldots, an∈Lna_n\in L_n such that f(a1,a2,…,an)≠0. f(a_1,a_2,\ldots,a_n)\neq 0. Cauchy (1813), Davenport (1935) Let pp be a prime and let A,BA,B be two nonempty subsets of Zp\mathbb{Z}_p. Then ∣A+B∣≥min(p,∣A∣+∣B∣−1).\lvert A+B\rvert\ge \min(p,\lvert A\rvert+\lvert B\rvert-1). Dias da Silva and Hamidoune (1994). A proof by Alon, Nathanson, and Ruzsa (1995). Conjecture of Erdős and Heilbronn (1964). Let pp be a prime and AA be a nonempty subset of Zp\mathbb{Z}_p. Then ∣{a+a′:a,a′∈A,a≠a′}∣≥min(p,2∣A∣−3). \lvert\{ a+a': a,a'\in A, a\neq a'\}\rvert \ge \min(p,2\lvert A\rvert-3). Alon (2000) [New in 2017] Let pp be an odd prime. For k<pk< p and every integers a1,a2,…,ak,b1,b2,…,bka_1,a_2,\ldots,a_k,b_1,b_2,\ldots,b_k, if b1,b2,…,bkb_1,b_2,\ldots,b_k are distinct, then there exists a permutation π\pi of {1,2,…,k}\{1,2,\ldots,k\} such that the sums ai+bπ(i)a_i+b_{\pi(i)} are distinct. Alon? [New in 2017] If AA is an n×nn\times n matrix over a field F\mathbb F, per(A)≠0\operatorname{per}(A)\neq 0 and b∈Fnb\in \mathbb F^n, then for every family of sets L1L_1, L2L_2, …\ldots, LnL_n of size 22 each, there is a vector x∈L1×L2×⋯×Lnx\in L_1\times L_2\times \cdots\times L_n such that (Ax)i≠bi(Ax)_i\neq b_i for all ii. Alon? [New in 2017] Let GG be a bipartite graph with the bipartition AA, BB with ∣A∣=∣B∣=n\lvert A\rvert=\lvert B\rvert=n. Let B={b1,b2,…,bn}B=\{b_1,b_2,\ldots,b_n\}. If GG has at least one perfect matching, then for every integer d1,d2,…,dnd_1,d_2,\ldots,d_n, there exists a subset XX of AA such that for each ii, the number of neighbors of bib_i in XX is not did_i. Erdős, Ginzburg, and Ziv (1961) [New in 2017] Let pp be a prime. Every sequence a1,a2,…,a2p−1a_1,a_2,\ldots,a_{2p-1} of integers contains a subsequence ai1a_{i_1}, ai2a_{i_2}, …\ldots, aipa_{i_p} such that ai1+ai2+⋯aip≡0(modp)a_{i_1}+a_{i_2}+\cdots a_{i_p}\equiv 0\pmod p. Alon, Friedland, and Kalai (1984) [New in 2017] Every (multi)graph with average degree >4>4 and maximum degree ≤5\le 5 contains a 33-regular subgraph. ? Let GG be an undirected graph. Let d(G)=maxH⊆G∣E(H)∣∣V(H)∣d(G)=\max_{H\subseteq G}\frac{\lvert E(H)\rvert}{\lvert V(H)\rvert}. Then there is an orientation of GG such that the outdegree of each vertex is at most ⌈d(G)⌉\lceil d(G)\rceil. Alon and Tarsi (1992) A simple planar bipartite graph is 33-choosable.
KAIST에서 2017년 봄에 열리는 이산수학/그래프이론 관련 교과목
2017년 봄학기 수강신청 기간이 다가왔습니다. 이번 학기에도 여러 이산수학/그래프이론 관련 교과목이 열릴 예정입니다. 수강신청에 참고할 수 있도록 정리해봅니다. MAS275 Discrete Mathematics (이산수학). 화목 14:30~16:00, 김동수 교수. 매년 봄학기마다 열리고 특별한 선수과목이 없습니다. 조합적 사고를 잘 할 수 있도록 도와주기 때문에 다른 과목을 듣기 전에 이 과목은 반드시 듣는 것을 추천합니다. MAS487 Discrete Geometry (이산기하) 화목 13:00~14:30, Andreas Holmsen 교수. 2년~3년 정도 주기로 열리고 있는 과목입니다. 국내에서는 KAIST에서만 볼 수 있는 과목으로 이산기하 전공하신 교수님으로부터 잘 배울 수 있습니다. 흥미로운 증명과 주제들이 많습니다. 마지막으로 열린 것은 2014년 봄입니다. 특별한 선수과목은 없지만 이산수학을 들어두었으면 수학적 내공이 충분하지 않을까 생각됩니다. 강의 설명:This course is an introduction to discrete geometry. We will cover basic results from packing and covering, convex polytopes, intersection patterns of convex sets, and combinatorial geometry. Our goal is to reach some key results by combining methods from linear algebra, topology, and probability. However, since this is an introductory course, all necessary notions will be introduced. The main prerequisite for this course is a basic understanding of elementary discrete mathemtaics and the n-dimensional Euclidean space. 교재: Jiří Matoušek, Lectures on Discrete Geometry (Springer, GTM 212). http://link.springer.com/book/10.1007%2F978-1-4613-0039-7 KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다. MAS480 수학특강 Algebraic Graph Theory (대수적 그래프이론), 월수 13:00~14:30, Brendan Rooney 교수. 교재: Chris Godsil, Gordon Royle, Algebraic Graph Theory, Sringer, GTM 207. http://link.springer.com/book/10.1007/978-1-4613-0163-9 KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다. KAIST에서는 적어도 최근 10년간은 열린 적이 없는 과목이고 앞으로도 언제 다시 열릴지 알 수 없는 과목입니다. Algebraic Graph Theory를 전공하였고 교재의 저자인 Chris Godsil 교수로부터 박사학위를 받은 Brendan Rooney 교수님이 강의하실 예정이라 기대가 됩니다. 중요한 선수과목은 선형대수학개론 혹은 선형대수학입니다. 행렬의 eigenvalue 관련된 내용을 숙지하고 spectral decomposition 같은 것들도 잘 알고 있으면 좋습니다. MAS575 Combinatorics (조합수학), 화목 10:30~12:00, 엄상일. 주교재: S. Jukna, Extremal Combinatorics, Springer-Verlag http://link.springer.com/book/10.1007%2F978-3-642-17364-6 KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다. 여러 기술들이 조합수학의 정리를 증명하는데 어떻게 활용되는지 다양하게 살펴봅니다. 선형대수 활용하는 방법, 다항식의 성질을 활용하는 방법, 램지 정리 관련, 확률을 활용하는 방법 등 다양한 주제를 다룹니다. 이산수학, 선형대수학개론을 수강한 학생이 듣는 것이 좋으며 가을마다 열리는 그래프이론개론을 수강했었다면 좀더 수월할 수도 있지만 내용은 독립적입니다. 2년마다 한 번씩 봄에 열리며, 학부생이나 대학원생 모두 수강 가능합니다. MAS583C 수학특론 Parameterized Algorithms and Lower Bounds (매개변수 고정 알고리즘과 하한), 수 16:00~17:30, 금 10:30~12:00, Helmut Alt 교수 및 Otfried Cheong 교수 전산학과 CS700과 교차개설된 과목입니다. 강의실도 전산학부 건물에서 열립니다. 독일 베를린자유대학 Helmut Alt 교수님이 KAIST 오셔서 강의하십니다. 강의홈페이지: http://otfried.org/courses/cs700spring2017/ 비슷한 과목은 2014년 봄에 수리과학과에서 제가 MAS583B Fixed-Parameter Algorithms라는 제목으로 연 적이 있습니다. 내용은 비슷하지 않을까 생각합니다. 그래프이론과도 관련이 많고 제 연구와도 관련이 많습니다. 교재: Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer. http://link.springer.com/book/10.1007/978-3-319-21275-3 KAIST 교내에서는 위 링크를 통해 Springer에서 책을 온라인으로 볼 수 있습니다.
5th Workshop on Graph Classes, Optimization, and Width Parameters
On Oct 2011, I organized the fifth workshop on graph classes, optimization, and width parameters (GROW2011).