세미나/포럼
[세미나/포럼] [2018.3.29.목] 수학과 위상조합세미나 개최 안내
- 세미나/포럼
- 교내
- 이은지
- 2018-03-23
안녕하세요. 수학과 위상조합 세미나를 아래와 같이 개최하고자 합니다.
많은 참여부탁드립니다.
연사 : Hong Liu, University of Warwick
일시 : 3월 29일 목요일 16:00 ~ 17:00
장소 : 팔달관 621호
제목 : Edges not in any monochromatic copy of a fixed graph
초록 :
(Joint work with Oleg Pikhurko and Maryam Sharifzadeh) For a sequence $(H_i)_{i=1}^k$ of graphs, let $\rm{nim}(n;H_1,\ldots, H_k)$ denote the maximum number of edges not contained in any monochromatic copy of $H_i$ in colour $i$, for any colour $i$, over all $k$-edge-colourings of~$K_n$. When each $H_i$ is connected and non-bipartite, we introduce a variant of Ramsey number that determines the limit of $\rm{nim}(n;H_1,\ldots, H_k)/{n\choose 2}$ as $n\to\infty$ and prove the corresponding stability result. Furthermore, if each $H_i$ is what we call \emph{homomorphism-critical} (in particular if each $H_i$ is a clique), then we determine $\rm{nim}(n;H_1,\ldots, H_k)$ exactly for all sufficiently large~$n$. The special case $\rm{nim}(n;K_3,K_3,K_3)$ of our result answers a question of Ma.
For bipartite graphs, we mainly concentrate on the two-colour symmetric case (i.e., when $k=2$ and $H_1=H_2$). It is trivial to see that $\rm{nim}(n;H,H)$ is at least $\rm{ex}(n,H)$, the maximum size of an $H$-free graph on $n$ vertices. Keevash and Sudakov showed that equality holds if $H$ is the $4$-cycle
and $n$ is large; recently Ma extended their result to an infinite family of bipartite graphs. We provide a larger family of bipartite graphs for which $\rm{nim}(n;H,H)=\ex(n,H)$. For a general bipartite graph $H$, we show that $\rm{nim}(n;H,H)$ is always within a constant additive error from $\rm{ex}(n,H)$, i.e.,~$\rm{nim}(n;H,H)= \rm{ex}(n,H)+O_H(1)$.