KIAS Combinatorics Workshop Series 
7th Workshop  Home > 7th Workshop 
 Date: March 1314 (FriSat), 2015
 Venue: Room 1503, KIAS
 Invited Speakers
Mitsugu Hirasaka (히라사카) at Pusan Nat'l Univ.
Jong Yoon Hyun (현종윤) at Ewha Women's Univ.
Eun Jung Kim (김은정) at LAMSADE, CNRS, France
Seogjin Kim (김석진) at Konkuk Univ.
Kyungyong Lee (이경용) at Wayne State Univ., USA
Sangil Oum (엄상일) at KAIST
Hyenkyun Woo (우현균) at KIAS
 Support:
 (1) Meal: We provide all meals during the workshop to all participants.
 (2) Accommodation:
 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천원으로 실비 정산하여 지급하여 드립니다.
 만일 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> Sangil Oum (엄상일)
Partitioning $H$minor free graphs into three subgraphs with no large components
2:50 ~ 3:30 <Talk II> Eun Jung Kim (김은정)
TreeCut width: computation and algorithmic applications 
3:30 ~ 4:00 Coffee Break
4:00 ~ 4:40 <Talk III> Seogjin 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> Sangil Oum
Title: Partitioning Hminor 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 ChunHung Liu.

<Talk 2> Eunjung Kim
Title: TreeCut width: computation and algorithmic applicationsAbstract: Wollan [1] has recently introduced the graph parameter treecut 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 lowerbounded 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 fixedparameter tractable (FPT) when parameterized by treewidth.
We present a 2approximation fptalgorithm for the problem of deciding whether the treecut 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 treecut 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 treecut decompositions and show that any treecut decomposition can be transformed into a nice one in polynomial time. Based on this notion, we introduce a general threestage dynamic framework for the design of FPT algorithms on nice treecut decompositions and apply it to several classic problems.
This talk is based on two disjoint results with Robert Ganian, Stefan Szeider, Sangil 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> SeogJin Kim
Title: Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for k ≤ 2Abstract: 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 NashWilliams 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 FactorizationAbstract: 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 Linfnorm based robust asymmetric nonnegative matrix factorization (RANMF) for the grouped outliers and low nonnegative rank separation problems. The main advantage of Linfnorm 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 wellconditioned 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 stateoftheart 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 Gleasontype theorem on binary selfdual bent function. Next, we give an explicit criterion for the existence of binary bent functions. Moreover we extend these results to pary weakly regular bent functions. This is joint work with Heisook Lee, Yoonjin Lee.

<Talk 6> Kyungyong Lee
Title: Finiteness of quiver mutationsAbstract: 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.

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 stronglyregular graph which is not a conference graph.
<Talk 7> Mitsugu Hirasaka
Title: The number of ideals of Z[x] containing x(x − α)(x − β) with given index
<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 11 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).