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:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260303T163000
DTEND;TZID=Asia/Seoul:20260303T173000
DTSTAMP:20260415T160436
CREATED:20250911T064608Z
LAST-MODIFIED:20260219T013227Z
UID:11576-1772555400-1772559000@dimag.ibs.re.kr
SUMMARY:Chính T. Hoàng\, Problems on graph coloring
DESCRIPTION:A k-coloring of a graph is an assignment of k colors to its vertices such that no two adjacent adjacent vertices receive the same color. The Coloring Problem is the problem of determining the smallest k such that the graph admits a k-coloring. Given a set L of graphs\, a graph G is L-free if G does not contain any graph in L as an induced subgraph. The complexity of the Coloring Problem for L-free graphs is known (NP-complete or polynomial-time solvable) whenever L contains a single graph. There has been keen interest in coloring graphs whose forbidden list L contains basic graphs such as induced paths\, induced cycles and their complements. In this talk\, I will provide a survey of recent progress on this topic.
URL:https://dimag.ibs.re.kr/event/2026-03-03/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260310T163000
DTEND;TZID=Asia/Seoul:20260310T173000
DTSTAMP:20260415T160436
CREATED:20251018T001247Z
LAST-MODIFIED:20260310T112956Z
UID:11743-1773160200-1773163800@dimag.ibs.re.kr
SUMMARY:Dario Cavallaro\, Well-quasi-ordering Eulerian directed graphs by (strong) immersion
DESCRIPTION:Directed graphs prove to be very hard to tame in contrast to undirected graphs. In particular\, they are not well-quasi-ordered by any known relevant inclusion relation\, and are lacking fruitful structure theorems. This motivates the search for structurally rich subclasses of directed graphs that are well behaved. Eulerian directed graphs are a particularly prominent example\, sharing many similarities with undirected graphs. In fact\, it is conjectured that Eulerian directed graphs are well-quasi-ordered by weak immersion\, and even well-quasi-ordered by strong immersion when restricting to classes of bounded degree. We believe that we have a proof of both conjectures\, and I will report on the current status\, progress\, and steps towards said proof and its implications. This is joint work with Ken-ichi Kawarabayashi and Stephan Kreutzer.
URL:https://dimag.ibs.re.kr/event/2026-03-10/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260312T163000
DTEND;TZID=Asia/Seoul:20260312T173000
DTSTAMP:20260415T160436
CREATED:20260226T002641Z
LAST-MODIFIED:20260226T002641Z
UID:12290-1773333000-1773336600@dimag.ibs.re.kr
SUMMARY:József Balogh\, Clique covers and decompositions of cliques of graphs
DESCRIPTION:Two related papers will be discussed: \n1. In 1966\, Erdős\, Goodman\, and Pósa showed that if $G$ is an $n$-vertex graph\, then at most $\lfloor n^2/4 \rfloor$ cliques of $G$ are needed to cover the edges of $G$\, and the bound is best possible as witnessed by the balanced complete bipartite graph. This was generalized independently by Győri–Kostochka\, Kahn\, and Chung\, who showed that every $n$-vertex graph admits an edge-decomposition into cliques of total `cost’ at most $2 \lfloor n^2/4 \rfloor$\, where an $i$-vertex clique has cost $i$. Erdős suggested the following strengthening: every $n$-vertex graph admits an edge-decomposition into cliques of total cost at most $\lfloor n^2/4 \rfloor$\, where now an $i$-vertex clique has cost $i-1$. We prove fractional relaxations and asymptotically optimal versions of both this conjecture and a conjecture of Dau\, Milenkovic\, and Puleo on covering the $t$-vertex cliques of a graph instead of the edges. Our proofs introduce a general framework for these problems using Zykov symmetrization\, the Frankl–Rödl nibble method\, and the Szemerédi Regularity Lemma. It is joint work with Jialin He\, Robert Krueger\, The Nguyen\, and Michael Wigal. \n2. Let $r \ge 3$ be fixed and $G$ be an $n$-vertex graph. A long-standing conjecture of Győri states that if $e(G) = t_{r-1}(n) + k$\, where $t_{r-1}(n)$ denotes the number of edges of the Turán graph on $n$ vertices and $r – 1$ parts\, then $G$ has at least $(2 – o(1))k/r$ edge-disjoint $r$-cliques. We prove this conjecture. It is joint work with Michael Wigal.
URL:https://dimag.ibs.re.kr/event/2026-03-12/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260324T163000
DTEND;TZID=Asia/Seoul:20260324T173000
DTSTAMP:20260415T160436
CREATED:20251114T231517Z
LAST-MODIFIED:20260227T004232Z
UID:11858-1774369800-1774373400@dimag.ibs.re.kr
SUMMARY:Hidde Koerts\, Characterizing large clique number in tournaments
DESCRIPTION:A backedge graph of a tournament $T$ with respect to a total ordering $\prec$ of the vertices of $T$ is a graph on $V(T)$ where $uv$ is an edge if and only if $uv \in A(T)$ and $v \prec u$. In 2023\, Aboulker\, Aubian\, Charbit and Lopes introduced the clique number of tournaments based on backedge graphs as a natural counterpart to the dichromatic number of tournaments. Specifically\, the clique number of a tournament is the minimum clique number of a backedge graph when considering all possible orderings. \nGiven this definition\, it is not immediately clear what the canonical clique object should be. In this talk\, we provide an answer to this question. We show that if a tournament has large clique number\, it contains a reasonably large subtournament from one of two simple and previously studied families of tournaments of unbounded clique number. \nThis talk is based on joint work with Logan Crew\, Xinyue Fan\, Benjamin Moore\, and Sophie Spirkl.
URL:https://dimag.ibs.re.kr/event/2026-03-24/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260331T163000
DTEND;TZID=Asia/Seoul:20260331T173000
DTSTAMP:20260415T160436
CREATED:20250922T145919Z
LAST-MODIFIED:20260308T043639Z
UID:11631-1774974600-1774978200@dimag.ibs.re.kr
SUMMARY:Tung H. Nguyen\, Polynomial χ-boundedness for excluding the five-vertex path
DESCRIPTION:We overview the recent resolution of a 1985 open problem of Gyárfás\, that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path. The proof introduces a chromatic density framework involving chromatic quasirandomness and chromatic density increment\, which allows us to deduce the desired statement from the Erdős–Hajnal result for the five-vertex path.
URL:https://dimag.ibs.re.kr/event/2026-03-31/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR