기초과학연구원 이산수학그룹
We prove that for every graph F with at least one edge there are graphs H of arbitrarily large chromatic number and the same clique number as F such that …
In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid $N$, we prove a complexity dichotomy for the problem $\rm{Hom}_\mathbb{M}(N)$ of deciding if …
The upper tail problem for subgraph counts in the Erdos-Renyi graph, introduced by Janson-Ruciński, has attracted a lot of attention. There is a class of Gibbs measures associated with subgraph …
Hadwiger's transversal theorem gives necessary and sufficient conditions for the existence of a line transversal to a family of pairwise disjoint convex sets in the plane. These conditions were subsequently …
We present a canonical way to decompose finite graphs into highly connected local parts. The decomposition depends only on an integer parameter whose choice sets the intended degree of locality. …
For a set $X$ of points $x(1)$, $x(2)$, $\ldots$, $x(n)$ in some real vector space $V$ we denote by $T(X,r)$ the set of points in $X$ that belong to the …
Reconfiguration is about changing instances in small steps. For example, one can perform certain moves on a Rubik's cube, each of them changing its configuration a bit. In this case, …
Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class C can be FO-transduced from a …
KSIAM (Korean Society for Industrial and Applied Mathematics) will have the KSIAM 2022 Spring Conference at the Institute for Basic Science (IBS). Its academic session for Combinatorics decided to have an …
SATNet is a differentiable constraint solver with a custom backpropagation algorithm, which can be used as a layer in a deep-learning system. It is a promising proposal for bridging deep …
