기초과학연구원 이산수학그룹
In this talk we shall discuss how quickly the genus of the Erdős-Rényi random graph grows as the number of edges increases and how dramatically a small number of random edges can increase the genus of a randomly perturbed graph. (Joint work with Chris Dowden and Michael Krivelevich)
Given a graph $G$, we define $\textrm{ex}_c(G)$ to be the minimum value of $t$ for which there exists a constant $N(t,G)$ such that every $t$-connected graph with at least $N(t,G)$ vertices contains $G$ as a minor. The value of $\textrm{ex}_c(G)$ is known to be tied to the vertex cover number $\tau(G)$, and in fact $\tau(G)\leq …
Let $F$ and $H$ be graphs. The subgraph counting function $\operatorname{ex}(n,H,F)$ is defined as the maximum possible number of subgraphs $H$ in an $n$-vertex $F$-free graph. This function is a direct generalization of the Turán function as $\operatorname{ex}(n,F)=\operatorname{ex}(n,K_2,F)$. The systematic study of $\operatorname{ex}(n,H,F)$ was initiated by Alon and Shikhelman in 2016 who generalized several classical …
Given a graph $G$, there are several natural hypergraph families one can define. Among the least restrictive is the family $BG$ of so-called Berge copies of the graph $G$. In this talk, we discuss Turán problems for families $BG$ in $r$-uniform hypergraphs for various graphs $G$. In particular, we are interested in general results in …
A well-known Ramsey-type puzzle for children is to prove that among any 6 people either there are 3 who know each other or there are 3 who do not know each other. More generally, a graph $G$ arrows a graph $H$ if for any coloring of the edges of $G$ with two colors, there is a …
A graph or graph property is $\ell$-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting $\ell$ vertices. Apart from the famous Graph Reconstruction Conjecture, Kelly conjectured in 1957 that for each $\ell\in\mathbb N$, there is an integer $n=n(\ell)$ such that every graph with at least $n$ vertices is $\ell$-reconstructible. We show that for …
For a graph $H$ and an integer $k\ge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $m\ge4 $ vertices. For odd cycles, Bondy and Erd\H{o}s in 1973 conjectured that …
For a graph $H$, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$, $p\geq e(H)$, denoted by $t_H(W)$. One may then define corresponding functionals $\|W\|_{H}:=|t_H(W)|^{1/e(H)}$ and $\|W\|_{r(H)}:=t_H(|W|)^{1/e(H)}$ and say that $H$ is (semi-)norming if $\|.\|_{H}$ is a (semi-)norm and that $H$ is weakly norming if $\|.\|_{r(H)}$ is …
Focus Session @ 2019 KMS Annual MeetingA focus session "Extremal and Structural Graph Theory" at the 2019 KMS Annual Meeting is organized by Sang-il Oum. URL: http://www.kms.or.kr/meetings/fall2019/SpeakersIlkyoo Choi (최일규), Hankuk University of Foreign StudiesKevin Hendrey, IBS Discrete Mathematics GroupPascal Gollin, IBS Discrete Mathematics GroupJaehoon Kim (김재훈), KAISTRingi Kim (김린기), KAISTSeog-Jin Kim (김석진), Konkuk UniversityO-joung Kwon (권오정), Incheon …
Given a cardinal $\lambda$, a $\lambda$-packing of a graph $G$ is a family of $\lambda$ many edge-disjoint spanning trees of $G$, and a $\lambda$-covering of $G$ is a family of spanning trees covering $E(G)$.We show that if a graph admits a $\lambda$-packing and a $\lambda$-covering then the graph also admits a decomposition into $\lambda$ many spanning …