### Boram Park (박보람), Odd coloring of sparse graphs

Room B232 IBS (기초과학연구원)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 …

Skip to content
#
Discrete Math Seminar

##

###
Boram Park (박보람), Odd coloring of sparse graphs

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

###
Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems

Room B332
IBS (기초과학연구원)
###
Kyeongsik Nam (남경식), Large deviations for subgraph counts in random graphs

Room B332
IBS (기초과학연구원)
###
Andreas Holmsen, A colorful version of the Goodman-Pollack-Wenger transversal theorem

Room B332
IBS (기초과학연구원)
###
Stijn Cambie, The precise diameter of reconfiguration graphs

Room B332
IBS (기초과학연구원)
###
Hongseok Yang (양홍석), Learning Symmetric Rules with SATNet

Room B332
IBS (기초과학연구원)
##

###
Amadeus Reinald, Twin-width and forbidden subdivisions

Room B332
IBS (기초과학연구원)
###
Ben Lund, Radial projections in finite space

Room B332
IBS (기초과학연구원)
##

###
Eric Vigoda, Computational phase transition and MCMC algorithms

Room B332
IBS (기초과학연구원)
###
Kevin Hendrey, Product Structure of Graph Classes with Bounded Treewidth

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

Loading view.

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 …

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 …

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, …

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 …

Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width, problems expressible in FO logic can be solved in FPT time when provided …

Given a set $E$ and a point $y$ in a vector space over a finite field, the radial projection $\pi_y(E)$ of $E$ from $y$ is the set of lines that …

This talk will highlight recent results establishing a beautiful computational phase transition for approximate counting/sampling in (binary) undirected graphical models (such as the Ising model or on weighted independent sets). The computational problem is to …

The strong product $G\boxtimes H$ of graphs $G$ and $H$ is the graph on the cartesian product $V(G)\times V(H)$ such that vertices $(v,w)$ and $(x,y)$ are adjacent if and only …