기초과학연구원 이산수학그룹
In an n-vertex graph, there must be a clique or stable set of size at least $C\log n$, and there are graphs where this bound is attained. But if we look at …
The canonical tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In …
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 …
An immersion of a graph H into a graph G sends edges of H into edge-disjoint trails of G. We say the immersion is flooding if every edge of G …
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 …
For a positive integer t and a graph G, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most …
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 …
A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős, Faber, and Lovász in 1972, states that the chromatic …
In the "cake partition" problem n players have each a list of preferred parts for any partition of the interval ("cake") into n sub-intervals. Woodall, Stromquist and Gale proved independently that under mild …
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 …