기초과학연구원 이산수학그룹
In 2017, Aharoni proposed the following generalization of the Caccetta-Häggkvist conjecture for digraphs. If G is a simple n-vertex edge-colored graph with n color classes of size at least r, …
A cross-cap drawing of a graph G is a drawing on the sphere with g distinct points, called cross-caps, such that the drawing is an embedding except at the cross-caps, …
Very little is known about critical properties of graphs in the hierarchy of monotone classes, i.e. classes closed under taking (not necessarily induced) subgraphs. We distinguish four important levels in …
Two-way online correlated selection (two-way OCS) is an online algorithm that, at each timestep, takes a pair of elements from the ground set and irrevocably chooses one of the two …
A vertex colouring of a hypergraph is $c$-strong if every edge $e$ sees at least $\min\{c, |e|\}$ distinct colours. Let $\chi(t,c)$ denote the least number of colours needed so that …
We will discuss recent progress on the topic of induced subgraphs and tree-decompositions. In particular this talk with focus on the proof of a conjecture of Hajebi that asserts that …
We provide new constructions of families of quasi-random graphs that behave like Paley graphs but are neither Cayley graphs nor Cayley sum graphs. These graphs give a unified perspective of …
Since the introduction of cluster algebras by Fomin and Zelevinsky in 2002, there has been significant interest in cluster algebras of surface type. These algebras are particularly noteworthy due to …
Tropical geometry replaces usual addition and multiplication with tropical addition (the min) and tropical multiplication (the sum), which offers a polyhedral interpretation of algebraic variety. This talk aims to pitch …
For a given hypergraph $H$ and a vertex $v\in V(H)$, consider a random matching $M$ chosen uniformly from the set of all matchings in $H.$ In $1995,$ Kahn conjectured that …