기초과학연구원 이산수학그룹
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 $G$ is rainbow. With this, we define a graph $G$ to be rainbow $H$-saturated when there is some proper edge-coloring of $G$ which is rainbow $H$-free, …
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 …
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 to 0. The main question of this theory is to estimate the maximal number of 1 entries in an n by n 0-1 matrix NOT …
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 …
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 pattern, and the Guillemot-Marx algorithm for pattern detection using the notion now known as twin-width. I will then present a decomposition result: permutations avoiding a …
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 then a great variety of extremal problems in finite planar point sets have been studied. Here, we look at such questions concerning triangles. Among others …
We will give an overview of the recent attempts of building a structure theory for graphs centered around First-Order transductions: a notion of containment inspired by finite model theory. Particularly, we will speak about the notions of monadic dependence and monadic stability, their combinatorial characterizations, and the developments on the algorithmic front.
Ehrhart theory is the study of lattice polytopes, specifically aimed at understanding how many lattice points are inside dilates of a given lattice polytope, and the study has a wide range of connections ranging from coloring graphs to mirror symmetry and representation theory. Recently, we introduced new algebraic tools to understand this theory, and resolve …
In 2005, Bollobás, Janson and Riordan introduced and extensively studied a general model of inhomogeneous random graphs parametrised by graphons. In particular, they studied the emergence of a giant component in these inhomogeneous random graphs by relating them to a broad collection of inhomogeneous Galton-Watson branching processes. Fractional isomorphism of finite graphs is an important …