BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv4.9.9//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20191008T163000
DTEND;TZID=Asia/Seoul:20191008T173000
DTSTAMP:20191020T190428
CREATED:20190709T235022Z
LAST-MODIFIED:20190713T021557Z
UID:1072-1570552200-1570555800@dimag.ibs.re.kr
SUMMARY:Alexandr V. Kostochka\, On Ramsey-type problems for paths and cycles in dense graphs
DESCRIPTION: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 monochromatic copy of $H$. In these terms\, the above puzzle claims that the complete $6$-vertex graph $K_6$ arrows the complete $3$-vertex graph $K_3$. \nWe consider sufficient conditions on the dense host graphs $G$ to arrow long paths and even cycles. In particular\, for large $n$ we describe all multipartite graphs that arrow paths and cycles with $2n$ edges. This implies a conjecture by Gyárfás\, Ruszinkó\, Sárkőzy and Szemerédi from 2007 for such $n$. Also for large $n$ we find which minimum degree in a $(3n-1)$-vertex graph $G$ guarantees that $G$ arrows the $2n$-vertex path. This yields a more recent conjecture of Schelp. \nThis is joint work with Jozsef Balogh\, Mikhail Lavrov and Xujun Liu. \n
URL:https://dimag.ibs.re.kr/event/2019-10-08/
LOCATION:Room 1501\, Bldg. E6-1\, KAIST
CATEGORIES:Colloquium
END:VEVENT
END:VCALENDAR