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:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230725T163000
DTEND;TZID=Asia/Seoul:20230725T173000
DTSTAMP:20260419T042606
CREATED:20230615T122924Z
LAST-MODIFIED:20240707T073405Z
UID:7282-1690302600-1690306200@dimag.ibs.re.kr
SUMMARY:Dong Yeap Kang (강동엽)\, Hamilton cycles and optimal matchings in a random subgraph of uniform Dirac hypergraphs
DESCRIPTION:A loose cycle is a cyclic ordering of edges such that every two consecutive edges share exactly one vertex. A cycle is Hamilton if it spans all vertices. A codegree of a $k$-uniform hypergraph is the minimum nonnegative integer $t$ such that every subset of vertices of size $k-1$ is contained in $t$ distinct edges. \nWe prove “robust” versions of Dirac-type theorems for Hamilton cycles and optimal matchings. \nLet $\mathcal{H}$ be a $k$-uniform hypergraph on $n$ vertices with $n \in (k-1)\mathbb{N}$ and codegree at least $n/(2k-2)$\, and let $\mathcal{H}_p$ be a spanning subgraph of $\mathcal{H}$ such that each edge of $\mathcal{H}$ is included in $\mathcal{H}_p$ with probability $p$ independently at random. We prove that a.a.s. $\mathcal{H}_p$ contains a loose Hamilton cycle if $p = \Omega(n^{-k+1} \log n)$\, which is asymptotically best possible. We also present similar results for Hamilton $\ell$-cycles for $\ell \geq 2$. \nFurthermore\, we prove that if $\mathcal{H}$ is a $k$-uniform hypergraph on $n$ vertices with $n \notin k \mathbb{N}$ and codegree at least $\lfloor n/k \rfloor$\, then a.a.s. $\mathcal{H}_p$ contains a matching of size $\lfloor n/k \rfloor$ if $p = \Omega(n^{-k+1} \log n)$. This is also asymptotically best possible. \nThis is joint work with Michael Anastos\, Debsoumya Chakraborti\, Abhishek Methuku\, and Vincent Pfenninger.
URL:https://dimag.ibs.re.kr/event/2023-07-25/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR