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:20260419T164405
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:20221206T163000
DTEND;TZID=Asia/Seoul:20221206T173000
DTSTAMP:20260419T164405
CREATED:20220908T152618Z
LAST-MODIFIED:20240707T074218Z
UID:6153-1670344200-1670347800@dimag.ibs.re.kr
SUMMARY:Giannos Stamoulis\, Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
DESCRIPTION:The disjoint paths logic\, FOL+DP\,  is an extension of First Order Logic (FOL) with the extra atomic predicate $\mathsf{dp}_k(x_1\,y_1\,\ldots\,x_k\,y_k)\,$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i\,$ for $i\in \{1\,\ldots\, k\}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every minor-closed graph class\, model-checking for FOL+DP can be done in quadratic time. We also introduce an extension of FOL+DP\, namely the scattered disjoint paths logic\, FOL+SDP\, where we further consider the atomic predicate $\mathsf{s-sdp}_k(x_1\,y_1\,\ldots\,x_k\,y_k)\,$ demanding that the disjoint paths are within distance bigger than some fixed value $s$. Using the same technique we prove that model-checking for FOL+SDP can be done in quadratic time on classes of graphs with bounded Euler genus.\nJoint work with Petr A. Golovach and Dimitrios M. Thilikos.
URL:https://dimag.ibs.re.kr/event/2022-12-06/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221215T100000
DTEND;TZID=Asia/Seoul:20221215T110000
DTSTAMP:20260419T164405
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
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221228T163000
DTEND;TZID=Asia/Seoul:20221228T173000
DTSTAMP:20260419T164405
CREATED:20221221T082326Z
LAST-MODIFIED:20240705T170042Z
UID:6590-1672245000-1672248600@dimag.ibs.re.kr
SUMMARY:Stijn Cambie\, The 69-conjecture and more surprises on the number of independent sets
DESCRIPTION:Various types of independent sets have been studied for decades. As an example\, the minimum number of maximal independent sets in a connected graph of given order is easy to determine (hint; the answer is written in the stars). When considering this question for twin-free graphs\, it becomes less trivial and one discovers some surprising behaviour. The minimum number of maximal independent sets turns out to be; \n\nlogarithmic in the number of vertices for arbitrary graphs\,\nlinear for bipartite graphs\nand exponential for trees.\n\nFinally\, we also have a sneak peek on the 69-conjecture\, part of an unpublished work on an inverse problem on the number of independent sets. \nIn this talk\, we will focus on the basic concepts\, the intuition behind the statements and sketch some proof ideas. \nThe talk is based on joint work with Stephan Wagner\, with the main chunk being available at arXiv:2211.04357.
URL:https://dimag.ibs.re.kr/event/2022-12-28/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR