Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems
Room B332 IBS (기초과학연구원)In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid
In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid
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
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 …
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 …
We show that if
One of the important work in graph theory is the graph minor theory developed by Robertson and Seymour in 1980-2010. This provides a complete description of the class of graphs …