BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230802T163000
DTEND;TZID=Asia/Seoul:20230802T173000
DTSTAMP:20260419T022146
CREATED:20230506T225557Z
LAST-MODIFIED:20240705T163040Z
UID:7156-1690993800-1690997400@dimag.ibs.re.kr
SUMMARY:Daniel Kráľ\, High chromatic common graphs
DESCRIPTION:Ramsey’s Theorem guarantees for every graph H that any 2-edge-coloring of a sufficiently large complete graph contains a monochromatic copy of H. As probabilistic constructions often provide good bounds on quantities in extremal combinatorics\, we say that a graph H is common if the random 2-edge-coloring asymptotically minimizes the number of monochromatic copies of H. This notion goes back to the work of Erdős in the 1960s\, who conjectured that every complete graph is common. The conjecture was disproved by Thomason in the 1980s\, however\, a classification of common graphs remains one of the most intriguing problems in extremal combinatorics. \nSidorenko’s Conjecture (if true) would imply that every bipartite graph is common\, and in fact\, no bipartite common graph unsettled for Sidorenko’s Conjecture is known. Until Hatami et al. showed that a 5-wheel is common about a decade ago\, all graphs known to be common had chromatic number at most three. The existence of a common graph with chromatic number five or more has remained open for three decades. \nWe will present a construction of (connected) common graphs with arbitrarily large chromatic number. At the end of the talk\, we will also briefly discuss the extension of the notion to more colors and particularly its relation to Sidorenko’s Conjecture. \nThe main result presented in the talk is based on joint work with Jan Volec and Fan Wei.
URL:https://dimag.ibs.re.kr/event/2023-08-02/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR