기초과학연구원 이산수학그룹
This talk deals with induced minor obstructions to treewidth. The natural setup for this problem is to consider the class of graphs excluding some planar graph, and some complete bipartite graph as induced minors, and some complete graph as a subgraph. Unfortunately, such classes still contain graphs of arbitrarily large treewidth. Moreover, a result of …
The grid theorem of Robertson and Seymour can be equivalently stated using balanced separators, that are separators whose deletion leaves every component with no more than half of the vertices of the graph, as follows. Every graph that excludes some planar graph as a minor has a balanced separator of bounded size. Building on this …
We study a problem related to submodular function optimization and the exact matching problem for which we show a rather peculiar status: its natural LP-relaxation can have fractional optimal vertices, but there is always also an optimal integral vertex, which we can also compute in polynomial time. More specifically, we consider the multiplicative assignment problem …
A family of sets in $$ is called an $\ell$-Oddtown if the sizes of all sets are not divisible by $\ell$, but the sizes of pairwise intersections are divisible by $\ell$. The problem was completely solved when $\ell$ is a prime via an elegant linear algebraic method, showing that the family has size at most …