BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv5.16.4//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:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220816T163000
DTEND;TZID=Asia/Seoul:20220816T173000
DTSTAMP:20220811T182348
CREATED:20220718T235006Z
LAST-MODIFIED:20220718T235006Z
UID:5967-1660667400-1660671000@dimag.ibs.re.kr
SUMMARY:Noleen Köhler\, Testing first-order definable properties on bounded degree graphs
DESCRIPTION:Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability correctly) whether a given input graph has property P or is far from having property P while having local access to the graph. We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree model. We show that any FO property that is defined by a formula with quantifier prefix ∃*∀* is testable\, while there exists an FO property that is expressible by a formula with quantifier prefix ∀*∃* that is not testable. In the dense graph model\, a similar picture is long known (Alon\, Fischer\, Krivelevich\, Szegedy\, Combinatorica 2000)\, despite the very different nature of the two models. In particular\, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders\, based on zig-zag products of graphs. \nThis is joint work with Isolde Adler and Pan Peng.
URL:https://dimag.ibs.re.kr/event/2022-08-16/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220823T163000
DTEND;TZID=Asia/Seoul:20220823T173000
DTSTAMP:20220811T182348
CREATED:20220823T073000Z
LAST-MODIFIED:20220804T235842Z
UID:5971-1661272200-1661275800@dimag.ibs.re.kr
SUMMARY:Raul Lopes\, Temporal Menger and related problems
DESCRIPTION:A temporal graph is a graph whose edges are available only at specific times. In this scenario\, the only valid walks are the ones traversing adjacent edges respecting their availability\, i.e. sequence of adjacent edges whose appearing times are non-decreasing. \nGiven a graph G and vertices s and t of G\, Menger’s Theorem states that the maximum number of (internally) vertex disjoint s\,t-paths is equal to the minimum size of a subset X for which G-X contains no s\,t-path. This is a classical result in Graph Theory\, taught in most basic Graph Theory courses\, and it holds also when G is directed and when edge disjoint paths and edge cuts are considered instead. A direct translation of Menger’s Theorem to the temporal context has been known not to hold since an example was shown in the seminal paper by Kempe\, Kleinberg and Kumar (STOC’00). In this talk\, an overview of possible temporal versions of Menger’s Theorem will be discussed\, as well as the complexity of the related problems.
URL:https://dimag.ibs.re.kr/event/2022-08-23/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220825T100000
DTEND;TZID=Asia/Seoul:20220825T110000
DTSTAMP:20220811T182348
CREATED:20220825T013000Z
LAST-MODIFIED:20220801T134714Z
UID:6007-1661421600-1661425200@dimag.ibs.re.kr
SUMMARY:Brett Leroux\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2022-08-25/
LOCATION:Zoom ID: 870 0312 9412 (ibsecopro)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220830T163000
DTEND;TZID=Asia/Seoul:20220830T173000
DTSTAMP:20220811T182348
CREATED:20220830T073000Z
LAST-MODIFIED:20220805T023825Z
UID:6018-1661877000-1661880600@dimag.ibs.re.kr
SUMMARY:Jun Gao\, Number of (k-1)-cliques in k-critical graph
DESCRIPTION:We prove that for $n>k\geq 3$\, if $G$ is an $n$-vertex graph with chromatic number $k$ but any its proper subgraph has smaller chromatic number\, then $G$ contains at most $n-k+3$ copies of cliques of size $k-1$. This answers a problem of Abbott and Zhou and provides a tight bound on a conjecture of Gallai. \nThis is joint work with Jie Ma.
URL:https://dimag.ibs.re.kr/event/2022-08-30/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220906T163000
DTEND;TZID=Asia/Seoul:20220906T173000
DTSTAMP:20220811T182348
CREATED:20220719T105944Z
LAST-MODIFIED:20220719T105944Z
UID:5974-1662481800-1662485400@dimag.ibs.re.kr
SUMMARY:Bjarne Schuelke\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2022-09-06/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220907T163000
DTEND;TZID=Asia/Seoul:20220907T173000
DTSTAMP:20220811T182348
CREATED:20220614T112030Z
LAST-MODIFIED:20220614T112030Z
UID:5853-1662568200-1662571800@dimag.ibs.re.kr
SUMMARY:Dömötör Pálvölgyi\, C-P3O: Orientation of convex sets and other good covers
DESCRIPTION:We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular\, we compare it to other systems of orientations on triples that satisfy a natural interiority condition. Such systems\, P3O (partial 3-order)\, are a natural generalization of posets\, and include the order types of planar point sets. Our main result is that P3O that emerge from points sets\, p-P3O\, and P3O that emerge from convex sets\, C-P3O\, do not contain each other. We also extend our orientation to other good covers from convex sets and study the resulting P3O’s.\nBased on joint work with Agoston\, Damasdi\, and Keszegh:\nhttps://arxiv.org/abs/2206.01721\nhttps://arxiv.org/abs/2206.01723
URL:https://dimag.ibs.re.kr/event/2022-09-07/
LOCATION:Zoom ID: 870 0312 9412 (ibsecopro)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220913T163000
DTEND;TZID=Asia/Seoul:20220913T173000
DTSTAMP:20220811T182348
CREATED:20220720T105001Z
LAST-MODIFIED:20220720T105001Z
UID:5990-1663086600-1663090200@dimag.ibs.re.kr
SUMMARY:Sebastian Wiederrecht\, Killing a vortex
DESCRIPTION:The Structural Theorem of the Graph Minors series of Robertson and Seymour asserts that\, for every $t\in\mathbb{N}\,$ there exists some constant $c_{t}$ such that every $K_{t}$-minor-free graph admits a tree decomposition whose torsos can be transformed\, by the removal of at most $c_{t}$ vertices\, to graphs that can be seen as the union of some graph that is embeddable to some surface of Euler genus at most $c_{t}$ and “at most $c_{t}$ vortices of depth $c_{t}$”. Our main combinatorial result is a “vortex-free” refinement of the above structural theorem as follows: we identify a (parameterized) graph $H_{t}$\, called shallow vortex grid\, and we prove that if in the above structural theorem we replace $K_{t}$ by $H_{t}\,$ then the resulting decomposition becomes “vortex-free”. Up to now\, the most general classes of graphs admitting such a result were either bounded Euler genus graphs or the so called single-crossing minor-free graphs. Our result is tight in the sense that\, whenever we minor-exclude a graph that is not a minor of some $H_{t}\,$ the appearance of vortices is unavoidable. Using the above decomposition theorem\, we design an algorithm that\, given an $H_{t}$-minor-free graph $G$\, computes the generating function of all perfect matchings of $G$ in polynomial time. This algorithm yields\, on $H_{t}$-minor-free graphs\, polynomial algorithms for computational problems such as the {dimer problem\, the exact matching problem}\, and the computation of the permanent. Our results\, combined with known complexity results\, imply a complete characterization of minor-closed graphs classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every $H_{t}$ as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes. \nThis is joint work with Dimitrios M. Thilikos.
URL:https://dimag.ibs.re.kr/event/2022-09-13/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR