Loading Events

« All Events

  • This event has passed.

Dong Yeap Kang (강동엽), Hamilton cycles and optimal matchings in a random subgraph of uniform Dirac hypergraphs

Tuesday, July 25, 2023 @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)


Dong Yeap Kang (강동엽)
IBS Extremal Combinatorics and Probability Group

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.

We prove “robust” versions of Dirac-type theorems for Hamilton cycles and optimal matchings.

Let $\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$.

Furthermore, 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.

This is joint work with Michael Anastos, Debsoumya Chakraborti, Abhishek Methuku, and Vincent Pfenninger.


Tuesday, July 25, 2023
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B332
IBS (기초과학연구원) + Google Map


Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.