기초과학연구원 이산수학그룹
For the past few years, I've been working on formalizing proofs in matroid theory using the Lean proof assistant. This has led me to many interesting and unexpected places. I'll …
Every (finite) matroid consists of a (finite) set called the ground set, and a collection of distinguished subsets called the independent sets. A classic example arises when the ground set …
In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2$ suffices, which …
An edge-colored graph $H$ is called rainbow if all of its edges are given distinct colors. An edge-colored graph $G$ is then called rainbow $H$-free when no copy of $H$ in …
We prove the following variant of Helly’s classical theorem for Hamming balls with a bounded radius. For $n > t$ and any (finite or infinite) set $X$, if in a …
We say that a 0-1 matrix A contains another such matrix (pattern) P if P can be obtained from a submatrix of A by possibly changing a few 1 entries …
Rödl and Ruciński established Ramsey's theorem for random graphs. In particular, for fixed integers $r$, $\ell\geq 2$ they showed that $n^{-\frac{2}{\ell+1}}$ is a threshold for the Ramsey property that every …
In general, random walks on fractal graphs are expected to exhibit anomalous behaviors, for example heat kernel is significantly different from that in the case of lattices. Alexander and Orbach …
This talk will first introduce combinatorics on permutations and patterns, presenting the basic notions and some fundamental results: the Marcus-Tardos theorem which bounds the density of matrices avoiding a given …
A classical problem in combinatorial geometry, posed by Erdős in 1946, asks to determine the maximum number of unit segments in a set of $n$ points in the plane. Since …