Loose cores and cycles in random hypergraphs

Research output: Contribution to journalArticlepeer-review

Abstract

Inspired by the study of loose cycles in hypergraphs, we define the loose core in hypergraphs as a structure which mirrors the close relationship between cycles and 2-cores in graphs. We prove that in the r-uniform binomial random hypergraph Hr (n, p), the order of the loose core undergoes a phase transition at a certain critical threshold and determine this order, as well as the number of edges, asymptotically in the subcritical and supercritical regimes. Our main tool is an algorithm called CoreConstruct, which enables us to analyse a peeling process for the loose core. By analysing this algorithm we determine the asymptotic degree distribution of vertices in the loose core and in particular how many vertices and edges the loose core contains. As a corollary we obtain an improved upper bound on the length of the longest loose cycle in Hr (n, p).

Original languageEnglish
Article numberP4.13
JournalElectronic Journal of Combinatorics
Volume29
Issue number4
DOIs
Publication statusPublished - 2022

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Loose cores and cycles in random hypergraphs'. Together they form a unique fingerprint.

Cite this