BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//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
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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221201T100000
DTEND;TZID=Asia/Seoul:20221201T110000
DTSTAMP:20260418T205808
CREATED:20221016T112526Z
LAST-MODIFIED:20240707T074433Z
UID:6354-1669888800-1669892400@dimag.ibs.re.kr
SUMMARY:Cosmin Pohoata\, Convex polytopes from fewer points
DESCRIPTION:Finding the smallest integer $N=ES_d(n)$ such that in every configuration of $N$ points in $\mathbb{R}^d$ in general position\, there exist $n$ points in convex position is one of the most classical problems in extremal combinatorics\, known as the Erdős-Szekeres problem. In 1935\, Erdős and Szekeres famously conjectured that $ES_2(n)=2^{n−2}+1$ holds\, which was nearly settled by Suk in 2016\, who showed that $ES_2(n)≤2^{n+o(n)}$. We discuss a recent proof that $ES_d(n)=2^{o(n)}$ holds for all $d≥3$. Joint work with Dmitrii Zakharov.
URL:https://dimag.ibs.re.kr/event/2022-12-01/
LOCATION:Zoom ID: 224 221 2686 (ibsecopro)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221215T100000
DTEND;TZID=Asia/Seoul:20221215T110000
DTSTAMP:20260418T205808
CREATED:20221109T130647Z
LAST-MODIFIED:20240707T074155Z
UID:6454-1671098400-1671102000@dimag.ibs.re.kr
SUMMARY:Maya Sankar\, Homotopy and the Homomorphism Threshold of Odd Cycles
DESCRIPTION:Fix $r \ge 2$ and consider a family F of $C_{2r+1}$-free graphs\, each having minimum degree linear in its number of vertices. Such a family is known to have bounded chromatic number; equivalently\, each graph in F is homomorphic to a complete graph of bounded size. We disprove the analogous statement for homomorphic images that are themselves $C_{2r+1}$-free. Specifically\, we construct a family of dense $C_{2r+1}$-free graphs with no $C_{2r+1}$-free homomorphic image of bounded size. This provides the first nontrivial lower bound on the homomorphism threshold of longer odd cycles and answers a question of Ebsen and Schacht. \nOur proof relies on a graph-theoretic analogue of homotopy equivalence\, which allows us to analyze the relative placement of odd closed walks in a graph. This notion has surprising connections to the neighborhood complex\, and opens many further interesting questions.
URL:https://dimag.ibs.re.kr/event/2022-12-15/
LOCATION:Zoom ID: 224 221 2686 (ibsecopro)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR