기초과학연구원 이산수학그룹
Let $\mathcal{G}$ and $\mathcal{H}$ be minor-closed graphs classes. The class $\mathcal{H}$ has the Erdős-Pósa property in $\mathcal{G}$ if there is a function $f : \mathbb{N} \to \mathbb{N}$ such that every …
Bollobás proved that for every $k$ and $\ell$ such that $k\mathbb{Z}+\ell$ contains an even number, an $n$-vertex graph containing no cycle of length $\ell \bmod k$ can contain at most …
The positive discrepancy of a graph $G$ of edge density $p$ is defined as the maximum of $e(U) - p|U|(|U|-1)/2$, where the maximum is taken over subsets of vertices in …
Delta-matroids are a generalization of matroids with connections to many parts of graph theory and combinatorics (such as matching theory and the structure of topological graph embeddings). Formally, a delta-matroid …
We say that two functors Λ and Γ between thin categories of relational structures are adjoint if for all structures A and B, we have that Λ(A) maps homomorphically to …
A family $\mathcal F$ of (di)graphs is said to have the half- or quarter-integral Erdős-Pósa property if, for any integer $k$ and any (di)graph $G$, there either exist $k$ copies …
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 …