기초과학연구원 이산수학그룹
Specifying a computational problem requires fixing encodings for input and output: encoding graphs as adjacency matrices, characters as integers, integers as bit strings, and vice versa. For such discrete data, the actual encoding …
We prove that if $n \geq 3$, then any family of $3n-3$ sets of matchings of size $n$ in any graph has a rainbow matching of size $n$. This improves …
Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all …
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 …
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$, …
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 …
In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.
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 …
Bouchet introduced isotropic systems in 1983 unifying some combinatorial features of binary matroids and 4-regular graphs. The concept of isotropic system is a useful tool to study vertex-minors of graphs …