<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.

[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: 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.