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:20230905T163000
DTEND;TZID=Asia/Seoul:20230905T173000
DTSTAMP:20260418T225049
CREATED:20230823T023519Z
LAST-MODIFIED:20240707T073059Z
UID:7531-1693931400-1693935000@dimag.ibs.re.kr
SUMMARY:Sebastian Wiederrecht\, Delineating half-integrality of the Erdős-Pósa property for minors
DESCRIPTION:In 1986\, Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minor if and only if it is planar. In particular\, for every non-planar graph $H$ they gave examples showing that the Erdős-Pósa property does not hold for $H$. Recently\, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa property for minors. \nIn this talk\, we start the delineation of the half-integrality of the Erdős-Pósa property for minors. We conjecture that for every graph $H$ there exists a finite family $\mathfrak{F}_H$ of parametric graphs such that $H$ has the Erdős-Pósa property in a minor-closed graph class $\mathcal{G}$ if and only if $\mathcal{G}$ excludes a minor of each of the parametric graphs in $\mathfrak{F}_H$. We prove this conjecture for the class $\mathcal{H}$ of Kuratowski-connected shallow-vortex minors by showing that\, for every non-planar $H\in\mathcal{H}$ the family $\mathfrak{F}_H$ can be chosen to be precisely the two families of Robertson-Seymour counterexamples to the Erdős-Pósa property of $H$.
URL:https://dimag.ibs.re.kr/event/2023-09-05/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230912T163000
DTEND;TZID=Asia/Seoul:20230912T173000
DTSTAMP:20260418T225049
CREATED:20230817T015106Z
LAST-MODIFIED:20240707T073045Z
UID:7512-1694536200-1694539800@dimag.ibs.re.kr
SUMMARY:Seog-Jin Kim (김석진)\, The square of every subcubic planar graph of girth at least 6 is 7-choosable
DESCRIPTION:The square of a graph $G$\, denoted $G^2$\, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. Wegner’s conjecture (1977) states that for a planar graph $G$\, the chromatic number $\chi(G^2)$ of $G^2$ is at most 7 if $\Delta(G) = 3$\, at most $\Delta(G)+5$ if $4 \leq \Delta(G) \leq 7$\, and at most $\lfloor \frac{3 \Delta(G)}{2} \rfloor$ if $\Delta(G) \geq 8$. Wegner’s conjecture is still wide open. The only case for which we know tight bound is when $\Delta(G) = 3$. Thomassen (2018) showed that $\chi(G^2) \leq 7$ if $G$ is a planar graph with $\Delta(G) = 3$\, which implies that Wegner’s conjecture is true for $\Delta(G) = 3$. A natural question is whether $\chi_{\ell}(G^2) \leq 7$ or not if $G$ is a subcubic planar graph\, where $\chi_{\ell}(G^2)$ is the list chromatic number of $G^2$. Cranston and Kim (2008) showed that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 7. We prove that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 6. This is joint work with Xiaopan Lian (Nankai University).
URL:https://dimag.ibs.re.kr/event/2023-09-12/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230919T163000
DTEND;TZID=Asia/Seoul:20230919T173000
DTSTAMP:20260418T225049
CREATED:20230904T063838Z
LAST-MODIFIED:20240707T073002Z
UID:7590-1695141000-1695144600@dimag.ibs.re.kr
SUMMARY:Donggyu Kim (김동규)\, Orthogonal matroids over tracts
DESCRIPTION:Even delta-matroids generalize matroids\, as they are defined by a certain basis exchange axiom weaker than that of matroids. One natural example of even delta-matroids comes from a skew-symmetric matrix over a given field $K$\, and we say such an even delta-matroid is representable over the field $K$. Interestingly\, a matroid is representable over $K$ in the usual manner if and only if it is representable over $K$ in the sense of even delta-matroids. The representability of matroids got much interest and was extensively studied such as excluded minors and representability over more than one field. Recently\, Baker and Bowler (2019) integrated the notions of $K$-representable matroids\, oriented matroids\, and valuated matroids using tracts that are commutative ring-like structures in which the sum of two elements may output no element or two or more elements. \nWe generalize Baker-Bowler’s theory of matroids with coefficients in tracts to orthogonal matroids that are equivalent to even delta-matroids. We define orthogonal matroids with coefficients in tracts in terms of Wick functions\, orthogonal signatures\, circuit sets\, and orthogonal vector sets\, and establish basic properties on functoriality\, duality\, and minors. Our cryptomorphic definitions of orthogonal matroids over tracts provide proofs of several representation theorems for orthogonal matroids. In particular\, we give a new proof that an orthogonal matroid is regular (i.e.\, representable over all fields) if and only if it is representable over $\mathbb{F}_2$ and $\mathbb{F}_3$\, which was originally shown by Geelen (1996)\, and we prove that an orthogonal matroid is representable over the sixth-root-of-unity partial field if and only if it is representable over $\mathbb{F}_3$ and $\mathbb{F}_4$. \nThis is joint work with Tong Jin.
URL:https://dimag.ibs.re.kr/event/2023-09-19/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230926T163000
DTEND;TZID=Asia/Seoul:20230926T173000
DTSTAMP:20260418T225049
CREATED:20230718T083922Z
LAST-MODIFIED:20240705T162115Z
UID:7392-1695745800-1695749400@dimag.ibs.re.kr
SUMMARY:Carl R. Yerger\, Solving Problems in Graph Pebbling using Optimization and Structural Techniques
DESCRIPTION:Graph pebbling is a combinatorial game played on an undirected graph with an initial configuration of pebbles. A pebbling move consists of removing two pebbles from one vertex and placing one pebbling on an adjacent vertex. The pebbling number of a graph is the smallest number of pebbles necessary such that\, given any initial configuration of pebbles\, at least one pebble can be moved to a specified target vertex. \nIn this talk\, we will give a survey of several streams of research in pebbling\, including describing a theoretical and computational framework that uses mixed-integer linear programming to obtain bounds for the pebbling numbers of graphs. We will also discuss improvements to this framework through the use of newly proved weight functions that strengthen the weight function technique of Hurlbert. Finally\, we will discuss some open extremal problems in pebbling\, specifically related to Class 0 graphs and describe how structural graph theoretic techniques such as discharging can be used to obtain results. \nCollaborators on these projects include Dan Cranson\, Dominic Flocco\, Luke Postle\, Jonad Pulaj\, Chenxiao Xue\, Marshall Yang\, Daniel Zhou.
URL:https://dimag.ibs.re.kr/event/2023-09-26/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR