Co-degrees Resilience for Perfect Matchings in Random Hypergraphs

In this paper we prove an optimal co-degrees resilience property for the binomial $k$-uniform hypergraph model $H_{n,p}^k$ with respect to perfect matchings. That is, for a sufficiently large $n$ which is divisible by $k$, and $p\geq C_k\log {n}/n$, we prove that with high probability every subgraph...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2020-02, Vol.27 (1)
Main Authors: Ferber, Asaf, Hirschfeld, Lior
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we prove an optimal co-degrees resilience property for the binomial $k$-uniform hypergraph model $H_{n,p}^k$ with respect to perfect matchings. That is, for a sufficiently large $n$ which is divisible by $k$, and $p\geq C_k\log {n}/n$, we prove that with high probability every subgraph $H\subseteq H^k_{n,p}$ with minimum co-degree (meaning, the number of supersets every set of size $k-1$ is contained in) at least $(1/2+o(1))np$ contains a perfect matching.
ISSN:1077-8926
1077-8926
DOI:10.37236/8167