기초과학연구원 이산수학그룹
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 family of Hamming balls of radius $t$ in $X$, every subfamily of at most $2^{t+1}$ balls have a common point, so do all members of …
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 $r$-colouring of the edges of the binomial random graph $G(n,p)$ yields a monochromatic copy of $K_\ell$. We investigate how this result extends to arbitrary colourings …
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 in 1982 conjectured that random walks on critical percolation, a prominent example of fractal graphs, exhibit mean field behavior; for instance, its spectral dimension is …