• Date: March 13-14 (Fri-Sat), 2015
• Venue:  Room 1503, KIAS
• Invited Speakers 

                    Suyoung Choi (최수영) at Ajou Univ.
                    Mitsugu Hirasaka (히라사카) at Pusan Nat'l Univ.                     
                    Jong Yoon Hyun (현종윤) at Ewha Women's Univ.
                    Eun Jung Kim (김은정) at LAMSADE, CNRS, France
                    Seog-jin Kim (김석진) at Konkuk Univ.
                    Kyungyong Lee (이경용) at Wayne State Univ., USA
                    Sang-il Oum (엄상일) at KAIST
                    Hyenkyun Woo (우현균) at KIAS


 

• Support:   
•    (1) Meal: We provide all meals during the workshop to all participants.  
•    (2) Accommodation:   

- We support accommodations for March 13 to speakers, students, and researchers who need support.
- For speakers, we support rooms at KIASTEL near KIAS. 
- For students and researchers, the lodging expenses will be reimbursed up to KRW 44,000.
  For more information on accommodation facilities, please see Accommodation Page.
  We recommend Hotel KP near Hoegi station with rate KRW 88,000 for two persons.

- 숙박에 대하여 지원이 필요하신 학생 및 참가자분들은 키아스 외부의 숙박시설을 이용하신 후, 숙박영수증, 통장사본, 학회참가동의서 (학생의 경우)를 제출하시면 숙박비를 최대 1인당 4만4천원으로 실비 정산하여 지급하여 드립니다.

(구비서류 제출은 Workshop당일 직접 제출하시거나 또는 이메일(이수연, suyeon@kias.re.kr)로  제출가능합니다.) 
- 만일 2명이 함께 방을 이용하는 경우는 최대 8만8천원까지 실비로 지원하여 드립니다. 
 Hotel KP (Benikea, 회기역 부근)를 추천하며 2인1실을 고등과학원 제휴가로 이용할 경우 8만8천원입니다.
 

• <Schedule>
• 
  [1st Day: March 13 (Fri)]
• 
    1:55 ~ 2:00   Opening address: Jeong Han Kim 
    2:00 ~ 2:40   <Talk I>  Sang-il Oum (엄상일)
                                Partitioning $H$-minor free graphs into three subgraphs
•                               with no large components                           
    2:50 ~ 3:30   <Talk II>  Eun Jung Kim (김은정)
                                Tree-Cut width: computation and algorithmic applications
•                                                          
    3:30 ~ 4:00   Coffee Break
    4:00 ~ 4:40   <Talk III>  Seog-jin Kim (김석진)
                                Decomposition of Sparse Graphs into Forests:
•                               The Nine Dragon Tree Conjecture for k ≤ 2                           
    4:50 ~ 5:20   <Talk IV>  Hyenkyun Woo (우현균)
                                Robust Asymmetric Nonnegative Matrix Factorization                        
    5:30 ~ 6:00   <Talk V>  Jong Yoon Hyun (현종윤) 
•                               Results on bent functions
    6:00 ~              Banquet
• 
  [2nd Day: Mar 14 (Sat)] 
• 
              ~ 09:20   Breakfast
    09:20 ~ 10:00   <Talk VI>  Kyungyong Lee (이경용)
                                     Finiteness of quiver mutations                    
    10:00 ~ 10:30   Coffee Break
    10:30 ~ 11:10   <Talk VII> Mitsugu Hirasaka (히라사카) 
•                                    The number of ideals of Z[x] containing x(x − α)(x − β) 
•                                    with given index                        
    11:20 ~ 12:00   <Talk VIII> Suyoung Choi (최수영) 
•                                    Small cover and puzzle
•  

• <Abstract>
•  

• 
  <Talk 1> Sang-il Oum
  Title: Partitioning H-minor free graphs into three subgraphs with no large components 

  Abstract: We prove that for every graph H, if a graph G has no H minor, then its vertex set V (G) can be partitioned into three sets X1, X2, X3 such that for each i, the subgraph induced on Xi has no component of size larger than a function of H and the maximum degree of G. This improves a previous result of Alon, Ding, Oporowski and Vertigan [Partitioning into graphs with only small components, J. Combin. Theory Ser. B 87 (2003), 231–243] which proves that V (G) can be partitioned into four such sets. Our theorem generalizes a result of Esperet and Joret [Colouring planar graphs with three colours and no large monochromatic components, Combin. Probab. Comput. 23 (2014), 551–570], who proved it for planar graphs and asked whether it is true for graphs with no H minor. 

  As a corollary, we prove that for every positive integer t, if a graph G has no Kt+1 minor, then its vertex set V (G) can be partitioned into 3t sets X1, . . . , X3t such that for each i, the subgraph induced on Xi has no component of size larger than a function of t. This corollary improves a result of Wood [Contractibility and the Hadwiger conjecture, European J. Combin. 31 (2010), 2102–2109], which proves that V (G) can be partitioned into ⌈3.5t + 2⌉ such sets. 

  This is joint work with Chun-Hung Liu. 

•  

• 
  <Talk 2> Eunjung Kim
  Title: Tree-Cut width: computation and algorithmic applications 

  Abstract: Wollan [1] has recently introduced the graph parameter tree-cut width, which plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. Tree- cut width is known to be lower-bounded by a function of treewidth, but it can be much larger and hence has the potential to facilitate the efficient solution of problems which are not believed to be fixed-parameter tractable (FPT) when parameterized by treewidth. 

  We present a 2-approximation fpt-algorithm for the problem of deciding whether the tree-cut width is at most k: that is, given a graph G and a positive integer k, the algorithm correctly decides in time 2O(k2 log k) · n5 log n that the tree-cut width of G is strictly bigger than k, or returns a tree- cut decomposition whose width is at most 2k. Moreover, we develop the notion of nice tree-cut decompositions and show that any tree-cut decomposition can be transformed into a nice one in polynomial time. Based on this notion, we introduce a general three-stage dynamic framework for the design of FPT algorithms on nice tree-cut decompositions and apply it to several classic problems. 

  This talk is based on two disjoint results with Robert Ganian, Stefan Szeider, Sang-il Oum, Christophe Paul, Ignasi Sau and Dimitrios Thilikos. 

   

  References 

  [1] P. Wollan. The structure of graphs not admitting a fixed immersion. Journal of Combinatorial Theory, Series B, volume 110, pp.47–66 (2015) 

•  

• 
  <Talk 3> Seog-Jin Kim 
  Title: Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for k ≤ 2 

  Abstract: For a loopless multigraph $G$, the {it fractional arboricity} $Arb(G)$ is the maximum of $frac{|E(H)|}{|V(H)|-1}$ over all subgraphs $H$ with at least two vertices.  Generalizing the Nash-Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if $Arb(G)le k+frac{d}{k+d+1}$, then $G$ decomposes into $k+1$ forests with one having maximum degree at most $d$. The conjecture was previously proved for $d=k+1$ and for $k=1$ when $dle6$. We prove it for all $d$ when $kle2$, except for $(k,d)=(2,1)$.  This is joint work with Min Chen, Alexandr Kostochka, Douglas West, and Xuding Zhu.

• 
  <Talk 4> Hyenkyun Woo
  Title: Robust Asymmetric Nonnegative Matrix Factorization 

  Abstract: The problems that involve separation of grouped outliers and low rank part in a given data matrix have attracted a great attention in recent years in image analysis such as background modeling and face recogni- tion. In this talk, we introduce a new formulation called Linf-norm based robust asymmetric nonnegative matrix factorization (RANMF) for the grouped outliers and low nonnegative rank separation problems. The main advantage of Linf-norm in RANMF is that we can control denseness of the low nonnegative rank factor matrices. However, we also need to control distinguishability of the column vectors in the low non- negative rank factor matrices for stable basis. For this, we impose asymmetric constrains, i.e., denseness condition on the coefficient factor matrix only. As a byproduct, we can obtain a well-conditioned basis factor matrix. One of the advantages of the RANMF model, compared to the nuclear norm based low rank enforcing models, is that it is not sensitive to the nonnegative rank constraint parameter due to the proposed soft regularization method. This has a significant practical implication since the rank or nonnegative rank is difficult to compute and many existing methods are sensitive to the estimated rank. Numerical results show that the proposed RANMF outperforms the state-of-the-art robust principal component analysis (PCA) and other robust NMF models in many image analysis applications. 

•  

• 
  <Talk 5> Jong Yoon Hyun
  Title: Results on bent functions
  Abstract: We present results on binary bent functions in two parts. First, we derive a Gleason-type theorem on binary self-dual bent function. Next, we give an explicit criterion for the existence of binary bent functions. Moreover we extend these results to p-ary weakly regular bent functions. This is joint work with Heisook Lee, Yoonjin Lee. 

•  

• 
  <Talk 6> Kyungyong Lee
   Title: Finiteness of quiver mutations 

  Abstract: Given a quiver (directed graph) Q, we consider all quivers that are obtained from Q by sequences of mutations. The set M(Q) of such quivers is infinite in general. This was one of the main obstacles to studying quivers and their associated cluster algebras. However we define a certain subset of M(Q), which is called the fundamental collection. We conjecture that this fundamental collection is finite and has enough information for M(Q). We prove this conjecture for quivers with at most four vertices. 

•  

• 
  <Talk 7> Mitsugu Hirasaka
  Title: The number of ideals of Z[x] containing x(x − α)(x − β) with given index 

  Abstract: For a square matrix A in the full matrix ring ∈ Mn(C) of degree n over the complex numbers field C we denote by ⟨A⟩ the subring of Mn(C) generated by A. In this talk we aim to find the number of ideals of ⟨A⟩ with given index when A is the adjacency matrix of a strongly-regular graph which is not a conference graph. 

•  
• 
  <Talk 8> Suyoung Choi 
• Title: Small cover and puzzle 

  Abstract: Let K be a polytopal simplicial complex of dim n − 1 on [m], and λ : [m] → Zn2 a map satisfying that λ(i1), . . . , λ(il) are linearly independent whenever {i1, . . . , il} ∈ K. We call λ a mod 2 characteristic function over K. It is an interesting fact that there is a 1-1 correspondence between the set of mod 2 characteristic functions and the set of small covers which are important objects in toric geometry. 

  In this talk, we count mod 2 characteristic functions over a polytope obtained by a sequence of wedg- ings. In order to do this, we introduce some puzzle, and find a bijection between them. This work is jointly with Hanchul Park (KIAS).