기초과학연구원 이산수학그룹
The first-order model checking problem for finite graphs asks, given a graph G and a first-order sentence $\phi$ as input, to decide whether $\phi$ holds on G. Showing the existence …
We introduce an odd coloring of a graph, which was introduced very recently, motivated by parity type colorings of graphs. A proper vertex coloring of graph $G$ is said to …
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 …