Attila Joó, Base partition for finitary-cofinitary matroid families

Room B232 IBS (기초과학연구원)

Let ${\mathcal{M} = (M_i \colon i\in K)}$ be a finite or infinite family consisting of finitary and cofinitary matroids on a common ground set $E$. We prove the following Cantor-Bernstein-type result: if $E$ can be covered by sets ${(B_i \colon i\in K)}$ which are bases in the corresponding matroids and there are also pairwise disjoint

Jaiung Jun (전재웅), The Hall algebra of the category of matroids

Room 1401, Bldg. E6-1, KAIST

To an abelian category A satisfying certain finiteness conditions, one can associate an algebra H_A (the Hall algebra of A) which encodes the structures of the space of extensions between objects in A. For a non-additive setting, Dyckerhoff and Kapranov introduced the notion of proto-exact categories, as a non-additive generalization of an exact category, which

Sanjeeb Dash, Boolean decision rules via column generation

Room B232 IBS (기초과학연구원)

In many applications of machine learning, interpretable or explainable models for binary classification, such as decision trees or decision lists, are preferred over potentially more accurate but less interpretable models such as random forests or support vector machines. In this talk, we consider boolean decision rule sets (equivalent to boolean functions in disjunctive normal form)

Ben Lund, Furstenberg sets over finite fields

Room B232 IBS (기초과학연구원)

An important family of incidence problems are discrete analogs of deep questions in geometric measure theory. Perhaps the most famous example of this is the finite field Kakeya conjecture, proved by Dvir in 2008. Dvir's proof introduced the polynomial method to incidence geometry, which led to the solution to many long-standing problems in the area.

Adam Zsolt Wagner, The largest projective cube-free subsets of $Z_{2^n}$

Room B232 IBS (기초과학연구원)

What is the largest subset of $Z_{2^n}$ that doesn't contain a projective d-cube? In the Boolean lattice, Sperner's, Erdos's, Kleitman's and Samotij's theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of $Z_2^n$ we work in $Z_{2^n}$, analogous statements hold if one

Dillon Mayhew, Courcelle’s Theorem for hypergraphs

Room B232 IBS (기초과학연구원)

Courcelle's Theorem is an influential meta-theorem published in 1990. It tells us that a property of graph can be tested in polynomial time, as long as the property can expressed in the monadic second-order logic of graphs, and as long as the input is restricted to a class of graphs with bounded tree-width. There are

Dong Yeap Kang (강동엽), Fragile minor-monotone parameters under random edge perturbation

Room B232 IBS (기초과학연구원)

We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of $H$. Our results are close to best possible for

Xin Zhang (张欣), On the equitable tree-coloring of graphs with low degeneracy

Room B232 IBS (기초과학연구원)

A (vertex) $k$-coloring of a graph $G$ is a tree-coloring if each color class induces a forest, and is equitable if the sizes of any two color classes differ by at most 1. The first relative result concerning the equitable tree-coloring of graphs is due to H. Fan, H. A. Kierstead, G. Liu, T. Molla,

Eun-Kyung Cho (조은경), Decomposition of a planar graph into a $d$-degenerate graph and a graph with maximum degree at most $h$

Room B232 IBS (기초과학연구원)

Given a graph $G$, a decomposition of $G$ is a collection of spanning subgraphs $H_1, \ldots, H_t$ of $G$ such that each edge of $G$ is an edge of $H_i$ for exactly one $i \in \{1, \ldots, t\}$. Given a positive integer $d$, a graph is said to be $d$-degenerate if every subgraph of it has

Dabeen Lee (이다빈), On a generalization of the Chvátal-Gomory closure

Room B232 IBS (기초과학연구원)

Integer programming is the problem of optimizing a linear function over the set of integer solutions satisfying a system of inequalities. The most successful technique in practice is the so-called "cutting-plane" algorithm in combination with branch-and-bound enumeration. Cutting-planes for an integer linear program are linear inequalities that are valid for all integer feasible solutions but

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.