기초과학연구원 이산수학그룹
The notion of convexity spaces provides a purely combinatorial framework for certain problems in discrete geometry. In the last ten years, we have seen some progress on several open problems …
We show that each perfect matching in a bipartite graph G intersects at least half of the perfect matchings in G. This result has equivalent formulations in terms of the permanent …
A family $\mathcal F$ of subsets of is called s-saturated if it contains no s pairwise disjoint sets, and moreover, no set can be added to $\mathcal F$ while preserving …
Main purpose of this talk is to introduce a connection between restriction estimates for cones and point-sphere incidence theorems in the finite field setting. First, we review the finite field …
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$, …