학과 세미나 및 콜로퀴엄
자연과학동(E6-1) Room 1409
Discrete Math
이상준 (Emory University, Atlanta, Georgia, USA)
Dynamic coloring and list dynamic coloring of planar graphs
A dynamic coloring of a graph G is a proper coloring of the vertex set V(G) such that for each vertex of degree at least 2, its neighbors receive at least two distinct colors. A dynamic k-coloring of a graph is a dynamic coloring with k colors. Note that the gap χd(G) – χ(G) could be arbitrarily large for some graphs. An interesting problem is to study which graphs have small values of χd(G) – χ(G).
One of the most interesting problems about dynamic chromatic numbers is to find upper bounds of χd(G)$ for planar graphs G. Lin and Zhao (2010) and Fan, Lai, and Chen (recently) showed that for every planar graph G, we have χd(G)≤5, and it was conjectured that χd(G)≤4 if G is a planar graph other than C5. (Note that χd(C5)=5.)
As a partial answer, Meng, Miao, Su, and Li (2006) showed that the dynamic chromatic number of Pseudo-Halin graphs, which are planar graphs, are at most 4, and Kim and Park (2011) showed that χd(G)≤4 if G is a planar graph with girth at least 7.
In this talk we settle the above conjecture that χd≤4 if G is a planar graph other than C5. We also study the corresponding list coloring called a list dynamic coloring.
This is joint work with Seog-Jin Kim and Won-Jin Park.
본 강연은 KMRS(KIAST Math Research Station)에서 제공하는 집중 강연으로 기하학적 입장에서 유도되어지는 편미분 방정식을 소개하는 것을 목적으로 하고 있다. 이제까지 주로 연구 되어진 다양한 편미분 방정식은 주로 물리학적인 문제들에서 유도 되어진 것이다. 본 강연을 통해서 기존의 편미분 방정식을 보다 기하학적인 관점에서 이해할 뿐 아니라 기하학적인 문제를 편미분 방정식의 형태로 소개 하고자 한다. This lecture series is provided by KMRS and aiming to introduce PDEs which are derived from geometry view point. So far PDEs are mostly derived from physical view point. In these lectures PDEs will be understood in geometry view point and PDEs related to geometry will be introduced. |
본 강연은 KMRS(KIAST Math Research Station)에서 제공하는 집중 강연으로 기하학적 입장에서 유도되어지는 편미분 방정식을 소개하는 것을 목적으로 하고 있다. 이제까지 주로 연구 되어진 다양한 편미분 방정식은 주로 물리학적인 문제들에서 유도 되어진 것이다. 본 강연을 통해서 기존의 편미분 방정식을 보다 기하학적인 관점에서 이해할 뿐 아니라 기하학적인 문제를 편미분 방정식의 형태로 소개 하고자 한다.
This lecture series is provided by KMRS and aiming to introduce PDEs which are derived from geometry view point. So far PDEs are mostly derived from physical view point. In these lectures PDEs will be understood in geometry view point and PDEs related to geometry will be introduced.
본 강연은 KMRS(KIAST Math Research Station)에서 제공하는 집중 강연으로 기하학적 입장에서 유도되어지는 편미분 방정식을 소개하는 것을 목적으로 하고 있다. 이제까지 주로 연구 되어진 다양한 편미분 방정식은 주로 물리학적인 문제들에서 유도 되어진 것이다. 본 강연을 통해서 기존의 편미분 방정식을 보다 기하학적인 관점에서 이해할 뿐 아니라 기하학적인 문제를 편미분 방정식의 형태로 소개 하고자 한다.
This lecture series is provided by KMRS and aiming to introduce PDEs which are derived from geometry view point. So far PDEs are mostly derived from physical view point. In these lectures PDEs will be understood in geometry view point and PDEs related to geometry will be introduced.
본 강연은 KMRS(KIAST Math Research Station)에서 제공하는 집중 강연으로 기하학적 입장에서 유도되어지는 편미분 방정식을 소개하는 것을 목적으로 하고 있다. 이제까지 주로 연구 되어진 다양한 편미분 방정식은 주로 물리학적인 문제들에서 유도 되어진 것이다. 본 강연을 통해서 기존의 편미분 방정식을 보다 기하학적인 관점에서 이해할 뿐 아니라 기하학적인 문제를 편미분 방정식의 형태로 소개 하고자 한다.
This lecture series is provided by KMRS and aiming to introduce PDEs which are derived from geometry view point. So far PDEs are mostly derived from physical view point. In these lectures PDEs will be understood in geometry view point and PDEs related to geometry will be introduced.
본 강연은 KMRS(KIAST Math Research Station)에서 제공하는 집중 강연으로 기하학적 입장에서 유도되어지는 편미분 방정식을 소개하는 것을 목적으로 하고 있다. 이제까지 주로 연구 되어진 다양한 편미분 방정식은 주로 물리학적인 문제들에서 유도 되어진 것이다. 본 강연을 통해서 기존의 편미분 방정식을 보다 기하학적인 관점에서 이해할 뿐 아니라 기하학적인 문제를 편미분 방정식의 형태로 소개 하고자 한다.
This lecture series is provided by KMRS and aiming to introduce PDEs which are derived from geometry view point. So far PDEs are mostly derived from physical view point. In these lectures PDEs will be understood in geometry view point and PDEs related to geometry will be introduced.
자연과학동(E6-1) Room1409
Discrete Math
오수일 (The College of William and Mary, Williamsburg, Vir)
Path Cover Number in 4-regular Graphs and Hamiltonicity in Connected Regular Graphs
A path cover of a graph is a set of disjoint paths such that every vertex in the graph appears in one of the paths.
We prove an upper bound for the minimum size of a path cover in a connected
4-regular graph with n vertices, confirming a conjecture by Graffiti.pc.
We also determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we solve the analogous problem for Hamiltonian paths.
This is a partly joint work with Gexin Yu and Rui Xu.
우리나라의 역사적 기록을 토대로 우리의 선조들이 정치, 경제, 복지, 과학분야에서 어떤 업적을 이루었는지를 재조명하는 시간을 갖는다. 아래 내용은 수학과 관련된 내용의 일부이다.
洪大容(1731-1783)
수학서 <주해수용(籌解需用)>의 내용
(1) 구체의 체적이 62,208척이다. 이 구체의 지름을 구하라.
正弦=sinA 餘弦=cosA 正切=tanA 餘切=cotA
正割=secA 餘割=cosecA 正矢=1-cosA 餘矢=1-sinA
正弦 30도=sin30도=0.5
正弦 25도 42분 51초=sin25.4251。=0.4338883739118
正弦 45도=sin45=0.7070167811865
(2) 甲地와 乙地는 동일한 子午眞線에 있다. 甲地는 北極出地 37도에 있고, 乙地는 36도 30분에 있다. 甲地에서 乙地로 직선으로 가는데 고뢰(鼓擂)가 12번 울리고, 종뇨(鍾鬧)가 125번 울렸다. 이 때 지구 1度의 里數와 지구의 지름, 지구의 둘레를 구하라.
The existence of topologically slice knots that are of infinite
Nonsmooth optimization problems are generally considered to be more difficult than smooth problems. Among those, optimization problem with sparsity, which has wide applicability in machine learning, satistics, and image processing, are usually structured. Hence many efficient optimization methods have been developed to solve such problems. In this talk, we introduce several optimization problems with sparsity arising in applications and optimization methods for solve them.
We consider a well-known combinatorial search problem. Suppose that there are n identical looking coins and some of them are counterfeit. The weights of all authentic coins are the same and known a priori. The weights of counterfeit coins vary but different from the weight of an authentic coin. Without loss of generality, we may assume the weight of authentic coins is 0. The problem is to find all counterfeit coins by weighing sets of coins (queries) on a spring scale. Finding the optimal number of queries is difficult even when there are only 2 counterfeit coins.
We introduce a polynomial time randomized algorithm to find all counterfeit coins when the number of them is known to be at most m≥2 and the weight w(c) of each counterfeit coin c satisfies α≤|w(c)|≤β for fixed constants α, β>0. The query complexity of the algorithm is O((m log n)/log m), which is optimal up to a constant factor. The algorithm uses, in part, random walks.
We will also discuss the problem of finding edges of a hidden weighted graph using a certain type of queries.
I will start with a pivot-minor containment problem in graphs. A graph H is a pivot-minor of a graph G if H is obtained from G by a sequence of pivoting edges and vertex deletions. In recent, we have a question that any incidence graph of a tree does not have binary tree of depth at least 5 as a pivot-minor. This comes true and I gives two proofs it. First, I prove it by using the fact that an adjacency matrix of a tree is nonsingular if and only if it has a perfect matching. Second, I will discuss how this problem is related to a fundamental graph of a binary matroid. Then we can convert original problem into a graph minor containment problem and we can solve it.