go-v.orgdoi

Co-degrees Resilience for Perfect Matchings in Random Hypergraphs

Asaf Ferber, Lior Hirschfeld · The Electronic Journal of Combinatorics · 2020

  • DOI 10.37236/8167
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2020

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2020

Abstract

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.

Open the resolved locator · 10.37236/8167

Metadata licence: OpenAlex metadata (CC0)