Blog
News and announcements.
Posts
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에서 책을 온라인으로 볼 수 있습니다.
수학동아 연재 (2016년)
2016년부터 수학동아에 “따끈따끈한 수학”이라는 코너를 연재하기로 하였습니다. 목표는 이산수학 분야의 따끈따끈한 논문 소식들을 중학생 수준에서도 읽을만하게 적는 것입니다. 사실 그게 말처럼 쉬운 것은 아니지만요. 현재까지 실린 글과 앞으로 실릴 글을 예고하고 관련 논문을 정리했습니다. 혹시 글감으로 추천할 논문이 있으면 연락주셔도 좋습니다. 글이 길어져서 2017년 내용은 따로 분리하였습니다. 2017년 따끈따끈한 수학 내용 보기 2016년 1월호: 그래프 동형 문제 (Graph isomorphism problem) 작년 가을에 떠들석했던 그래프 동형 문제를 quasi-polynomial 시간에 풀 수 있다는 Babai 교수 결과에 대해 정리했습니다. (사실 기사 제목에 “P일까, NP일까?”로 나갔는데 잘못된 제목입니다. 정확하게는 “P일까 아닐까?” 정도가 좋겠죠. NP 대신 NP-hard라고 하든지 했어야 하는데 제목이 들어간 편집본을 꼼꼼히 검토하지 못했네요.) 이 글은 네이버캐스트에도 소개되었습니다. 논문: L. Babai, Graph Isomorphism in Quasipolynomial Time, arXiv:1512.03547, 2015. 2016년 2월호: Gyárfás 추측
KSIAM 조합론 분과 신설 소식
최근 KSIAM(한국산업응용수학회)에 조합론(Combinatorics) 분과가 신설되었습니다. 미국의 SIAM에서는 Discrete Mathematics가 예전부터 하나의 분과였는데 KSIAM에는 이제야 생기게 된 것이지요. 조합론 전공하시는 분들께서는 이번 기회에 KSIAM에 가입해주시면 좋을 것 같습니다. 가입하기 위해서는 KSIAM 홈페이지에서 가입신청을 하시고 회비를 신용카드 등으로 지불하면 됩니다. 하실때 조합론(Combinatorics) 분과를 선택해주시면 됩니다. 참고로 KSIAM 회원은 Reciprocity 계약에 의해 SIAM 회비의 30%를 할인받을 수 있습니다. 할인받는 방법은 KSIAM 홈페이지에 잘 나와 있습니다. SIAM 회비는 regular member의 경우 2015년 현재 $145이지만 Reciprocal member의 경우 $101.50입니다. 따라서 $43.50 할인되지요. 그런데 KSIAM 회비는 5만원입니다. 환율이 1150원 이상만 되더라도 $43.50이 5만원을 넘네요? SIAM 회비 매년 내시고 SIAM Conference on Discrete Mathematics 같은 학회 가시던 분들께서는 이번 기회에 KSIAM 회원 가입하시길 적극 권해드립니다.
그래프 이론 용어 우리말 번역
그래프 이론에서 널리 사용되는 용어들을 우리 말로 번역하는 적절한 표준이 아직 없습니다. 10여년 전에 성균관대 이상구 교수님께서 제작한 “그래프이론 용어사전” 웹사이트가 있습니다만, matching이나 k-connected같은 현대적이고 널리 (제) 연구에 쓰이는 그래프이론 용어가 나오지 않습니다. 오죽하면, 2000년에 고 이창우 교수님이 Introduction to Combinatorics라는 책을 쓰셨는데, 서문을 읽어보면 한국어 용어를 몰라 영어를 잘 못하는데도 불구하고 영어로 책을 쓰게 되었다고 적혀있습니다. (저도 어쩌다보니 보게 된 책일 뿐, 그래프이론 공부를 위해서는 딱히 추천하는 책은 아닙니다.)
KMO 여름학교/겨울학교 강의노트
2008년부터 대한수학회 주최 한국수학올림피아드(KMO) 여름학교와 겨울학교에서 조합수학 분야 강의를 해왔습니다. 그 중 유인물을 나눠준 적이 몇 번 있는데 그것들을 여기에 공유하고자 합니다. 2008년 제21기 겨울학교 (KAIST, 1월 7일-1월 22일) (유인물 없음) 2008년 제18기 여름학교 유인물 (KAIST, 7월 28일-8월 8일) 비둘기집의 원리와 램지 이론 / 수학적 귀납법 / 그래프이론 2009년 제19기 여름학교 (배재대, 8월 4일-8월 13일) (유인물 없음) 2010년 제23기 겨울학교 (한남대, 1월 6일-1월 21일) (유인물 없음) 2010년 제20기 여름학교 (충남대, 8월 2일-8월 13일) (유인물 없음) 2011년 제24기 겨울학교 (KAIST, 1월 6일-1월 21일) (유인물 없음) 2011년 제21기 여름학교 유인물 (KAIST, 8월 1일-8월 12일) 수학적 귀납법 2012년 제25기 겨울학교 (KAIST, 1월 4일-1월 19일) (유인물 없음) 2012년 제22기 여름학교 유인물 (충남대, 7월 26일-8월 7일) 수학적 귀납법 2013년 제26기 겨울학교 유인물 (KAIST, 1월 8일-1월 21일) partial order, well-quasi-order, Dilworth 정리, antichain 2014년 제23기 여름학교 (KAIST, 7월 23일-8월 1일) (유인물 없음) 2015년 제28기 겨울학교 유인물 (KAIST, 1월 2일-1월 15일) 확률론적 방법론 2015년 제24기 여름학교 유인물 (KAIST, 8월 3일-14일) 수학적 귀납법 2016년 제29기 겨울학교 (KAIST, 1월 6일-19일) (유인물 없음) 2016년 제25기 여름학교 (KAIST, 8월 1일-12일) (유인물 없음) 2017년 제30기 겨울학교 (KAIST, 1월 4일-17일) (유인물 없음) 2017년 제26기 여름학교 (KAIST, 7월 31일-8월 11일) (유인물 없음) 2018년 제31기 겨울학교 (KAIST, 1월 3일-1월 16일) (유인물 없음) 한편 1993년 1월에 있었던 제6기 한국수학올림피아드 겨울학교에 고등학생으로 참가하여 필기했던 노트도 공유합니다. 누락되거나 빠진 페이지가 있을 수 있습니다.
ICM2014 Satellite Conference on Extremal and Structural Graph Theory
======================================================== ICM2014 Satellite Conference on Extremal and Structural Graph Theory August 5-9, 2014 Gyeongju, South Korea http://icm2014.combinatorics.kr ======================================================== In August 2014, International Congress of Mathematicians (ICM) will be held in Korea. Before the main ICM, we would like to have a satellite conference on extremal and structural graph theory. We have an excellent list of plenary and invited speakers and we would like to ask you to consider attending this conference. We have small number of time slots for contributed talks.
Dynamic survey on rank-width
Note added on Jan. 2019: An improved version of this article has been published as a journal paper in Discrete Applied Mathematics. Dynamic survey on rank-width and related width parameters of graphs Sang-il Oum Aug 19, 2013 This is an incomplete on-going survey on rank-width and its related parameters. I intend to expand it slowly. By no means, this will be complete. Please feel free to leave comments or give me suggestions.
Mac OS에서 기본 한글 입력기 + KeyRemap4MacBook 이용 한글 입력 설정법
Mac OS X의 기본 한글입력기를 더욱 편리하게 사용하기 위해 KeyRemap4MacBook을 이용하는데 아래 설정을 private.xml 파일에 넣어두면 편리합니다. 기능 shift-space로 한영 전환이 된다. 단, 자체 한글 입력 기능이 있는 Aquamacs와 VirtualBox 같은 가상머신에서는 shift-space로 한영 전환을 하지 않는다. 한글 모드에서 ctrl 키를 누르면 일시로 영문으로 전환되도록 해두어서 한글 모드에서도 ctrl-a 같은 단축키를 편리하게 사용할 수 있다. <?xml version="1.0"?> <root> <item> <name>Shift-Space to Shift-Cmd-Space, not on Aquamacs or Virtualbox</name> <identifier>private.shift_space_toggle</identifier> <not>EMACS</not> <not>VIRTUALMACHINE</not> <autogen>--KeyToKey-- KeyCode::SPACE, VK_SHIFT, KeyCode::SPACE, ModifierFlag::OPTION_L | ModifierFlag::COMMAND_L</autogen> </item> <item> <name>Allow modifier keys in korean mode</name> <identifier>private.allow_modifier_key_in_korean</identifier> <inputmode_only>KOREAN</inputmode_only> <autogen>--KeyToKey-- KeyCode::CONTROL_L, KeyCode:: CONTROL_L, Option::KEYTOKEY_BEFORE_KEYDOWN, KeyCode::SPACE, ModifierFlag::OPTION_L | ModifierFlag::COMMAND_L, Option::KEYTOKEY_AFTER_KEYUP, KeyCode::SPACE, ModifierFlag::OPTION_L | ModifierFlag::COMMAND_L </autogen> </item> </root>
2012년 국제수학올림피아드(IMO) 참가 보고
올해로 53회를 맞는 국제수학올림피아드(International Mathematical Olympiad, IMO)는 중고등학생 나이의 학생들이 참가할 수 있는 수학경시대회 중 가장 권위 있는 국제대회이다. 매년 100여 나라가 참가하고 각 나라에서 6명까지 학생들을 참가시킬 수 있다. 이번 53회 IMO는 아르헨티나의 마르델플라타에서 열렸다. 우리나라는 1988년 호주에서 열린 29회 대회부터 참가하기 시작하였으며, 올해는 역대 최초로 참가학생 전원이 금메달을 받음과 동시에 학생들의 총점으로 세계 1위를 차지하는 좋은 결과를 냈다. 올해 참가한 학생들은 아래와 같다. 김동률(서울과학고 1), 김동효(서울과학고 3), 문한울(세종과학고 2) 박성진(서울과학고 2), 박태환(서울과학고 3), 장재원(서울과학고 3) 대표 6명에는 들지 못했지만 최종후보로 뽑혔던 그 외 7명의 학생들은 아래와 같다. 강내훈(서울과학고 3), 강승연(서울과학고 2), 김재중(서울과학고 3), 배영진(서울과학고 3) 정종욱(신천중학교 3), 지세현(서울과학고 2), 황인재(서울과학고 1) 이번 한국 대표단 단장은 대략 20년간 올림피아드 사업에 참여하시고 계신 인하대 송용진 교수님이 수고해 주셨다. 그리고 전 세계 단장들이 뽑은 IMO 자문위원회 위원(IMO AB)이신 서울대 김명환 교수님, 공동 부단장이며 올림피아드 사업에 몇 년째 봉사하고 계신 영동대 이승훈 교수님이 함께 하셨다. 나는 올해로 3번째 참가였는데, 이번에 처음으로 부단장을 맡았다. 그 외에도 채점 과정 등을 돕기 위해 2007년과 2008년 IMO에서 각각 은메달과 금메달을 받았던 서울대 수리과학부의 이수홍 학생이 참관인으로 함께 참여했다. 한편 한국과학창의재단, 한국연구재단, 그리고 교육과학기술부에서도 한 명씩 부단장팀의 일원으로 참관인을 보냈다. IMO에서는 총 2번의 시험을 이틀 연속으로 보는데, 각각 3문제를 4시간 30분 동안 시험을 치른다. 각 문제는 7점 만점으로 채점하므로 한 학생이 받을 수 있는 최대 점수는 42점이다.
올해 아벨상은 헝가리 수학자 세머레디(Szemerédi)교수
헝가리 출신 수학자 세머레디 교수(71)가 수학계의 노벨상이라고 할 수 있는 아벨상 2012년 수상자로 결정되었다. 아벨상은 수학자 아벨의 이름을 따서 노르웨이 왕실에서 매년 매우 큰 업적을 남긴 수학자에게 수여하는 상으로 6백만 노르웨이 크로네, 원화로 약 11억원의 상금이 있는 명예로운 상이며 2003년에 첫 상이 수여되었다. 2년후 서울에서 열릴 국제수학자대회(ICM)에서 수여되는 필즈상은 40세 이하의 수학자만 받을 수 있지만, 아벨상은 노벨상처럼 나이 제한이 없다. 세머레디 교수의 전공분야는 이산수학 혹은 조합수학이라 불리는데, 특히 극단 조합론(Extremal Combinatorics) 분야를 많이 연구하였다. 수많은 공저자를 가진 수학자로 잘 알려진 에르디시의 영향으로 헝가리 수학자들이 전통적으로 강한 분야이다. 200여편의 논문을 쓰고 아울러 70이 넘은 지금도 여전히 연구에 매진하는 세머레디 교수의 연구결과를 모두 소개하는 것은 매우 어렵다. 하지만 수학의 다른 분야에 비해 상대적으로 이산수학의 문제들은 풀기는 매우 어렵더라도 누구나 쉽게 이해할 수 있는 경우가 많다. 이 글에서는 세머레디의 가장 잘 알려지고 중요한 업적인 등차수열이 있을지에 관한 연구와 그 과정에서 파생되었으나 수많은 응용을 낳은 “규칙성 보조정리”라는 것에 관해 다루고자 한다.
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).