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:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240903T163000
DTEND;TZID=Asia/Seoul:20240903T173000
DTSTAMP:20260415T164323
CREATED:20240319T124710Z
LAST-MODIFIED:20240707T023848Z
UID:8360-1725381000-1725384600@dimag.ibs.re.kr
SUMMARY:Amadeus Reinald\, Oriented trees in $O(k \sqrt{k})$-chromatic digraphs\, a subquadratic bound for Burr's conjecture
DESCRIPTION:In 1980\, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2$ suffices\, which was improved in 2013 to $\frac{k^2}{2} – \frac{k}{2} + 1$ by Addario-Berry et al. \nIn this talk\, we give the first subquadratic bound for Burr’s conjecture\, by showing that every directed graph with chromatic number $8\sqrt{\frac{2}{15}} k \sqrt{k} + O(k)$ contains any oriented tree of order $k$. Moreover\, we provide improved bounds of $\sqrt{\frac{4}{3}} k \sqrt{k}+O(k)$ for arborescences\, and $(b-1)(k-3)+3$ for paths on $b$ blocks\, with $b\ge 2$.
URL:https://dimag.ibs.re.kr/event/2024-09-03/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240906T163000
DTEND;TZID=Asia/Seoul:20240906T173000
DTSTAMP:20260415T164323
CREATED:20240619T001339Z
LAST-MODIFIED:20240707T023728Z
UID:8770-1725640200-1725643800@dimag.ibs.re.kr
SUMMARY:Neal Bushaw\, Edge-colored Extremal Problems
DESCRIPTION:An edge-colored graph $H$ is called rainbow if all of its edges are given distinct colors.  An edge-colored graph $G$ is then called rainbow $H$-free when no copy of $H$ in $G$ is rainbow.  With this\, we define a graph $G$ to be rainbow $H$-saturated when there is some proper edge-coloring of $G$ which is rainbow $H$-free\, but for every pair of non-adjacent vertices $x\,y\in V(G)$\, the graph $G+xy$ formed by adding the edge $xy$ to $G$ cannot be given a rainbow $H$-free coloring.  We think of these graphs as edge-maximal rainbow $H$-free graphs.  (We note that here we make no restrictions on the colorings of $G+xy$ whatsoever\, except that they are proper colorings.  They may use any number of colors\, and need not be extensions of the original rainbow $H$-free coloring of $G$.)\n\nWith this framework in place\, we define the rainbow saturation number and rainbow extremal number to be the largest and smallest number of edges\, respectively\, among all $n$ vertex rainbow $H$-saturated graphs.  The latter of these was defined by Keevash\, Mubayi\, Sudakov\, and Verstraëte in 2007; the former was introduced by B.\, Johnston\, and Rombach in 2019.\n\n In this talk\, we discuss recent progress on both the rainbow saturation numbers and rainbow extremal numbers.  We also give several broad generalizations of these concepts and discuss many open problems.  This talk contains joint work with Vic Bednar (Furman)\, Dan Johnston (Trinity College\, CT)\, and Puck Rombach (Vermont).
URL:https://dimag.ibs.re.kr/event/2024-09-06/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240910T163000
DTEND;TZID=Asia/Seoul:20240910T173000
DTSTAMP:20260415T164323
CREATED:20240807T055137Z
LAST-MODIFIED:20240807T083739Z
UID:9690-1725985800-1725989400@dimag.ibs.re.kr
SUMMARY:Zhihan Jin (金之涵)\, The Helly number of Hamming balls and related problems
DESCRIPTION:We prove the following variant of Helly’s classical theorem for Hamming balls with a bounded radius. For $n > t$ and any (finite or infinite) set $X$\, if in a family of Hamming balls of radius $t$ in $X$\, every subfamily of at most $2^{t+1}$ balls have a common point\, so do all members of the family. This is tight for all $|X| > 1$ and all $n > t$. The proof of the main result is based on a novel variant of the so-called dimension argument\, which allows one to prove upper bounds that do not depend on the dimension of the ambient space. We also discuss several related questions and connections to problems and results in extremal finite set theory and graph theory. This is joint work with N. Alon and B. Sudakov.
URL:https://dimag.ibs.re.kr/event/2024-09-10/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240924T163000
DTEND;TZID=Asia/Seoul:20240924T173000
DTSTAMP:20260415T164323
CREATED:20240721T112741Z
LAST-MODIFIED:20240913T040647Z
UID:9602-1727195400-1727199000@dimag.ibs.re.kr
SUMMARY:Gábor Tardos\, Extremal theory of 0-1 matrices
DESCRIPTION:We say that a 0-1 matrix A contains another such matrix (pattern) P if P can be obtained from a submatrix of A by possibly changing a few 1 entries to 0. The main question of this theory is to estimate the maximal number of 1 entries in an n by n 0-1 matrix NOT containing a given pattern P. This question has very close connections to Turan type extremal graph theory and also to the Devenport-Schinzel theory of sequences. Results in the extremal theory of 0-1 matrices proved useful in attacking problems in far away fields as combinatorial geometry and the analysis of algorithms. \nThis talk will concentrate on acyclic patterns and survey some old and recent results in the area and will also contain several open problems.
URL:https://dimag.ibs.re.kr/event/2024-09-24/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR