기초과학연구원 이산수학그룹
Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph $G$ is called $F$-saturated if $G$ does not contain a subgraph isomorphic to $F$, but …
We propose a theoretical analysis of recommendation systems in an online setting, where items are sequentially recommended to users over time. In each round, a user, randomly picked from a …
Corneil, Olariu, and Stewart presented a recognition algorithm for interval graphs by six graph searches. Li and Wu simplified it to only four. The great simplicity of the latter algorithm …
In 1975, Erdős asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, …
The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of …
We show that that the maximum number of of edges in a $3$-uniform hypergraph without a Berge-cycle of length four is at most $(1+o(1)) \frac{n^{3/2}}{\sqrt{10}}$. This improves earlier estimates by …
A pure pair in a graph G is a pair of subsets A, B of the vertex set of G such that in G, either all of the edges or …
In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.
For a graph G and an integer d, the dth power of G is the graph $G^d$ on the same vertex set as G where two vertices are considered adjacent …
Ordered Ramsey numbers were introduced in 2014 by Conlon, Fox, Lee, and Sudakov. Their results included upper bounds for general graphs and lower bounds showing separation from classical Ramsey numbers. We …