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:20260312T163000
DTEND;TZID=Asia/Seoul:20260312T173000
DTSTAMP:20260415T172359
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
END:VCALENDAR